ICPC アジア地区予選つくば大会 参加記
参加記です。Hziwara, hogloidとCxiv-Dxivで参加していました。
- 一日目
家を出る。まだTXにすら乗っていない時間にもうつくばについている人々が大量にいて集合時間を間違えていないか不安になる。調べたら大丈夫そうなので北千住でラーメンを食べる。
https://tabelog.com/tokyo/A1324/A132402/13161350/
食べログで評価が結構高かったので行った。北千住から徒歩5分。
煮干ラーメンなんだけど、煮干特有のきつい感じがなくて、でもしっかり煮干のうまみがある。たまに柚子が口に入って、これがまたスープに合う。おいしかったです。
なんだかんだでつくばに着く。Tシャツを着る前にKLab魔剤を飲みに行ったら係の人に「Tシャツ着ろ」って言われる。何を思ったのか、「But I want to drink it.」とか言ってそのまま飲む(意味不明)。
practiceは暇なのでおやつを食べたりほかのチームにちょっかいを出しに行ったりする。Javaチャレンジがないらしく結構早く終わった。
そのあと懇親会とかあって、みさわさんとフローの話をしたりきゅうりの服で遊んだり害悪しているうちに終わり、ホテルに着く。まともなホテルで何より。
ARCはFだけ考えて、わかったけど実装する時間はなかった。寝る。翌日ちゃんと起きるために目覚ましを5回くらいかける。
- 二日目
起床に成功する。なんと朝食を食べる。この時点で勝利である。(そんなことはない。)
なんだかんだでコンテストが始まる。英字キーボードに慣れていないのでGから読む。正確にいうと、
hogloid「最初のほうDEGwerがやってもしょうがないだろうから真ん中辺から読んで」
ぼく「はいじゃあFくらいから読みます」
コンテスト開始
Fの問題文が長いことに気付いたぼく「Gから読みます」
最悪である。
Gは読んですぐ解法がわかり若干不安になる。制約500000を50000だと思い込んで動的構築segtreeで二分探索とか言う。詰めずに後ろを読み進める。←あまりよくない
最初のほうが通されている。少しパソコンが開いたすきに書き始めるが、途中でさすがに量が多いので詰め直したほうがいいという結論に至り、交代して真面目に詰める。setでいいことに気付く。
再びパソコンに触れ、細かいことを口に出しながら実装するがサンプルが合わない。印刷するとバグに気付くが出すとREとか言われる。結局印刷デバッグを何回かやったら通った。3回もWAを出して、クソだなぁみたいな気分になる。
後ろのほうは読み進めた時とかに若干方針を考えたものがあったので、Iの雰囲気をふじわらさんに伝えてそれっぽいものを書いてもらう(証明とかは全然していない)。四角形のほう(のちょっとした一般化)しか渡しておらず、そりゃ通るわけがない。Jはざっと見たときにどうせ山登ればいけるだろう(幾何なので僕は実装しないけど)と思っていたので、まあ幾何やって山登りするだけなので時間できたらやっておいてくださいみたいなことを言う。
その間にhogloidと2人でHを考える。無向辺からなる木を縮約してDAGかどうか見るのでinfinite判定ができるというのを思いつき、解けそうな見た目の問題になったのでhogloidに投げると、hogloidが残りの部分を思いついてhogloidが実装をはじめる。量は多いけどまあ通せるやろみたいな気分でいる。
ふじわらさんとIがバグなのかどうかわからんなぁとか言っているうちに、縦横が互いに素に近い場合そもそも四角形にする必要がないやんということ(当たり前である)に気付き、それがわかるとオーダー解析の方針も一瞬で見える。三角形の場合と四角形の場合を両方使うとどちらもsqrtくらいのオーダーになるという話だった。見切り発車からの方針転換が起こっており危険なのだが、幸いちょっと変えるだけで済むらしい。ふじわらさんに伝える。
なんやかんやでHIが通り、JKが残ったのでふじわらさんがJをやる。Kをひたすら考える。全く分からないのであきらめて3並列でJのデバッグをしようとか思ったくらいの時刻にJが通る。のこりは暇である。凍結前トップで、終了直前にSJTUのFHの提出が両方増えており、ペナルティ的にもこれが両ACでなければ1位だという気分になる。
あんぱんがおいしかった。
解説は長く暇だった。聞きたかったKは、知識ゲーで解けるわけなしだった。SJTUはなんでこんなものを知っているんだ。
結果発表である。SJTUのどちらかが間に合っていないのを祈っていたし終了直前に提出が増えているので通っていないと思っていたが、両方通っていた。終了9分前と6分前にACしたらしく、負けを認めた。まあ選抜的には中国は関係ないので選抜としては実質1位(これはコンテスト終了時にはわかっていた)なので喜ぶ。
あとは企業ブースで問題を解き続けておなかがすいたのでそこらへんに生えているペンネを食べて、電車に長々と乗っておしまい。
去年と違って中難度が大量に並んでいたので得意セットだった。終了15分前くらいにできることがなくなるという一番いい形だった。得意分野が違うので3人いれば中難度は誰かは解けて、チーム戦は最高という気分になった。なにせ結局1問しか実装してないからね。一人ハマってもその間他が進み続けるからなんだかんだでカバーできるというのもチーム戦ならではの安心要素で、そういうふるまい方まで含めてやっぱり面白いなぁと。HとかIとか問題として面白かったし。特にHは大好き(しかも実装すらせずに済んで最高)。
まあ個人のふるまいとしてはGで無駄にペナルティを使ったので実装面ではあまりよくなかったし反省要素はあるけど、結局完数単独の2位だったし、解法は結構出したのでそこそこ貢献できたと思っています。まあなんだかんだで結果が良かったし満足しています。
WFがんばるぞい。
