CodeFestival 2014 上海ツアー 参加記 〜コンテスト編〜

結果としては、
1位:snuke (GJ以外の8完)
2位:omeometo (HIJ以外の7完)
3位:アジアの人 (GHJ以外の7完)
という感じで、優勝できました。やったー。
7完のままでも時間の差で勝っていたけど、8問目を残り30秒くらいで通して順位表を面白く出来て良かった。
AOJ-ICPCを埋めまくっていたおかげか実装力が上がっていたらしく、前半6問を2時間弱で終わらせて後半の問題をやる時間ができたのが良かったっぽい。
AOJ-ICPCは神。あと、準急を止めた税金さんも神。



・開始前の準備としては、順位表のページをchrome拡張を使って定期reloadするようにしておいた。
・とりあえずA問題から見る。
・なんかgrayコードっぽい。
・適当に実装する。
・WAたくさん
・自明なミスがたくさんあった。つらい。
・とりあえず順位表を見る
・tozan、omeさん、ロジマシさんしかまだ通してなかった。
・最初の数問でtozangezanとかに勝てないのはわかっていた。
・Bを読む。
・慎重を要する感じで怖かったので慎重にやる。
・こういう感じの慎重系はAOJ-ICPCに割と出てきたのでちょっと慣れた。
・部分ごとにテストして1発AC。バグらなくて良かった。
・Cを読む。
・Regular Polygonは多分正多角形だと思いつつもweblioで一応確認した。
・正方形しかないよね、コーナーケースを考えながら適当に実装してAC
・この時点でomeさんの次の2位(AB早かったtozanはCを飛ばしていたっぽい)
・Dを読む。
・解法はすぐ見えたけど、明らかに実装重いし、バグ出したら一気にペース乱れる問題に見えたので飛ばす。
・「Yakiniku」という文字列につられてFを読む。
・問題設定は簡単そう。
・とりあえず数式を立ててみる。
・あー、ax+bをたくさんの区間に対して求める感じかー
・たこ焼きオイシクナール型segtreeを書く。
・ちょっとデバッグしてしまったけど1発AC
・この時点では多分1位だった。
・とりあえずDに戻ってもりもり実装
・流量を1箇所間違えたり、あきれるようなミスとかあった気がするけど、泥沼デバッグとかはせずに一発AC
・調子がいいとはあんまり言えないけど、ハマったりはしてないからまあまあいいんでは。
・この時点でomeさんに20秒差を付けられて2位
・まぁでもこの段階での微妙な順位はどうでも良いので気にせず次。
・omeさんが解いてるEやるか。
・ゲームの戦略系のDPだ。
・こういうのはメモ化で実装すると楽なやつだ。
・状態の持ち方工夫しないとループ起きそうだなぁ。
・「何ステージ目か」も持てば1ステージ目以外はループしなさそう。
・WA!?
・精度が足りてないのかなぁと思ったがそんなことはさすがになさそう
・問題文を眺め直す「if the difficulty of that stage was 2 or 3,」あっ
・AC
・この時点で1位に返り咲く。
・omeさんはDを飛ばしているっぽくて、引退勢には体力的に厳しそうなのかなと思った。
・なんかここまで、「書き終えてサンプルすんなり通って出したらあっさりAC」みたいなACがCくらいしかなかったけど、どハマりはなかった。
・優勝ラインは700~800っぽい
・少なくともあと1問は解かないと。
・順位表を眺めている時になんかIを解いてる人が結構いたことを知っていたのでIを読む。
・なんかLapin Noirっぽいけど、終末状態は複数あるからちょっと違うか(これは「Mr.X disappearsした後はもうMr.Xは二度と現れない」という誤読によるものだった・・・)
・誤読したまま解く。
・WA!?
・あっ、もしかしてこれ「Mr.X disappearsはそのターンだけ」なのでは
・AC。修正箇所がほんの少しで良かった。
・700点の時点で1位だったので、1・2位くらいは取れそうかなーと思っていた。
・あと1完はしとくに越したことはなさそう
・omeさんがGを通していたので読む
・なんかよくわからないけどよくわからなさそうだった。
・うーん、トイレに行ったりしてる間にも何もわからなかった。
・準急が通してない時点でJは捨てた方が良さそう。
・Hを読む。
・結構ときやすそうな問題だった。
・条件を整理していくと流したくなった。
・結構辺の数が多い気がしたのでグラフを小さくする方法を考えていたけど小さくなりそうにない。
・残り時間も少なくなってきていたので、試しに書いてみることにした。
・書き上げた時点で残り1分にだったのでsubmitしてみたけどサンプルすらあっていなかった。
・絶望しながらコードを見たら明らかに変なところを見つけて書き換えてまたsubmitしたらACした。
・8完、普通に嬉しい
・辺の数については、フローの計算量について疎かっただけっぽくて、減らさなくても普通に間に合った。
・凍結こわい・・・
・omeさんがIを出していて、これがACなら時間差で負けていた。
・こういうコンテストでの優勝は初めてだったのでめっちゃ嬉しい。



各問題の感想

A「Lock」:サンプル入出力を5個書いてみて欲しかったw
B「n-th Points」:面倒なだけだけど、結構ユニークな問題で僕は少しだけ好き。
C「Regular Polygon」:数学系の用語を英語で何て言うかって結構知らないよね。
D「Maze」:復元つらい(◞‸◟)けど、AOJ-ICPCでの圧倒的成長によりあっさり倒せた✌︎
E「Game」:「if the difficulty of that stage was 2 or 3,」はなんか現実に合わせすぎて面倒くさくなるだけだったんじゃないかなぁ。サンプルで落とされないのはつらい。それがなければ結構面白い。
F「Yakiniku」:これは良問。さすが焼肉。
G「Ammunition Dumps」:問題文が分かりにくかったのは残念だけど、問題としては面白かった。意外と気付きにくいもんだなぁ。
H「Dungeon」:なんというか目新しさはない印象だけど、問題としてはなかなか面白く出来ていて好き。
I「Obstruction」:Lapin Noirを知っていると、Lapin Noirに対して「こういう解き方もアリだよね」って言っている風にも感じた。解法は結構違う。Lapin Noir的な解法でも解けそうだけど結構面倒そう。(そもそも誤読してたしね)
J「XORAND」:読んでません。(XOR RANDだと思ってたくらい)ホテルでantaさんにwavelet系のデータ構造に教えていただいた。分かりやすかった。wavelet面白い。


コンテストの運営様お疲れ様でした。
特に英語の問題文とか大変だったのではないでしょうか。
問題面白かったです^^(特に後半)
サンプルはちょっと弱かった気がするけど、リジャッジとか起こってなかったのはプロ。