hotpepsiの練習帳

SRM 569

14:31

Div1 Easy (250) TheDevice

問題

• Mビットのデータが書かれたプレートがN枚ある。
• 各ビットの処理がORかANDかXORのMビットのデバイスをプレートで調べる。
• デバイスの全入力を機能を調べるのに必要な追加のプレートの枚数を求める。

方針

• 真理値表とサンプルを読む
• 0と1だけだとORとXORが区別できない
• というように見ていくと、各ビットについて、少なくとも1個のゼロと2個の1が必要
• プレートは何回使ってもいいので、ビット毎の必要枚数の最大値が答え
• ビット毎にループ
• 0があったら...と場合わけ
• 提出
• Passed System Test
• (書き直し)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_569/TheDevice.cpp

Div1 Medium (500) TheJediTest

問題

• 何階建てかの建物に、ジェダイの素質を持った子供がいる。
• ジェダイの騎士は最大K人まで面倒を見ることができる。
• 子供は上下に1階だけ移動できる。
• 必要なジェダイの騎士の数を求める。

方針

• 剰余について考えればよい
• DPかな
• しかし何人移動すればよいかわからない
• 最上階または一番下の階について考える
• 余りが生じても、ひとつ上にしかいけないので、ひとつ上の階で何とかするしかない
• つまり選択肢はないので、greedyに決められるっぽい
• 書くけど合わない
• (終了後)
• N階に注目する
• N-1階に余りがいれば、N階に移動させて、N階で面倒を見る
• 合計がK人に満たなければ、N+1階からも移動させて面倒を見る
• N+1階で場合わけしないように、ダミーを挿入
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_569/TheJediTest.cpp

結果

o-- 185.10pt 305th/567 rating 1322 -> 1364 (+42)

easyはサンプルに2がないので、かなり慎重に解いたがまあまあの時間だった。

mediumは合わないなあと思っていたら、最初に剰余を取ると移動できなくなるので増えてしまうのだった。すごくSRMらしくていい問題。