かっつのメモ帳

主に競プロ 時々日記

ICPC 国内予選2020 参加記

チームgive us sociabilityで出場し、3完52位でした。

目標としていた4完&アジア大会進出が叶わず、同大学内でもライバルチーム2つに負けてしまい、良い結果とは言えない内容でした…。

f:id:KKT89:20201106224557p:plain

模擬国内参加記

kkt89.hatenablog.com

模擬国内〜本番

  • チームでAOJ-ICPCの問題を集めたバチャをやるようにしていた。(こんな感じで7回やった)

  • 本番数日前は構文解析バチャ構文解析系の問題に触れるようにしたり、去年のE問題をやったりと実装の練習を多めにするようにしていた。

  • 本番前に飛ばしていた数問を解いてAOJ-ICPCの400点以下が全て埋まった。

本番

僕がA問題、HyadoがB問題、HotmanがC問題以降を最初に見て実装が面倒そうだったら僕に投げて担当をswapする。という戦略を取ることに。

…と、意気込んでいたが予定時刻になっても競技用サイトに繋がらない。焦ったが他の二人も繋がらないようなので僕の環境のせいでは無いと知りホッとした。

全体で起こったシステムトラブルらしいので落ち着いて待つことにする。

たまたま手元にあった声グラを眺めていたら(?)いきなりサイトが復旧しコンテストが始まったのでびっくりした。なんやかんやでコンテスト開始。

A問題はやるだけだったので、ささっと書いてAC(0:02:49)

B問題は読んでいないがHyado君が書いてACしていた(0:08:51)

C問題はhotmanが計算量よく分からないけど素因数分解貼れば終わり、と主張していたので任せていると実行に少し間があったが程なくしてACする(0:29:38)

前半の3問のムーブは悪くなかったと思うが、この時点で既に同大学内3位だったのでここから先の4問目5問目が大事だね、という話をした(結局この時点から完数を伸ばせなかった…)

Aを書いた後、Dを見ると構文解析だったのでウキウキで問題を読む。

問題概要を理解したが全然方針が浮かばなかった。取り敢えず無駄にならなさそうな登場する文字列の座圧を先に書きつつ、構文解析パートも問題なく実装できそうだったので、概要をHyadoにも投げて二人で考察することにした。

↓↓以下本番中に考えてたこと↓↓

 N! の愚直は流石に無理。最終的に一致する文字を固定すれば排反に数え上げが出来そう。だがこれだけでは情報が足りない。最終的に出てくる文字を固定すると「○○は□□よりも前/後」という情報が出てくるから、この情報を基にしたトポロジカルソートの数え上げはbitDPで可能。しかしこれでは排反な数え上げが難しそう。しかも二分木の葉同士の比較だったら良いが、「(○○と△△のうち前に来るもの)は□□よりも前/後」みたいに情報のネストが深まるととても扱いにくい。一つの文字列に注目すると文字列長に関する制約からS/Tに関して登場する不等号の数は高々24個。なので比較結果を全探索することが出来る。しかしSとTの情報のマージが不可能なのでこの方針もダメ。


こんな感じで泥沼化していたので、終了後解法ツイート見て暫く、なるほどな〜〜〜〜確かにな〜〜〜〜いやーそれはそうだな〜〜〜〜の言葉しか発せなくなってしまった。

こうやって思考の流れを言葉にしてみたら何か見えるかなと思ってやってみたけど、普通に難しい問題だと思いました(小並感) 足りなかったのは、最終的な文字を固定→何が分かれば N!通りを試さずに実際にシミュレーションが行える?っていう考察だったのかな。


以下辛いので覚えてることをサクッと書いていきます。

  • 割と早い段階でhotmanがEは行を4分割できてそれぞれに独立集合の数を求めるbitDPで答えが求まると主張。直に書き上がったがWA。

  • 順位表を見たHyadoがFを読む、良しなにマージテクをすれば行けそうな問題ぽく見えるとのこと。あまり問題間を迷走するのも良くないと思い10分だけ考察に回った。愚直解は分かったが真面目に(?)やろうとすると方針も実装も詰め切る自信が無かったので僕はFに行くのを辞めておこうとなった。

  • 軽く話聞く限り解法は正しそうだったので任せていたが、ラスト40分でDを諦めEのデバックに回った。実際に手を動かして考察は確かに良さそう、となる。

  • Eのコードを見るが添字周りが色々不安でどこに手をつけて良いか分からなかったので、怪しそうなところを投げつつ僕も1から添字周りを書き直すことにした、が修正は間に合わずこのままコンテスト終了。

感想

ここ数年早稲田からはアジア2チーム出していて今年は3枠を目標に、という話をしていたのに蓋を開ければ通過は1チームだけになってしまって情けない&応援してくれていたコーチOBの方に申し訳ないなぁと感じています。

チームメイトは終了後、あと一歩って感じがして惜しいなという会話をしていたが、まあこんなもんかなという思いも少なからずあり(こういう一歩を詰め切るのは見た目以上にギャップがあるものだと思うので)。

とはいえ、幸いにも僕たちは来年以降もチャンスがあるので、来年に向けまた出直して行きたいと思います。

今また競技プログラミングのモチベが高まってるので頑張ります。ただICPCを理由に炎上させて放置してる大学タスクと明日から向き合わないといけないのが辛いです(おわり)