google code jam 2015 Round1A

解いた問題と解けなかった問題書くのサボるのよくない。
oo oo -- 48pt 1689位 通過ならず。次で通過したい。

A. Mushroom Monster

問題

キノコが好きな人がいて、最初の状態と10秒おきのキノコの個数の情報が与えられる。
キノコは、適当に追加されることがありえ、キノコがなくなった場合は追加されるまでなにもできない。
以下の2種類の食べ方をした場合、それぞれ最小何個食べたかを答える。
①好きなタイミングで好きなだけキノコを食べえられる場合
②一定の食べるペースでキノコを食べ続けた場合

テストケース数<=100
Small キノコの個数の情報の数<=10, 各情報でのキノコの個数<=100
Large キノコの個数の情報の数<=10^3, 各情報でのキノコの個数<=10^4

解いた方法

シミュレーション。

①は、単純にキノコが減っていたら食べたということなので、減っていた分の合計が答え。
②は、食べるペースをすべて試し、矛盾が発生しない場合で、食べた合計が一番小さいものが答え。
矛盾は、減っていた場合に、食べるペースよりも減っていたるかどうか。

B. Haircut

問題

理髪師がB人おり、1〜Bまで番号が振られている。
各理髪師の髪を切るのにかかる時間M[i]が与えられる。
今、N人のお客がおり、前から順番に、手の空いている理髪師が番号が若い順に割当たる。
切り終えたら即座に次の客にうつれるとき、最後のお客が割当たる理髪師の番号を答える。

テストケース数<=100
お客の数<=10^9
Small B<=5, M[i]<=25
Large B<=1000, M[i]<=10^5

解いた方法

愚直にやると、お客の数が多いのでSmallでもTLE。

仮にx分の時点で切り終わっている人の数がnum人ならば、num

C. Logging

未開封。