FCCPO.js.hs.dチームの@nariです。6月24日、一年に一回のICPC国内予選に参加しました。我々は去年に引き続き、traPとして2回目の参加となります。
チームメンバーは@nari、@phi16、@kriwでした。そのうち@nariと@phi16は去年@nonsakoと共にArrows16というチームで惜しくも25位で学内順位3位となり敗退しています。なおこの時、「上位にいるけど選抜されなかった残念(笑)なチーム」に贈られる副賞、ドワンゴ賞を貰っています。微妙に不名誉。
さて、今年ですが、2年目ということである程度自信がありました。というのも、今年は去年いたFCCPCチームが解散となっているため、学内順位が1つ空く、そう思っていたからです。
残念ながらyosupoさんのチームpoの他に、konjouというチームがいたため、5完、全体順位19位、学内順位3位となりました。死因は誤読死です。以下参加記と共に死亡原因を探っていこうと思います。
開始前
@nariはプロ3の課題をやっていました。@phi16は計算機室でぐっすり眠っていました。その後控室に行って@kriwと合流(4時頃)。私は昼飯を食べていなかったのでマックに行ってえびフィレオをお持ち帰りして速攻で食べました。ついでにRedBull投入。
@nariは意気揚々とSpaghetti Sourceを大量に印刷していました。あと蟻本とコンピュータジオメトリを持参。これで問題ないと思っていました。
開始直前、ログインページとIDとパスワードを写していなかったことに気付きました。急いで控室に戻って写します。セーフセーフ。
計算機室のプリンターですが、数が限られているため他のチームに先を譲りました。というか↑で焦っていたので交渉の時間が無かった。
開始
開始直後の作戦はこうです。@phi16がA、@kriwがB、@phi16がCを解きます。@nariはその間に問題をまとめ、解けそうなものから概要を@phi16に伝えたり自分自身で解いたりする感じです。
A
@phi16がブラウザを見つつ解きます。@nariが後から見た感じだとソートして差を取るだけみたいです。速いところは3分でACしていたそうで。
難なくAC。この間にとりあえず1部印刷が終わったので@kriwにBを渡して考察させていました。
B
@kriwに交代します。問題概要としては投票を開票していって、勝利が確定した瞬間にその候補とその瞬間の開票数を出力するようです。The ICPC。バグりやすそう。
案外バグってWA。コードを印刷してデバッグしつつ、できたという@phi16のCに変わります。なお@nariは未だ問題の精読中。
C
@phi16が解きました。エラトステネスの鰤をやるだけのようです。しかもご丁寧に最大値が示されている。AC。そして@nariがその他の問題を見ていて全然解法が浮かばないため焦り始めます。
D
@phi16がBの時にすでに解法をまとめていたため続けてやっていました。見るからに区間DPな制約に区間DPな設定でした。区間DPであることを確認してGOサインを出しましたが、微妙に漸化式が間違っていたらしい。一旦戻って貰って、漸化式の変更を@nariが指摘。その間にBに戻ります。
B
@kriwがデバッグし終えたそうです。AC。
D
@phi16が微修正してAC。
残りはEFGHですが、@nariが問題を読んだ感じ、Fは実装難、Eは(@nariが読み飛ばしたのもあって)幾何？と判断、Gは幾何、HはTheグラフでした。
個人的にHがグラフと分かっているのでHを押して行きたかったです。割当問題はフローを匂わせますが、いい流し方がわからなかったため保留。
E(死因)はN個の立方体の内からK個とって表面積を最小化する問題。制約を誤読しました。この問題は最終的に隣接関係からグラフに落ちるのですが、条件をよく読むとこのグラフの次数はたかだか2です。つまり閉路のみかパスのみ。自明じゃん。この時チームメンバー全員が次数3以上がありえるという誤読をキメていました。
Fはグリッドマップでの包含関係を調べるもので、実装難ですが、偶然にもyukicoderのカゴメカゴメという問題を知っていたので実装のアイデアを持っていました。
Gは幾何です。N<=20がビット全探索を思わせましたがいまいちピンとこなかった。なんか凸っぽい感じが見えたので焼きなまし法とか三分探索とかで実は通ったりしねぇかなぁとか思ってました。
というわけで、気が引けますが実装難のFを進めました。
F
@nariが担当。グリッドマップの包含関係は外側に1マス余分に白マスを置いてからDFSで外から塗りつぶす方針が一番シンプルだと思います。で、DFSして別の連結成分にあたったらそのIDを控えておきます。そのIDの親は当然今塗りつぶしている奴になるので、これで親子関係が抑えられます。抑え終わったら木構造に直して、題意から最終的に2つの木構造の同型判定になります。
木構造の同型判定ですが、Spaghetti Sourceに置いてあった気がして完全に考察してなかったのですが、なんと印刷している中にそういったものは見当たりませんでした。焦ってとりあえずハッシュ関数を考えます。ハッシュ設計をミスって1WAしましたが、2つ目のハッシュ案でAC。よく通ったなぁ……
後から考えると、良くデバッグで使われるように括弧列に直して部分木をソートしてくっつけるということをすれば一意に定まるのでこっちの方が安全ですね。なお、以下が私が実際に使ったハッシュです。
ちなみに木の同型判定に使ったハッシュは以下の感じ(mod 1e9+7で)
def dfs(int p)
ret ← 10007
for(int to : g[p])
ret ← ret * dfs(to)
return ret+107— 鰤 (@_n_ari) 2016年6月24日
さて、残りはEGHです。Gはどう考えてもダメ、行けそうなのがEとHです。Hを@phi16に、Eを@kriwにまかせていました。@nariはダメ元でGを少し考えつつEとHにも思いを馳せていました。
お通夜の時間
お通夜です。
残り30分ぐらいで@phi16がHのそれっぽい貪欲解を思いつきます。PCは空いているのでとりあえず@phi16にそれっぽい実装を任せます。
残り10分。
以下のツイートの事件が起きます。
ABCDFをAC状態にて 鰤「Eってこれ次数2以下だよね」 phi「えっ」 kriw「えっ」 鰤「あっ」チーム誤読死一同「自明じゃん……」(残り10分)
— 鰤 (@_n_ari) 2016年6月24日
そうです。Eは次数が2以下なのです。
サイクルとパスしか無く、K個の1連結成分を取り出す、最小化、こんなの自明です。適当に組んでもO(N^2+NK)に収まります。
お通夜です。
ダメ元で私がEの実装を行いますが当然間に合わず。死んだ鰤の目をしながら今年の国内予選が終了しました。
終了後
yosupoさんに木の同型判定を聞かれます。ハッシュと答えました。
そんなことよりEを実装できなかったショックがでかすぎます。ところでチームpoもFがダメだったらしく5完で爆発炎上だったそうです。
学内1位はチームkonjouで6完でした。このセットは6完すべき。うん。
tokoharuさんにも「このチームがEを通さないのは疑問」と言われました。終わった私達からしても疑問でした。
FCCPC(FCCPOの親集合)の人にも話を聞きましたが、最終的に、「FCCPCという名前で出なかったのが悪い」という結論に至りました。来年はFCCPCです。
終了後は味庵に行って打ち上げでした。なんか無限に@phi16と誤読～～～～～～～～～と言っていた記憶があります。爆発炎上だったチームpoが向かいにいたせいもあってか、私の座っていたテーブルだけ食べ物が残っていました。仕方ないね。
というわけでFCCPOの戦績は5完全体19位学内3位でした。学内1位のkonjouと学内2位のpoは通過が確定していますが、学内3位のFCCPOは微妙です。ICPC国内予選ではワイルドカードがあるらしく、運営の裁量次第で通ったり落ちたりする立場らしいです。通ってたらいいなぁ。落ちたらまたドワンゴ賞でニコニコテレビちゃんぬいぐるみが増えるよ。
以上です。お疲れ様でした。
