google code jam 2015 Round1C

今年は突破ならず・・・
oo o- x- 44pt 1335位

A. Brattle ship

問題

R*Cのマスがあり、1*Wの戦艦のマスをすべて言い当てるゲームをしている。
自分は戦艦の場所を見ることができず、言ったマスに戦艦があるかどうかを知ることができる。
ところが、見られないことをいいことに、矛盾が無いようになら戦艦の位置をゲーム中自由に動かされてしまう。
戦艦のマスをすべて言い当てるために必要な最小質問回数を返す。

Small T=55, R=1, 1<=C<=10
Large 1<=T<=100,1<=R,C<=20

解いた方法

largeまで解けた。

O(1)解があるっぽいけど、愚直にループを回した。

戦艦が存在しないと確定できる場所を最適に埋めていく。
R=1の場合、Cマスのうち、左からW番目を質問して、あれば、戦艦をみつけられたし、なければ、Wマスには存在しないことが確定できる。
確定できていないマスのサイズが、W+1以上2*W-1以下ならば、必ず戦艦はあると返ってくるので、隣接するようにマスを指定していけばW+1回(1回は無いと言える)で求められる。サイズがWならば、W回で求められる。それ以外なら「ない」と答えればさらに質問回数を増やすことができるので、そう答えるはず。
R>1の場合は、R-1回は上記の「戦艦がある」と答えるところまでは質問させることができるので、「戦艦がある」と答えるまでの回数*(R-1)回が加わる。

B. Typewriter Monkey

問題

猿がK個のキー(同じ文字が存在するかもしれない)をS回押す。同じキーを何回も押すかもしれない。
押した順番に文字を並べた長さSの文字列ができあがるが、この中に、長さLの文字列Tが含まれる個数だけバナナを上げることにしている。
バナナは必要最低限の数だけ持っていくので、猿にバナナを渡した後手元に残っているバナナの数の期待値を求めよ。

T<=100
Small 1<=K<=7, 1<=L<=S<=7
Large 1<=K<=100, a<=L<=S<=100

解いた方法

smallだけ解けた。

全探索する。
KとSは高々7なので、7^7=823,543個しか文字列がない。
K個のキーで生成できる文字列をすべて生成し、Tが含まれる個数の合計と最大値を求めてあげれば、「(Tが含まれる個数の最大値) - (Tが含まれる個数の合計値)/(生成できる文字列の数)」で求まる。

C. Less Money, More Problems

問題

D種類の異なる金額を表すコインがある。
各種、C枚までしか使うことができない。
1〜Vまでの金額をすべて払えるようにしたい。
あと何種類追加すればすべて払えるようにできるか？

T<=100
Small C=1, 1<=D<=5, 1<=V<=30
Large 1<=C<=100, 1<=D<=100, 1<=V<=10^9

解いた方法

greedyか全探索か迷って、間違ったgreedyでハマってしまった。
終わった後、smallだけ全探索で。

与えられたD種コインで作ることができない最低の金額をeとする。
eを作ることができるようにするために、e以下のまだ持っていないコインを追加してあげる必要がある。
追加するコインの最小数を再帰的に全探索すればよい。

反省

全探索できるなら全探索のほうが安心。