hotpepsiの練習帳

Google Code Jam 2011 Round 1C

23:12

A. Square Tiles (10pt + 10pt)

問題

• グリッドに1x1の正方形のタイルが敷いてある。
• 全てのタイルが敷いてある場所を2x2のタイルで置き換えたい。
• 可能かどうか、可能な場合は敷き方を求める。

方針

• 左上から貪欲に置いていくだけ
• 1マスでも置いてあれば、残りのマスに置けないとだめ
• 右端や下端に1マスだけ置いてある場合を考慮する
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1C_A.cpp

B. Space Emergency (12pt + 25pt)

問題

• 星0から星Nまで、速度0.5の宇宙船で移動する。
• 利用準備に時間tがかかるブースターがL個ある。
• ブースターを使うと、使用してから次の星までの速度が1.0になる。
• 星と星との距離を示すのに、C個の配列が与えられる。
• それぞれの星の距離はC個の配列の繰り返しである。
• 星Nへの最短到達時間を求める。

方針

• 距離を2倍しておいて、ブースターを使った場合に1/2にするのが楽
• ブースターの準備時間より前はひたすら足すだけ
• ブースターが使える区間をリストで持っておく
• 星と星の間にブースターが使えるようになる場合は、準備完了後から次の星までの残りの区間をブースターが使える区間として扱う
• 長い期間から貪欲に使う
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1C_B.cpp

C. Perfect Harmony (8pt + 35pt)

問題

• ある二つの数があり、片方がもう片方で割り切れるとき、ハーモニーと呼ぶことにする。
• 数値の配列Aが与えられる。
• L以上H以下でAの全てとハーモニーが成り立つ数を求める。

方針

• 全探索でsmallのみ通す
• largeは、素因数分解+大きさで場合分けだろうか...
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1C_C.cpp

結果

本番ではA(small+large)+C(small)で28ptだった。

今年はBみたいなのが何とか解けるかも。