Google Code Jam レビュー : Round 1C 2015

R x C の碁盤に、弟が1 x W の戦艦をC方向に沿って置き、兄が碁盤を見ずに戦艦を弾丸で仕留めるゲーム。弟は、兄が弾丸を打つたびに、弟が戦艦を動かしていると兄が気付かない範囲で戦艦を動かすので、弟が戦艦を動かせずに弾丸が当たるまでゲームは続く。目標は、戦艦に当てるための最小の弾丸数を求めること。
兄は、最小の弾丸で戦艦に当てるために、戦艦が存在するマスを戦略的に減らしていく必要がある。要は、弾丸を1発打つとそのマスを含めてC方向の前後Wに戦艦は存在しないことになる。

K個の文字しかないキーボードと、あなたが欲しいL文字の言葉があり、お猿さんがそのキーボードをS回タイプしたときに、あなたが欲しい言葉が何回出現するか。あなたは欲しい言葉が出現した回数だけお猿さんにバナナを与えなければならないので、与える可能性のある最大数のバナナを予め準備している。目標は、予め準備したバナナの数から、お猿さんに与えたバナナの数を引いて残るバナナの数の期待値。
まず予め準備すべきバナナの数(M)を求める。キーボードの文字を考えず、S回タイプして長さLの言葉が登場する回数はfloor(S/L)になる。しかし、例えばS=5でL="ABC"の場合はM=1になるが、L="ABA"の場合はM=2になるので、その考慮が必要。期待値は、与えられたキーボードから欲しい言葉を形成する確率と、S回タイプしたときにその言葉が登場する回数、から求まる。なお、Pythonのfor-else文のelseは、forループが回りきったときに実行される。

ある国の王女が課した新しいルールでは、一回の購入において、同じ単位のコインは、最大C個しか使えない。現在、D個のユニークな単位のコイン(Coins)があるとすると、最大でV円のあらゆる価格のものを買うために、あといくつの単位のコインを追加しなければならないか。目標は、最小のコインの追加数。
愚直にやれば、動的計画法＋メモ化で解けそうな問題。v(<V)円のものを買うためにd(∈Coins)を、使う・使わない、で場合分けしてあらゆるケースを網羅する。コインを使い切ったり、手持ちのコインでは払えなくなったら、新しい単位のコインをC個追加する。コインを単位でソートして保持しているため、新しい単位のコインを追加する際にバイナリサーチで追加するべき箇所（インデックス）を求めている。

Smallのやり方だとLargeでは解けないので、ある価格v(<V)が手持ちのコインで実現できる場合は、v以下の単位のコインで実現できる最大の価格を求める。もし、vが実現できなければ新しい単位vのコインを追加するので、またそれらのコインで実現できる最大の価格を求める。これをVまで繰り返せば良い。