君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

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したコードです。えーと、ソートして貪欲で