hotpepsiの練習帳

Google Code Jam 2015 Round1C

00:15

https://code.google.com/codejam/contest/4244486/dashboard

Problem A. Brattleship

問題

• 戦艦の位置あてゲーム
• R×Cマスに幅Wの戦艦を置く
• プレーヤーは戦艦の位置を知らない
• 1ターンずつどこかのマスを攻撃する
• 戦艦のどこかの部分に当たったら、当たったことがわかる
• 戦艦の全てのマスに確実に当てる手数の最小値を求める

方針

• R-1行については、Wマスおきに攻撃するのが最善なので(R-1)×(C÷W)回必要
• 最後の行については、W*2マス以上はWマス単位で攻撃していく
• 最後に残ったマスの範囲内に必ず戦艦がある
• 残りのマスがW個ならコストW、そうでなければ1回は外すのでW+1
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1C_A.cpp

Problem B. Typewriter Monkey

問題

• K個のキーのあるキーボードを猿がランダムに叩き、長さSの文字列を生成する
• 長さLのキーワードが与えられる
• 文字列Sに含まれるキーワードの個数ぶんのバナナを猿に与える
• 必要な最大数バナナを持っていて、猿に与えた後、残りのバナナの数の期待値を求める

方針

• キーボードの文字別の出現個数を数えておく
• L個入力してキーワードに一致する確率dは、(キーワードのi番目の文字の出現個数)÷KをL回かけたもの
• L文字以降の各位置についてキーワードに一致する可能性があり、それらは独立事象
• なので、バナナの期待値eは、d×(S - L + 1)
• 一方、必要なバナナの最大数は、キーワードを連続で入力できたとき
• キーワードの後半と、キーワードの前半が一致するときは、Lより短い周期になる
• 最大値 - 期待値が答え
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1C_B.cpp

Problem C. Less Money, More Problems

問題

• D種類の硬貨があり、1度の支払いには同時にC枚までしか使えない
• 1からVまで全ての金額に対応するために追加する必要がある硬貨の種類の数を求める

方針

• smallのみ、愚直に埋める
• 支払い可能なフラグの配列v[100]を用意しておく
• 価値dのコインを追加したらvを埋める関数fill (v[i-d]が支払えるならv[i]は支払える)
• 価格1から順番に、価格dが支払えなければ、価値dのコインが必要なので、追加する
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1C_C.cpp

結果

A small, large B small, large C small

77pt 316th

提出したのが全部通るのはとても良い。

http://togetter.com/li/819466