Shirotsume の日記

嘘Greedyを生やすな

ICPC2023 国内予選　参加記

国内予選の目標．上から難易度順のつもり．

こういうのは早めに書かないと忘れるので．

↓問題文

icpc.iisf.or.jp

↓順位表

icpcsec.firebaseapp.com

神戸大学からShirotsume + MaskoaTS + fky_ = Uriboというチームで出場し，37位で予選通過しました．

練習，立ち回りについて

対面でのチーム戦は全員初めてだったので，チーム戦に特有のコミュニケーションや立ち回りなどの練習を中心として行い，並行してABC後に勉強会を開いていました．

コンテスト序盤の立ち回りは固定化して，まずShirotsumeが問題を印刷してフォルダを作り，MasKoaにバトンタッチをしてA問題を解いてもらう，fky_が印刷された紙を回収するというところまで事前に決めていました．ここらへんであたふたすると後に響くので，ガチガチに決めておいたのは正解だと思います．

Shirotsumeは3人の中で最も学年が上かつレートが高いので，進んでリーダー的立ち回りをしていました．「あと何分で解けそう？」とか，「今思いついている解法はある？」のような声掛けをしていました．泥沼化すると声が減ってしまうので，その時に鼓舞するような声掛けも心掛けていました．また，誤読や嘘解法で時間とペナを浪費するというミスが練習中に起こったことから，B問題以降は問題の概要と思いついた解法を3人で共有するということをルールとして定めておきました．これらについては，結果的に部屋が盛り上がって全員のやる気が増してよかったのではないかなと思います．今後のチーム戦でもやっていこうと思っています．

問題毎の話

最初は，序盤の割り当てを決めていたのですが，あんまり今回は機能していなかったようです．結局全員で読むことになるので，そっちの方がいいかも？

A

先述のとおり，AはMasKoaにやってもらうと決めていました．特に苦労なくサクッと通してくれました．

B

えー戦犯です．

まず問題文読んで「え，AtCoderのPVとかぶってるやんｗｗｗ」みたいなことをしゃべっていました．最初に問題文を読んで，Shirotsumeが上からと下からでたどっていって，隣り合うところで線を引けばよいという解法を思いついたので実装しました．

そして提出すると，

Wrong Answer

そ，そんな…

正直どこでバグってるのか分からなくて，かなりパニックになっていました．そこでfky_が「全部のところに線引いてみてシミュレーションすればええやん」という天才アドバイスをくれたので落ち着きを取り戻すことに成功しました．線を引くというのは配列xの任意箇所に要素を挿入するのと一緒なので，実装もこちらの方が簡単そうです．計算量はちゃんと考えてなくて心配でしたが，実行してみると普通に速く終わったのでOK．ということで提出すると…

Wrong Answer

そ，そんな…

今度こそ頭が真っ白になりましたが，OKの場合の分岐をミスっていただけと気づいて，修正するとAC．

C

私がBの底なし沼にハマっているときに並行して残り二人が考えてくれていました．fky_が方針を思いついたので実装することに．バグらせたりして大変そうでしたが，ジャッジを書いてチェックしながら丁寧に実装することでAC．さすがH黄色．私は進捗を管理したりD問題を書きたくてうずうずしたりしているだけで，Cはほとんどノータッチです．

D

fky_がCの実装をしているときに読んでいました．制約が小さいので多少ごり押しが通りそうということを考えて，1, 2, 4, 8…n - x みたいな集合でansの上界が小さいよね！ということを思いつき，実際にそれが構築可能なことをざっくり証明して，MasKoaに説明して確認してもらっていました．じゃあ答えはdfsとかで全探索で良いよね，計算量は額面ヤバいけど適切に枝刈りすれば定数倍軽くなるよね，ということを確認して，実装すると…

Wrong Answer

そ，そんな…

このミスの原因は，26 = 64なので上界は6や！というShirotsumeのカス過ぎる勘違いによるものでした．修正するとAC．

C, Dを通して順位表を見ると22位になっていて，一通り喜びました．観戦してくれていた後輩によると，この直前は順位が100位とかで結構やばかったとのこと．

E

眺めていて，LISっぽいよね～という話をしていました．実際yだけ見ると広義単調増加になっている必要があって，そうじゃないところは書き替えないといけないみたいなことを考える．ただ，これは筋が悪そうで一回離れた解法を考えようということになり，

dp[i][x][y] = i項目まで見て末尾がx, yである場合

というdpを高速化できないかということをうなりながら考えていたが，結局思いつかずコンテストが終了．

コンテスト終了後

最終順位は37位で予選通過は確実なので，祝勝ムードでした．ずっと観戦してくれていたコーチ兼監督員の先生にEの解法を即説明され，Fも見た目ほど難しくないという話をしていただいた．先生はアルゴリズムが専門ですが，競プロをそれほどしているわけではなく，今回も黙って観戦しているだけでしたが，そこまで考察できているのは本当にすごいと思いました．

終わった後，選手3人で大阪王将に行きました．店員がやたらフレンドリーで面白かったです．

アジア大会に向けて練習を重ね，私たちのベストを尽くして大学競プロ界に神戸ありというところを見せていきたいと思います．