Codeforces Beta Round #59 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Sinking Ship

implementation, sorting, string

ざっくりと大意

・船が沈みそうなので優先順位にしたがって避難する。
・最初にねずみ、次に女性や子ども、そして男性、最後に船長の順番で避難。
・同じ優先の組？の人たちは一覧の出現順に避難する。

Python2

n=int(raw_input())
d={'captain':[],'man':[],'woman':[],'child':[],'rat':[]}
for i in range(n):
    a,b=[x for x in raw_input().split()]
    if b=='woman': b='child'
    d[b].append(a)
for i in ['rat','child','man','captain']:
    for j in d[i]:
        print j

女性と子供は後から出現順にするのは面倒そうなので先に同じリストに入れてしまった。

B. Settlers' Training

implementation

ざっくりと大意

・n人いるランクがそれぞれ\(a_i\)の兵士たちをランクkに引き上げるのにかかる資金はいくらか。
・ランクアップはそれぞれの同ランクの者の内で1人だけがランクアップしてそれに資金が1かかる。
・1,2,2,3は最初はランク1が1人いて1人がランク2になる。ランク2は2人いて1人がランク3になる。ランク3は1人いて1人がランク4になる。資金1を使った後は2,2,3,4になっている。以下略

Python2

n,k=[int(x) for x in raw_input().split()]
l=[int(x) for x in raw_input().split()]
d={i:0 for i in range(1,k+1)}
for i in l:
    d[i]+=1
ans=0
while d[k]!=n:
    ans+=1
    for i in range(k-1,0,-1):
        if d[i]>0:
            d[i]-=1
            d[i+1]+=1
print ans

多分、シミュするしか手が無いと思う。シミュはランク大きい方から見ていかないとダメです。小さい方から見ていくとサンプル2の1,1,1,1を試せば分かるのですが資金1で1人がランクk達成できてしまいます。ランクは大きい方から見ないとダメです。