Google Code Jam 2012 Round1A/B/C - ぼくのぬまち出張版

まさかR1全部やるハメになろうとは．R1を一発パスしなかったのって始めてかも．

R1A

1062位でギリひっかからず．AS,AL,BS,BL獲ってスコア的にはボーダー上だったのだが，時間負け．特に妙なハマりがあったわけでもなく問題自体も大して難しくはなかったが，単に問題を読み切って理解するのが遅かった．あと開始時にちょっと外出してて15分くらいスタート遅かったのも地味に効いてしまった気がする．

A

ハンパに入力されたパスワードが各位置の文字が一定確率で間違ってるかもしれない開始状況で，正解パスワードを入力するタイプ数の最小期待値を求める問題．まぁ，期待値を求めるだけなのでHaskell的にもキレイに書けるハズ(提出版はそうでもない)．が，問題を理解(ry．特に初期入力を削除した後のリタイプではタイプミスしないんだってとこがわかりづらかった．

B

各ステージに2段階のクリアレベルの設定されたゲームで，全ステージを最高クリアレベル2でクリアするまでの最短ステージ試行数を求める問題．greedyに「いきなりクリアレベル2クリア」「クリアレベル1済をクリアレベル2クリア」「クリアレベル1クリア」の順で拾っていけばよい．ただし，クリアレベル1クリア時はクリアレベル2クリアが難しいものから取る．クリア状況の記憶がHaskellだとちょっと面倒かと思ったのでC++．やはり問題を理解(ry．

C

読んでない．問題の印象ではなく，A/Bにやたら時間を食われたため．

R1B

1299位でまたもダメ．AS,AL,CS獲ってやっぱりボーダー上だったが，時間負け．これはAの二分探索に気付くのが遅れたため．いろいろ鈍ってる感．CLの乱択はなるほどーというところ．

A

競技者集団に審査員によってそれぞれスコアが与えられ，その各人のスコアに，審査員スコア総点の観客投票比率分が加点されて最終スコアとなる競技において，スコアどんけつの競技者だけが失格するとき，各競技者は最低何%の観客投票を得られれば失格しないかを求める問題．始め，対象のプレイヤーVS残りのプレイヤー平均で式を立ててたが，これだと対象のプレイヤーのスコアを明らかに審査員スコアだけで上回ってしまうプレイヤーがいてダメ．なので，対象のプレイヤーVS対象のプレイヤーのスコアより低い残リのプレイヤー平均で式を立てる必要があるが，対象のプレイヤーの観客投票比率を変動させると残りのプレイヤーの集団も変わってしまうのでさてどうするか．二分探索で対象のプレイヤーの観客投票比率を変えながら計算することでパス．Haskellで楽

B

読んでない．問題文が長い．3行でたのむ．

C

ある正数値の集合が与えられたとき，そのdisjointな2つのサブセットで，含まれる数値の総和が等しくなるようなものを見付けるというもの．組み合わせが爆発しているのでSmallは小さいほうから全探索でもよさげだが，Largeは即死する．とりあえずSmallだけ出した．Largeは乱択で候補を搾っちゃえばよかったらしい．このへんはオーダー見て気付けってことだよな．Smallでも速度が心配だったのでザックリC++で．

R1C

463位でやっとパス．AS,AL,CS獲ってボーダーより上．

A

継承関係のDAGが与えられるので菱形継承の有無を答える問題．各親を始点にトポロジカルソート(というかなんちゃら優先探索というか要はなんでもいいが)の容量でダブって辿るノードがあるかを見つけるだけ．瞬殺．ただ，以前使ったHaskellのグラフ系パッケージがグラフデータの構築が(今はどうかしらないが)めんどくさい印象だったので，大人しくC++．

B

長いし小数が見えたので読まずにそっと閉じる．

C

ふたつの組み立てラインからパーツが複数個決まった順番で出てくるので，片方を捨ててラインの次のパーツを取るか，組み合わせられるパーツ同士なら組み合わせる．組み合わせられたセットが最大で何セット作れるかという問題．変形のLCSっぽい．Smallはとりあえず楽して再帰で通したが，Largeはムリゲ．ちゃんとマジメにやる必要がありそうだったけどR1Cともなるともう妖怪メンドクサイが強すぎる．

時間負けが目立ったり問題が長く感じたり読めてないっていうのは，アルゴリズム系短期戦の勘所を忘れてるってことかもしれない．ま，もともとそんな強くないけど．でも流石にここ半年間くらいの残業時間拘束からくる修練不足は確実に響いてきている気がする．TLEも出られなかったし．要リハビリ．