Codeforces Round #402 (Div.2)
はい。
http://codeforces.com/contest/779
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で割ったものが必要な入替回数になる。
B. B. Weird Rounding
ざっくりと大意
・nを10kで割り切れるようにする。
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などのようなのはないと思われる。。
C. Dishonest Sellers
ざっくりと大意
・今週の価格aと来週の価格bがある。今週は少なくともk種類の買い物をして来週までにn種類をコンプリートする。コンプするのに最小のお買い物額はいくらか。
Python3
#!/usr/bin/env pypy3 # -*- coding: UTF-8 -*- import sys import re import math import itertools import collections import bisect #sys.stdin=file('input.txt') #sys.stdout=file('output.txt','w') #10**9+7 mod=1000000007 #mod=1777777777 pi=3.1415926535897932 IS=float('inf') xy=[(1,0),(-1,0),(0,1),(0,-1)] bs=[(-1,-1),(-1,1),(1,1),(1,-1)] def niten(a,b): return abs(a-b) if a>=0 and b>=0 else a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b)) def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)] def gcd(a,b): return a if b==0 else gcd(b,a%b) def lcm(a,b): return a*b/gcd(a,b) def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5 def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0 def pscl(num,l=[1]): for i in range(num): l = map(lambda x,y:x+y,[0]+l,l+[0]) return l 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)
当時リアタイでコンテスト参加時のACしたコードです。えーと、ソートして貪欲で