AIM Tech Round (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Save Luke

ざっくりと大意

・ルークの体の大きさがd、空間の広さがL。両サイドから壁が\(v_1\)、\(v_2\)の速度で迫ってくるのをルークはいつまで生きていられるか。
・サンプル1はルークの大きさが2で、壁は初期では0,6の位置にある。1.0経過で壁が2.0, 4.0の位置になってルークは死ぬ。
・サンプル2はルークの大きさが1で、壁は初期では0,9の位置にある。1.0経過で壁が1.0, 7.0、2.0経過で2.0, 5.0、2.666..経過で2と2/3, 3と2/3でルークは死ぬ。

Python2

d,l,v1,v2=map(int,raw_input().split())
l-=d
v1+=v2
print l/(v1*1.0)

ルークが生きられる距離は空間の広さのLから体の大きさdを引いたものになる。生きられる距離は両サイドが\(v_1\)、\(v_2\)で迫ってくので2つの和が1.0経過ごとに縮められる。少し言い方を変えるとルークを殺すためのL-dの距離に\(v_1\)、\(v_2\)の合算の速度でいつ到達するか？を計算することでもある。

B. Making a String

ざっくりと大意

・n種類の文字を使う。
・各文字を最大で\(a_i\)回使いつつ、同じ回数のものがないようにする。

Python2

n=int(raw_input())
l=map(int,raw_input().split())
d={}
for i in l:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
l=list(set(l))
l.sort()
l=l[::-1]
chk=[]
while len(l):
    t=l[0]
    if d[t]==1:
        l.pop(0)
    else:
        if t==1:
            d[t]=1
            break
        elif t-1 in d:
            d[t-1]+=d[t]-1
            d[t]=1
            l[0]=t-1
        else:
            d[t-1]=d[t]-1
            d[t]=1
            l[0]=t-1


ans=chk=0
for i in d:
    ans+=i

print ans

大きい数の方から重複が合ったら1つずつ減らしていく。重複がなくなったときの総和が解になる。