2012-04-25
TCO12 Round 2A
Easy (300) SwitchesAndLamps
問題
- N個のスイッチとN個の電灯がある。
- それぞれのスイッチと電灯との位置関係はばらばらである。
- どのスイッチが接続されているか何回かチェックした。
- あと何回チェックすれば対応関係がわかるかを求める。
方針
- 矛盾判定をunion find木で書いてみたりとか
- 確定したやつを取り除いてみたり
- 75分終了
- komiyaさんのを写経
- スイッチの状態をbit化
- i番目のスイッチに着目したとき、そのon/offと連動しているものをbitwise andして、同じグループであるとみなす
- 最大グループのサイズが1なら確定しているので答えはゼロ
- 1度チェックすると、グループのサイズを約半分に減らせる
- https://github.com/firewood/topcoder/blob/master/tco_2012/SwitchesAndLamps.cpp
結果
0pt rating 1363 -> 1377
難しすぎて0点だけどrating上がった。
コードは短いけどなかなか書けない。
Max -= Max / 2;
を
Max /= 2;
と書いたら間違いだった。難しい。
2012-04-24
SRM 541
Div1 Easy (250) AntsMeet
問題
- 直交座標系に蟻が何匹かいる。
- 蟻は縦または横に移動していて、全ての蟻の速度は同じである。
- 蟻同士が出会うと、その場で消滅する。
- 蟻の座標と向きが与えられる。
- 最終的に残る蟻の数を求める。
方針
- シミュレーションしてみる
- 割とすぐ書けたが、実行したら10秒くらいかかった
- 高速化のため、ぶつかる時間を求めてみる
- ある蟻Aと蟻Bの組を考えてみると、それがぶつかるチャンスは1度しかない
- 蟻がぶつかる可能性がある時刻は高々2500個なので、記憶しておく
- 時刻順にシミュレーションし、生き残っていればぶつかる
- お互いに向かってくると位置が0.5単位になるので2倍しておく
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_541/AntsMeet.cpp
Div2 Easy (250) AkariDaisukiDiv2
問題
- 以下のような形式に文字列を分解するあかり関数f(X)を考える。
- 「わーい ○○ あかり ○○ 大好き」
- ここで「わーい」「○○」「あかり」「大好き」は、それぞれ1文字以上の文字列である。
- 「○○」には同じ文字列が入る。
- 与えられた文字列に対して、あかり関数を満たすのは何通りか求める。
方針
結果
o-- 92.77 446th rating 1377 -> 1420
easyを4回連続で落としていたので、そろそろ通さなければと思っていた。シミュレーションしたら全く間に合わなかったので書き直したらバグがずっと取れずに70分かかった。しかしプラス点なのは非常に良かった。2倍していない人がばたばた落ちていたけど、解くのに精一杯で気がつかなかった。
赤い人のコードがシミュレーションだったので手元で試してみたら、VC++の/O2だと間に合わないが、/Oxだと一瞬で終わって衝撃を受けた。といっても最初に書いたコードはいちいちstd::mapに突っ込んで判定していたので、どの道間に合わないものではあった。
div1は撃墜祭りだったが、div2も正答率があまり良くなかったようだ。TopCoderの参加者は計算問題とかが得意で、泥臭い文字列処理は苦手な印象。
div2easyとdiv1mediumは問題文が面白すぎ。
2012-04-20
Code Jam Sprint
A. Android Figurines
問題
- M種類のアンドロイドのミニフィギュアが発売になった。
- それぞれの種類を少なくともK1, K2, ... KM個入手する衝動に駆られた。
- 店にはそれぞれの種類の在庫がL個ずつある。
- 望みの数だけ入手するために最悪何個買う必要があるか求める。
方針
- 最悪ケースでは、同じのばっかり掴むことになる
- ということは、(M-1)種類までは全部買うことになる
- 最後の種類は、M種類のうち最大の個数だけ
- Lより多いものがあれば不可能(-1)
- 全種類とも必要数が0なら0
- https://github.com/firewood/topcoder/blob/master/gcj_2012/CJS_A_AndroidFigurines.cpp
B. Repeated Numbers
問題
- 鴨にゼッケンをつける。
- 書き留める数字の数を節約するために、K桁の数を1ずつオーバーラップして
- 記録することにした。
- 重複している数を昇順に求める。
方針
- 1ずつずらしながらstd::set<int>に突っ込む
- 重複していれば記録しておく
- 最後に昇順に連結
- Nが小さいので特に問題なし
- https://github.com/firewood/topcoder/blob/master/gcj_2012/CJS_B_RepeatedNumbers.cpp
結果
Aのジャッジ解が間違っていて紛糾。それはさておき、普通に3回間違えたので反省しなければならない。4回目には正解を送ったがWAとなった。見直しても合ってそうだったのでもう一度送ったら通った。どうも60分経過時点くらいにジャッジ解を修正したようである。(送信履歴を確認した)
Bは普通に解けた。
一応79位だったのだけど、ジャッジ解が合っていたらたぶん100位に入れなかったので、これはラッキーというしかない。狙った運営ならすごすぎる。
両方ともSRMだとdiv1easyに出てきそうな問題。Aが出てたら死んでたと思う。コーナーケースの注意力が足りない。
ということでGoogle I/Oのチケット買えたのでアメリカ行ってきます。
2012-04-18
Google Code Jam 2012 QR
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が厳しそうである。
2012-04-13
Google Code Jam 2011 Round 1A
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だけなんとか書けた。