Codeforces Round #402 (Div.2) 参加記

はい。 -xo— (0/0) 1071(-25)
http://codeforces.com/contest/779
A問題が誤読でサンプルすら手動計算合わずでコンテスト中はダメ。B問題は特に誤読もなくサンプルも良かったけど考慮不足ありでプレ通ってシスで落ち。C問題もサンプルが親切でプレ通してシスも通る。でなんとか1完。。。

A. Pupils Redistribution

ざっくりと大意

・AグループとBグループでスコア1の人たち、スコア2の人たち….をそれぞれ同じになるようにしたい。最小の入替回数はいくつか。若しくは不可なら-1。

Python3

ans=0
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
x={i:0 for i in range(1,6)}
y={i:0 for i in range(1,6)}
for i in a:
    x[i]+=1
for i in b:
    y[i]+=1
ans=[0]*2
for i in range(1,6):
    tmp=x[i]-y[i]
    if tmp%2!=0:
        print(-1)
        exit()
    elif tmp>0:
        ans[1]+=tmp
    else:
        ans[0]+=tmp
print(ans[1]//2 if sum(ans)==0 else -1)

0回以上の入替操作で成績xの人の人数をA,Bグループで等しくするには分ける前から偶数でないと不可能になる。偶数なら人数差を2で割ったものが必要な入替回数になる。 コンテスト中は総和だけを等しくすればと勘違いして(各スコアの人数を等しくすれば、総和も等しくはなりますけどね)、サンプル4が手動と結果が合わずであうあうしてコンテスト中にはできずでした。

B. Weird Rounding

ざっくりと大意

・nを10kで割り切れる数にするようにnのどこかの桁を消去する操作をする。操作の最小回数はいくつか。
・サンプル1は2を消して3000にすると103で割り切れる、サンプル2は1と0を消去して0にすると109で割り切れる、サンプル3は3,4,9を消去で10200にすると102で割り切れる。

Python3

t=cnt=0
n,k=input().split()
if len(n)<=int(k):
    print(len(n)-1)
else:
    k=int(k)
    for a,i in enumerate(n[::-1]):
        if i!='0':
            t+=1
        else:
            cnt+=1
        if cnt==k:
            break
    print(t if t!=len(n)-n.count('0') else len(n)-1)

サンプル1のようなので末尾から0以外の数を削除するようにして末尾の0の連続並びがk個以上になれば解決するのが素直に単純なパターン。サンプル3もそれほど変わらない。サンプル2のように桁数が足りないならば0を1つだけ残すようにしてnの桁数、長さ-1が解になる。解は必ずあることを保証するそうなのでnが111などのようなのはないと思われる。 0以外の数を削除した後に2つ以上の0しか残っていない場合には更に0が1つになるまで削除が必要になるのが考慮不足で落ちました。

C. Dishonest Sellers

ざっくりと大意

・今週の価格aと来週の価格bがある。今週は少なくともk種類の買い物をして来週までにn種類をコンプリートする。コンプするのに最小のお買い物額はいくらか。

Python3

n,k=map(int,input().split())
p=n
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
N=[i for i in range(n)]
ind=[0]*n
chk=set([])
d={}
ans=0
for i in N:
    tmp=a[i]-b[i]
    ind[i]=tmp
    if tmp in d:
        d[tmp].append(i)
    else:
        d[tmp]=[i]
        chk.add(tmp)
chk=list(chk)
chk.sort()
chk=chk[::-1]
for i in range(n):
    if i>=k and chk[-1]>0:
        break
    ans+=a[d[chk[-1]][-1]]
    d[chk[-1]].pop()
    p-=1
    if len(d[chk[-1]])==0:
        del d[chk[-1]]
        chk.pop()

for i in range(p):
    ans+=b[d[chk[-1]][-1]]
    d[chk[-1]].pop()
    if len(d[chk[-1]])==0:
        del d[chk[-1]]
        chk.pop()
print(ans)

\(a_i\) - \(b_i\) の差の小さいものから(負の数になるならばより0から遠いもの)が今週買う優先ブツ。というか特に負の数になるものは来週値上がりするので今週で必ず買う。今週に買うk種類はat leastが何度も強調されているように少なくともなので、合計額を最小にするためにはk種類より多く先に買う場合がある。サンプル2もそうなっているはずで親切な問題だった。1週目はとりあえずは長さnで開始して1週目の終了条件は既にk種類以上お買い物済で \(a_i\) - \(b_i\) が正の数になる、来週買ったほうが安い場合に1週目は終了。2週目は持ち越してお安くなったものを買う。また、1週目でk種類を買うとその中に来週のほうが安いものが含まれる場合もある。 その場合でも差の小さいものを優先すれば合計額を抑えることが出来る。C問題だったけど配点は1000だったし、コンテスト全体でも解けてる人が多いので難易度はお察しで。