hotpepsiの練習帳

Google Code Jam 2012 QR

02:08

A. Speaking in Tongues

問題

• Googlereseを英語に翻訳する

方針

• サンプルをそのままコピペすれば辞書が作れる
• そのままだと一番最初の例(zoo)が通らない
• qとzを追加すればOK
• https://github.com/firewood/topcoder/blob/master/gcj_2012/QR_A_SpeakingInTongues.cpp

B. Dancing With the Googlers

問題

• 10点満点×3項目の採点結果がある
• 基本的には±1点くらいに収まる
• 2点だけ突出しているスコアだとsurprising
• 合計スコアとsurprisingの最大人数が与えられる
• p点以上取った人が最大で何人いるかを求める

方針

• 必ずp点以上取っているかどうか判定
• そうでないならsurprisingの可能性があれば+1してsurprisingの総数を-1
• surprisingの場合は(p-2)×2+pを超えていればいいのだが、pが2未満のときはp-2が負になるのでそこだけ考慮する
• https://github.com/firewood/topcoder/blob/master/gcj_2012/QR_B_DancingWithTheGooglers.cpp

C. Recycled Numbers

問題

• A <= x <= Bとなる数値の集合Sが与えられる
• xの先頭の何桁かを末尾に移動してもSに含まれる数をリサイクルペアとする
• リサイクルペアの総数を求める

方針

• 題意を誤解してなかなかサンプルが合わなかった
• smallのみ
• Aから1ずつループ
• 条件を満たしたらunion find木に突っ込む
• 最後に木に入ったやつの総数を求めて2で割る(2回カウントするから)
• https://github.com/firewood/topcoder/blob/master/gcj_2012/QR_C_RecycledNumbers.cpp

結果

A o

B oo

C o-

45pt

Aの出力結果にABCの歌とか、all your baseとか色々入っていたみたい。

去年よりソースコードがだいぶ短くなった。今年は人数が大幅増なのでR1が厳しそうである。