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

A. Valera and Plates

ざっくりと大意

・Valeraはm個の丼とk枚のお皿を持っている。
・n日間の食事計画を立てたが、食器が無くなるまで浸け置きしっぱなしで足りない時だけ使うものを仕方なく洗うが最小の回数にしたい。
・aが1なら丼必須で2なら丼でもお皿でもどちらでもよい。

方針のようなもの

・1なら必ず丼を使うのは問題文通りで、2ならお皿を最優先で使ってお皿を使い切ったら丼を使う。

n,m,k=map(int,raw_input().split())
l=map(int,raw_input().split())
ans=0
for i in l:
    if i==1:
        if m<=0:
            ans+=1
        else:
            m-=1
    else:
        if k<=0 and m<=0:
            ans+=1
        elif k==0:
            m-=1
        else:
            k-=1
print ans

コンテストあった当時もリアタイで参加しててその時は1発ACだったのに、今回練習したら問題文誤読で1WAで成長なさすぎ酷い。。

B. Valera and Contest

ざっくりと大意

・Valeraを含むn人の学生はプログラミングコンテストが好き。
・コンテストが終わってそれぞれの学生はlからrのポイントを得た。
・全員での合計ポイントは\(s_{all}\)。
・上位k人の合計ポイントは\(s_k\)。

方針のようなもの

・\(s_k\)は必ずしもkで割り切れることが保証されていないので余りは1ずつ適当に分配する。
・サンプルの1を見ると最低点のlの人が居ない場合もありうる。

n,k,l,r,sa,sk=map(int,raw_input().split())
ans=chk=0
l=[0]*n
for i in range(sk%k):
    l[i]+=1
for i in range(k):
    l[i]+=sk/k
if n>k:
    for i in range(k,k+(sa-sk)%(n-k)):
        l[i]+=1
for i in range(k,n):
    l[i]+=(sa-sk)/(n-k)
print ' '.join(map(str,l))

リアタイ当時と同じにnとkが等しい場合を考えてなくてミスする。。書き方は簡潔に出来たけど考えとか気付きは進歩してないな。。

C. Valera and Elections

ざっくりと大意

・n個の都市と1からnまでそれぞれの都市に双方向移動できるn-1本の道路がある。
・それぞれすべての都市に移動可能でn-1本の道路ということは循環になる、閉路になってる場所はないはずだと思う。
・tが2の道路は壊れているので修理が必要。
・1が中心になる都市で2からnの都市で選ばれた人は自分の都市から1へ繋がる道路を全て修理する。
・選ぶ都市/人は最小にしたい。

方針のようなもの

・1から経路を終端まで見ていって道路が2だったら選ぶ候補として更新。
・深さ優先探索らしい。。あとで

D. Valera and Fools

ざっくりと大意

・n人の1からnまで一意なナンバリングのFoolがk個の弾丸と銃を持っている。
・行われるラウンドでそれぞれのFoolは自分以外の最も小さい番号に対して\(p_i\)%で銃を撃つ。撃たれると死ぬ。最後の1人になったら撃たない。
・3人Foolがいたら2,3番目は1番がターゲットで、1番は2番をターゲットにするので各ラウンドで1,2番目以外は絶対撃たれない。

方針のようなもの

・あとで