ICPC模擬国内2020 & ICPC2020国内予選 参加記

こんにちは、ホスフィン(mine691)です。
Aobayama_sugarstep(ha15 mine691 tarakojo1019) でICPCの模擬国内と国内予選に参加しました。
青葉山ドロップアウトしてないほうのチームです。

人物紹介

2020/11/06現在
mine691 : B3 この記事を書いている人。AtCoder 水、事務処理担当、知識ゲーに強い。
ha15 : B3 AtCoer 黄色、AC Count Ranking 9位、Streak Ranking 6位のすごい人、なんでも強い。
tarakojo1019 : B2 AtCoder 水、実装と式変形に強い。

チーム名は Aobayama_dropout という別チームのリスペクトです。*1

模擬国内

前日譚1

10月2日くらいにチームが決まりました。チーム決め遅くないか?って気持ちになりますが、誰かが悪いわけではないので仕方ないです。

ha15 さんとは昨年チームを組んでいますが、tarakojo1019さんとは面識がないので、チームとしてやっていけるか少し不安でした。

ある日 Twitter を眺めていると、HCPC(北海道大学競技プログラミングサークル)が AOJ-ICPC で練習会をやることを知りました。

うちの大学の競プロサークルでは、そういうことをやるつもりがないらしいので、チームメイトに相談して参加を決意しました。

実際のところ、ICPC 本番をゴタゴタした雰囲気の中でやるのは辛いので*2、結成間もないチームならチーム練をするべきだと思います。

前日譚2

バチャに出たりKUPCに出たりして、まあまあ雰囲気が良くなりました(はず)。

そんなわけで模擬国内に向けての準備を始めました。

感染症対策により大学の施設が使えないため外部の会議室を借りることにしたのですが、当初予定していた場所に空いているか問い合わせしたら、数時間後に問い合わせフォームが消えていました。(は?意味不明)

仕方ないので別の場所を借りて I got a kotonaki.

模擬国内

レート順に tarakojo1019さんがA、mine691がB、ha15さんがCを見ます。

A が一瞬で通ります。

B はボンバーマンをするだけなので気合で通します。*3

C が実装問らしくて、ha15 さんがすごく辛そうにしていました。それでもなんとかなりそうなので信用して任せることに。(「他チームも通ってないので焦らなくていいですよ」みたいなことを言った気がします)

tarakojo1019 さんと一緒にDを見ます。なにこれ不可能。

こういうの DP とかでできない?実は貪欲とかでできない?などと言って迷走します。

C を通した ha15 さんも合流して一緒に考察を進めます。

普通の括弧列判定の考え方を使うと、左括弧を1個か2個使ったとき、許容される右括弧の個数は区間になる。*4

なので、適当にシミュレーションをして O(N) で解けました。

誰が実装するかという話になったとき、ha15さんに「二人で書きましょうよ」と言われ、困惑しながら二人がそれぞれコードを書きます。

私のほうが早く書きあがったので、とりあえず出すと WA が出ます。

よく見ると、マルチテストケースであることを忘れて break を return にしてました。初心者か???

ha15 さんも書きあがったので実行結果を照らし合わせると、ところどころ結果が違っています。

不安な気持ちになるんですが、自分のコードがバグっていると主張して、ha15 さんのやつを提出させると AC が出て一安心。(実際、出力結果の自明な上界を超えていたので、明らかにおかしいことが分かる)

ちょっと休憩してEを読みます。ここら辺から疲れてきて問題文が理解できません。

なんとなーくグラフでみてフローとかでできないか提案してみますが結構厳しそう。

時間ギリギリになって「2-SATをすれば valid か判定できるのでは?」と提案すると、「それならしゃくとりの要領でできますね。」となるが残り時間が足りないのでお通夜状態となる。*5

結果はABCDの4完、全体38位学内3位で予選敗退順位

やっぱり5完早解きor6完が求められます。

B,C 問題が実装でない or 早く解ける ならもっといい順位になる気がするので、本番のセットを祈るのみです。

模擬国内~ICPC本番

結構チーム戦で勝てるようになってきた気がします。(本当?)

布団で寝ていると国内予選のルールが変わって、ライブラリのコピペが可能になりました。

流石にライブラリゲーは出題されないと思いつつ、他チームとの差を生まないようにするために、他人のライブラリを拝借してぼくがかんがえたさいきょうのライブラリを用意しました。

国内予選

国内予選当日

生活リズムが終了していたのですが、気合で健康を手に入れます。

0時に布団に入ったのに緊張で寝たのには3時半ごろだったのですが……。

朝の10時半から学業があるので早起きします。

12時過ぎに参加する研究室にお邪魔して、もろもろの準備をしました。

私と ha15 さんは 16:10 まで講義に参加するので、一度ここで解散しました。

講義が終わったらダッシュで参加場所に向かい、3人で談笑しながら緊張をほぐします。

国内予選

心臓をバクバクさせながら HP を更新したら問題文が見れません。

近くにコーチがいなくて不安になりますが、チームメイトとワイワイしながら問題が見れるのを待ちました。

問題が見れるようになったので、tarakojo1019さんがA、mine691 がB、ha15 さんがCを見ました。

緊張で B の問題文のサンプルを理解するのに手間取りますが、やるだけなのでやります。*6

