hotpepsiの練習帳

Google Code Jam 2012 Round 1A

23:39

A. Password Problem (10pt + 10pt)

問題

• めっちゃ長いパスワードを使っている。長さはBである。
• そのうち、すでにA文字入力済である。
• 入力済の文字が合っている確率が文字数ぶん与えられる。
• その状態から、パスワードを正しく入力するまでのストローク数の最小の期待値を求める。

方針

• 入力した長さが間違っているというのは考慮しなくてよい
• 新たに入力するぶんは完全一致するとみなしてよい
• 最終的に、入力した文字は完全一致する必要がある
• つまり入力した文字が使える確率は、それまでに入力した文字が全て一致する確率 p0*p1*p2... である
• BSキーで削除すると、削除した部分は全て一致するとみなしてよい
• ということで、全て一致する確率のテーブルだけあれば計算できる
• 全部打ち直した場合を考慮しておく
• https://github.com/firewood/topcoder/blob/master/gcj_2012/1A_A.cpp

B. Kingdom Rush (15pt + 18pt)

問題

• Kingdom Rushというゲームをクリアしたい。
• ゲームはN面からなる。各面はレベル1とレベル2からなる。
• 全ての面のレベル2をクリアすればゲームクリアである。
• レベル1をクリアすると星がひとつ、レベル2をクリアすると星がふたつもらえる。
• ただしレベル1をクリア済でレベル2をクリアしたときは星がひとつだけもらえる。
• 各面のそれぞれのレベルをクリアするのに必要な星の数が与えられる。
• 星の条件を満たしている場合、1プレイでそのレベルをクリアである。
• 星の条件を満たしていない場合、そのレベルはクリアできない。
• ゲームをクリアするのに必要な最小のゲームのプレイ数を求める。

方針

• 貪欲でやってみる
• レベル2がクリアできるものを全て処理する
• クリアしていないレベル2のうち最も星が少ないやつがクリアできるようになるまでレベル1をこなして星を稼ぐ
• そこで無理なら失敗
• 書いたがIncorrect...最適解じゃないのかな
• 簡単なやつから取ると無駄があるっぽい
• クリアできるレベル1のうち、レベル2の星が最も大きいやつから取ればよさそう
• いけた
• https://github.com/firewood/topcoder/blob/master/gcj_2012/1A_B.cpp

結果

oooo-- 2WA 53pt 989th

超ぎりぎりだけど通過!!

今年の目標はGCJ R1突破とTopCoderで一瞬黄色になる、だったのだけど両方達成できて嬉しい。