hotpepsiの練習帳

Google Code Jam Qualification Round 2015

01:42

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

A. Standing Ovation

問題

• 友人のオペラの公演で観客全員をスタンディングオベーション状態にしたい
• ある観客がSO状態となるためにはSO状態の観客がSi人以上必要である
• 観客全員をSO状態にするためのサクラの人数を求める

方針

• Sが小さいほうから数えていき、S人未満ならサクラを追加する
• https://github.com/firewood/topcoder/blob/master/gcj_2015/QR_A.py

B. Infinite House of Pancakes

問題

• D個の皿に何個かのパンケーキが配られる
• 毎秒、全ての皿のパンケーキを1つずつ食べるか、または、どれかの皿のパンケーキをどこか(新しい空の皿でもよい)に移動できる
• 全てのパンケーキを消費する最小秒数を求める

方針

• 分割するなら最初が一番いいので、最初に必要な分割を行い、そのあとほったらかしにする
• X個より多ければ分割、でX=1～1000で試す
• https://github.com/firewood/topcoder/blob/master/gcj_2015/QR_B.py

C. Dijkstra

問題

• i、j、kからなる基本文字列Lと、その繰り返し回数Xが与えられる
• 隣接する2文字は置換ルールで1文字に短縮できる
• 3文字の文字列ijkに短縮可能かどうか求める

方針

• 数値に変換して先頭からシミュレーション
• 先頭がiになるまで次の文字と短縮していく
• 文字がjになるまで次の文字と短縮していく
• 文字がkになるまで次の文字と短縮していく
• 残りの文字が空か、すべて短縮したら1(同じ)になるかどうかを調べる
• 同じ文字列を4回かけると1になるので、4の倍数分はカットする
• https://github.com/firewood/topcoder/blob/master/gcj_2015/QR_C.py

結果

A、B、C-smallで49点。例年より通過枠が厳し目か。

Cで末端の処理をX % 16としていたが、これだと残りがちょうど16回の場合に誤判定するので、(X > 4のとき)4 + (X % 4)のようにしないといけなかった。

http://togetter.com/li/807476