ICPC2020国内予選参加記
チーム Chabashira (NOSS, まほろば, まつした)としてICPC国内予選に参加しました。
追記(2020/11/09)
チームメイトの参加記
- ICPC2020国内予選参加記 - まほろば精進日誌
- ICPC2020国内予選に出場しました｜MacaronBLOG
開始前
開始直前まで研究室のタスクがあって忙しく、前日はあまり眠る時間がとれなかった… 若干不安になりつつも時間のすきまにリハーサルのKを通したり、他人やチームメイトのライブラリを回収して準備。
コンテスト環境は完全オンラインでチームメイトと通話をつなぎながらやっていました。
コンテスト本番
16:30とコンテストページを更新するとアクセスできず「あれ？」となる。チームメイト全員がアクセスできずちょっと焦る。Twitterを覗きたい気持ちを抑えつつ運営との連絡方法などを確認していると徐々にサイトが復帰し始めたので待機。
16:40頃に突然問題が表示されコンテスト開始。
初動はAをまつした君、Bをまほろば君、Cを自分が担当。
Cは問題文は非常にシンプルで のとき
の最小値を求める整数問題。
なのでそれなりに高速なアルゴリズムが必要かもしれないと考える。(問題を読んだときはこれを思い出してよくない予感がした)
しかし、考えても何もわからず。これやばくね...？
この間にチームメイトが順調にA,Bを通す。
まだ自分がCの方針を立てられていないので模擬国内の反省1を活かし、まつした君をCのヘルプに呼んでDをまほろば君に読んでもらう。
Cでの付近を探索する方針は
が素数のときに破綻するので、とりあえず愚直に約数列挙をするコードを実行してみようという話になる。
Cを解ける気持ちにならなかったので実装と実行をまつした君に丸投げお願いしてDに移る。
まほろば君からDの概要を聞くと構文解析系の問題なのでちょっと難しそう。この時点でCが詰まっていてDも通せないとなると予選突破は厳しいのでDを通すぞ！と心の中で気合を入れる。
Dを受け取り他の問題をまほろば君に任せる。
文字の種類数が であることからエスパーすると
の計算量になりそう。なのでTSPのような順列を扱う系のbitDPにならないか考察する。
式から文字同士の前後関係を有向グラフに変換できないか？などの考察しても良い方法思いつかなかったので模擬国内Eを反省にして2冷静に条件を見直してみる。
式にはmin,max演算しか含まれないので実はかなり単純。2つの式の出力が一致するということだから各式の出力は知りたい。出力の通り数が少ないのでこちらを固定してみる。
するとある注目した文字が出力されるかどうかの判定は...その他の文字が注目した文字の前か後かのどちらにあるかだけわかっていればできる！！！
つまり文字を前後2つのグループに分ける方法を全探索すればよくそのときの通り数も簡単に計算できるので解ける！
念のためまほろば君に解法を確認してもらうと解けていると同意がもらえたのでさっそく実装にとりかかる。構文解析パートはこんなときのために実装の練習をしていたのでサッと実装ができた。精進していた過去の自分に感謝。
サンプルも無事に合ったので提出すると...AC！激アツ。
この時点でDを通しているチームは十数チームくらいしかいなかったのでかなり嬉しくなる。
あとはCを通せれば予選突破にかなり近づくのでCの状況をチームメイトに確認する。
約数を愚直にやっていく解法は実行が遅かったのでまほろば君が枝刈り高速化したコードを書いてくれたらしい。とりあえず実行してもらうとなぜかよくわからないが(？？？)割と速く実行が終わった
ここで伝家の宝刀「コンパイルオプション -O3 + 感謝の言葉」バイナリファイルに感謝の言葉をかけると実行速度が速くなることが知られている3のでチームみんなで通話越しにありがとう、ありがとうと唱えると無事にテストケースの実行が終了する。提出してもらうと...AC！ ありがとうC++のコンパイル最適化。
この時点で4完24位(学内1位)ぐらいでそれなりの速度で4完できたのでかなり気持ちが安らかになる。これはもしかしたら初の5完いけるのでは？という雰囲気になる。
Eはまほろば君がすでに考察を進めてくれていて点が4つのグループに分けられてそれぞれのグループはgrid状になっていることを聞く。ここまでだと30*30のサイズなので幅がもう半分の15程度だったらbitDPできるのになーとチームメイトに伝える。みんなで上手いこと幅を減らせないかと考えたけど結局ここから進まなかった。
順位表をみるとEよりFが通されているのでFをよむ。辺の切断は時刻を逆順にみると結合なのでUnionFindで管理できる。連結成分のサイズと最適地の候補の集合をうまいこと管理すればよさそうという話になる、が、怖いコーナーケースが見つかったりサイズの確認回数がO(NM)になる/ならないのような話がたくさんでてきて頭が壊れる。
正直なにもわからずE,Fを眺めていたら時間が経過...。
コンテスト終了5分前くらいにまほろばくんが永続UnionFindをつかった実装でFのサンプルがあったらしいので驚く。これで通ったらマジ天才だなと思いながら提出してもらうとWA... 出力形式や怪しい答えも出力していないと確認してもらったのでもはやここまで。コンテストが終了した。
結果
チーム Chabashira の結果は ABCD 4完 33位(学内1位) でした。
無事に国内予選突破です！
コンテスト後
同大学の他チームとも通話をつないで解法の共有をしたり感想を話したりした。他チームもCは約数列挙してゴリ押しだったぽい。ここで高度合成数の話を思い出したので調べてみると 以下では約数の個数は最大でも
程度らしい。この辺の話を知っておきながら、本番中に約数の個数が少ないことを指摘出来なかったのもしかして戦犯では？ EはTwitterで流れてきた解法が天才すぎて完敗。
感想
Cが解けなくても1人で固執せずにチームメイトに託してDを見れたのはとてもいいムーブだったと思う。おそらくあのままずっとCを考えてDに移っていなかったらもっと解くのが遅くなっていた。今後もやばくなったら積極的に投げていきたい。Fはもっと冷静に考えていれば解けたかもしれない。
全体としてはDの考察・実装ができたのでチームの中での役割を果たせたかなと思う。
連絡手段がチャット・通話のみという環境の中戦ってくれたチームメイトに感謝。横浜大会オンサイトで会いましょう。
