hotpepsiの練習帳

Google Code Jam 2011 Round 1A

00:47

A. FreeCell Statistics

問題

• フリーセルを今までG回以上やった
• そのうちD回解いた
• 今日のプレイ回数はN回以下
• 今日プレイしたうち、ちょうどPdパーセント解けた
• 今日のプレイ回数が、今までのプレイ回数全体のちょうどPgパーセント
• 可能かどうか求める

方針

• 0%と100%のときを場合わけ
• 100とPdとのGCDをgcdとする
• 100÷gcdが分母として可能性のある数の最大値
• 最大値がN以下ならPossible
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1A_A.cpp

B. The Killer Word

問題

• Seanと単語当てゲーム(Hangman)をする
• Seanはある並びの文字列を持っていて、その順で当てにくる
• Seanが文字を言って、外れたら減点
• ただし可能性のない文字は言わない
• 最も減点される候補を求める

方針

• 同じ見た目になる文字列グループに分類する
• 残り候補が1のものは除外する
• 各グループで1文字開示してスコアを計算
• 分類(繰り返し)
• 最大のスコアのものが答え
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1A_B.cpp

C. Pseudominion

問題

• カードを1枚ずつ出していくゲーム
• カードには、山からひける枚数(c)、スコア(s)、ターン数増加(t)、の三つの属性がある
• 手札と山札が与えられる
• 残り1ターンからはじめるときの最大のスコアを求める
• smallのみ
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1A_B.cpp

方針

• カードを、ターン増加あり(T)、枚数増加なし(C0)、枚数増加あり(C1)に分類
• Tカードは最優先で使う
• C1カードを0枚から1枚ずつ増やして評価
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1A_C.cpp

結果

本番では0ptだった。

一年かかって復習したがなかなか難しい。

Aはまあ、言われてみればなるほどという問題。

Bは普通に実装すれば解けるのだが、違うグループの点数を加算したりしてバグがなかなか取れなかった。

Cはsmallだけなんとか書けた。