AとBがほぼ同時に通って安心します。序盤でペナを出さなくて本当に良かったです。

C が少し大変そうで ha15 さんからHELPが来ます。うーん、約数とか素因数を列挙してやるだけに見えますが、実は計算量がヤバそう?です。

念のため自分も書いたのですが、実行に無限時間かかるし、バグっている部分があったので色々修正をします。

ha15 さんのコードは case 1 に 40 秒くらいかかっており、本人はあまり納得がいっていない様子でしたが、そのくらいなら改善を考えずに実行したほうがよいと説得して提出させます。

無事AC、早いタイミングで提出を促せてよかったです。*7

全員で D と E を見ます。途中まで誤読をしていたのですが、チームメイトのおかげで誤読に気付きました。*8Thank you チームメイト

D は Nの制約的に bit 系なのですが、何を情報に持つか分かりません。

構文の性質を利用することを考えると、max/min の性質が大事そうに見えますが、何も思いつきません。

ちょっと辛くなってきたので休憩しつつ E を考えることになります。

ha15 さんから「無向グラフが与えられる。隣接する2点を選ばないような選び方は何通りか。」という問題は解けますか?と聞かれました。

こういうのを一般のグラフで解くのは厳しいので、「木や二部グラフといった、特殊なグラフの場合なら解けるんじゃないですか?」と言いました。*9

問題文をよく読むと二部グラフとして見れるそうです。

頂点数が N * M / 4 くらいに減らせるんですが、ここから全然進展がありません。(DPで解きたい気持ちになったくらい)

トイレに行って D の嘘考察を思いついたり、軽食を食べて落ち着きます。

うんうん悩んでいると、D 問題を考えていた tarakojo1019 さんから、式の値を固定して、そのほかの変数の大小をbitで分けるのはどうですか?と言われます。

なんとなく正しそうに見えたので、二人でホワイトボードを使って丁寧に詰めます。

計算量的にも大丈夫で解けることが分かったので、ha15さんを呼んで解法を共有し、実装フェイズに入ります。

構文解析は苦手で…」と言う最悪ムーブをして ha15さんに実装をお願いすると…

ha15 さん「じゃあ一緒にやりましょうよ。tarakojo1019 さんも提案したんだからやりましょうよ。」

3人が同じ問題をそれぞれ別々に書き始めます。(??????????)

模擬国内でも同じことをしているのですが、バグらせても謎の安心感があるので落ち着いて実装できます。

ローカルに保存してある構文解析の記事をガン見しているのに、答えが 0 にしかなりません……。

ha15 さんのコードでサンプルが合ったらしいので、提出してもらうと AC できて滅茶苦茶盛り上がりました。

そのあとは順位表を眺めて終了。

結果は全体42位、学内2位で国内予選通過でした!本当に嬉しいです!

感想

正直、チームメイトの実力を考えると、暖色*2の学内チームには勝てないと思っていました。

それでもできることなら横浜に行きたいし、数少ない機会を逃したくありませんでした。

以前 kotatsugame に「Aobayama_dropout を解散して、AtCoderのレートが高い2人を連れてきて組んだりしないの?」と聞いたことがあります。

本人曰く、「Aobayama_dropout のほうが居心地がいいから解散はしない。」でした。*10

確かに居心地のいいチームだと緊張でパフォーマンスが劇的に下がったりしないので、自分のチームもそういうチームにしたいと思いました。

居心地のいいチームにするためにたくさんチーム練*11をして、結果的に(少なくとも私は)居心地のいいチームになったと感じています。

私は、この3人でチームが組めて幸せです。

チーム戦略について

今回限定の特別ルールを上手く生かした戦略ができたと思います。

具体的には、google ドキュメントを利用した点です。(画像はチーム練のときのもの、ネタバレ注意)


f:id:lily728-gg:20201107021509p:plain


ステータスには、そのときしていることを書きます。それぞれの行動を一々聞くのは面倒なので、さまざまな事象が発生する序盤で活躍しました。

考察に関しては、式変形パートを落ち着いて処理できたり、HELPのときに状況を把握するのが楽になります。

謝辞

バチャを開催してくれた HCPC さん、それに参加していた方々、それ以外にも色々な方々にお世話になりました。本当にありがとうございました。

*1:ガヴリールドロップアウト/タプリスシュガーステップからもじってます。数か月前に思いついたチーム名で、音の響きがすごく気に入っています

*2:3人がそれぞれ自由に発言できる雰囲気がないとチーム戦で勝つのは厳しい

*3:こういうのは細かく関数を分割して、それぞれの関数の役割をコメントアウトしておくと実装に迷わないんですよね~。

*4:この考え方は典型なのにパッと出てこなくて精進不足を感じる

*5:誰も 2-SAT のライブラリを持ってないのである。

*6:Union Find を使いたくなりますが、こういうのは配列でやったほうが直感的だと思います。

*7:提出用のケースをみるとかなり悪意のある数字が並んでいるので、愚直が間に合うか不安でした。

*8:'<' と '>' の意味を間違えていました

*9:じょえチャンネルでこういうこと言ってた気がする。

*10:ここエモい

*11:一か月ちょっとでさっき数えたら11回もやってた。コンテスト狂