はじめに

ICPC 2021 国内予選に 202 Accepted という名前のチームで出場をしていました！結果は，ABDE 4 完で $ 32 $ 位の学内 $ 2 $ 位でおそらく通過となりました！よーし．ホスト校枠もおそらく温存かな？ ~~去年ホスト校枠にすらひっかからず予選落ちした時は顔面ぐちゃぐちゃになっていたので本当によかった…~~

自分自身は BD を担当していました（詳しくは後述）．

チームについて

チームメンバーは HayatoY, auaua, centipede_human です．使用言語は全員 C++．後輩チームに一人今年 ICPC を引退する老の者が混ざった形となった．

「国内予選の時にはみんな黄色っぽいですね」みたいな話をしていたのに気づいたら本番時点で黄色は auaua くんだけになっていました．どうして…

個人的にはチームの構成自体は悪くないなと思っていました．最近のコンテストで，それぞれのメンバーの結果が芳しくない場合でも OR を取ればまあ…みたいな回も結構あったような気がする．具体的にどういう風に得意不得意を補っているのか全然よくわからないが，どうやら得意被りはあまりしていなさそうだった． $ 3 $ 月までにお互いの傾向をよりよく知れたら本番のムーブ改善につながるだろうか．

実際，模擬国内でもまあまあぐらいのパフォーマンスで通常選抜圏内だったので流石に国内通過はいけるやろ（というかいけてくれ）と思っていた．

個人的な近況報告

完全に話が横道に逸れるが，個人的な近況のお話．

自分は最近競技プログラミングをする時間が全然取れなくて，競プロ備忘録であるこのブログで週記を更新していいのか？みたいな気分になりしばらく更新見送りをしていた．（一瞬復帰したけど，競プロやってなさすぎてなんか違うなと思った）

ICPC があるということで最近は無理やり時間を作って一日に最低でも $ 1,2 $ 問は通したり，コンテストには出来るだけ出席するようにしたりした．とはいえ，Codeforeces や SRM には参加できておらず怠慢… すっかり色々なものが脱落していたり遅刻しまくったりして AtCoder のレートは現在すっかり青になってしまった．

直前期は AOJ-ICPC の難しくない問題を使って，毎日 ICPC の問題慣らしみたいなことだけはやっていた． C++ の getline 関数の扱いなんかすっかり忘れていました．あと準備と言えば，ICPC 国内のデータセットってそんな強い印象がないので近似ソルバみたいなものが効きやすいのではないかと考えて，そこらへんの準備も一応していた．

本番

直前まで研究に関するミーティングをしていた．正直かなり怒られると思っていたけど全然そんなことなかったのでむしろ怖かった．

自分は恐るべき早解き苦手人間な上にいきなり難易度の高い問題を取り組めない人間なので， A 問題は Hayato くん， C 問題は auaua くんに投げて自分は B 問題を担当．

B 問題は $ H \times W $ マス計算答えから一意に問題を求められるか？みたいな問題．読解が苦手なので困った．ちょっとすると Hayato くんが A 問題を通したと聞いたので D 問題を読んでもらうことに．上部の最左の数字が $ 0 $ と決まっているので，同一行に数字が書かれていたら推移的に決まっていくなと思い，じゃあ連結性の判定で終了ですねとなる．しかし，今回は差も重要なので心が慎重になっていた．ポテンシャル付き UnionFind を持ち出そうとするも，あまりに早く通されているので問題文をもう一度よく読むと解は最低一個はあるようなので単純な連結性判定だけでよさそうだ．（本当は Input の部分にも書いてほしかったぜ） AC．少々遅れた．

Hayato くんが D は難しそうで E が解けそうなので E を見ると言っていたので D を読む．順位表を見るに，D が一番実装と考察のバランス的にマシっぽい．設定も単純で数列があって，「非 $ 0 $ の最左 $ 3 $ つの要素から $ 1 $ ずつ取る」操作を繰り返す．数列を自由に並び替えられる時，最大の操作回数を求めよという問題．

制約が要素数，要素の大きさともに $ 50 $ 以下というかなり緩め． Hayato くんが最後に残す要素を固定すれば，嬉しそうな見た目をしているがそう簡単でもなさそうと言っていた．確かに，最後の要素から逆操作をしそうな見た目をしているが結局分岐しまくって全然うれしそうじゃないし残りソートとかしても全然できそうにない．ここまでの感じから DP っぽさを感じたがこの方向性だと DP すらきつい．

C が重い全方位木 DP と言って頑張ってくれている auaua くんと E が結構面倒くさいけど解けると言ってる Hayato くんたちに「D 難しいよ～」などとぼやきながら順位表を見ると続々と D が通されていてかなり焦る．

残すものを考える方針が厳しそうなので，一旦フラットな気持ちになって棒グラフみたいのを書いてサンプルを手で実行してみる．「一番低い棒グラフの高さで切り取って右から新しい棒グラフをもってくる」をしたときに，いやこれ「無になった上に積み重ねる」のと同義だと気づく．ちょっと考えると，適当に積み重ねて $ 3 $ つの高さの最小で良いと証明できる．不可能な積み重ね方もあるが，最適解には絡まないので無視できる．脳を無にすると添え字を $ 3 $ 本の棒グラフの高さにする三次元 DP を思いつくが bool の DP は無駄だと古事記にも書かれているので，（$ 2 $ 本の高さ - 最低の棒グラフの高さ）を添え字に持って値として最低の棒グラフの高さを値として持つことによって次元を落とすことに成功．定数倍を雑に書きすぎたせいか重いので O2 オプションを付けて実行すると速い．一個目のデータを通る．二個目のデータでなぜかランタイムエラー．メモリ系のエラーらしい．free() のサイズがおかしいと言われるがどう考えても std::vector の内部の話なので参る．ここで時間を浪費．

時系列が前後するが，E 問題が解けそうだが重いことから F を auaua くん Hayato くんの二人で話合っていて反例を見つけたり見つけなかったりしていて，つらそうだったので順位表を見ると流石に 4 完はしないとマズそうで F は厳しい問題っぽいので重そうな E をそろそろ先にやったらどうかという提案おじさんになっていた．

時系列は戻って E を通して再び F に取り掛かる Hayato くんが D のデバッグ手伝いますと言われたのでコードを投げる．遷移で境界違反してそうと言われ，そうかなあとか戯けたこと抜かしながら見ると DP 初心者みたいな境界違反をしていた．取り急ぎ直すと二個目のデータが通る．コードが変わっているので三個目のデータを通して AC．コード間違っていたのにペナにならなかったのは普段の行いかな？ｗ

この時点で順位表を見ると，F を通しているチームは非常に少なく厳しそうなので，auaua くんの C のデバッグを全員でやってみる．とはいえ，自分はとくになにもできず試して起こった現象について述べているだけの人になっていた．最終的にバグ取れたと思いきや二個目のデータで WA．

ここでコンテストが終了．割と全員が苦しんでいたが，なんとか耐えました． CE 問題はジャッジが来たら実装練習としてやろうかな． D 問題も高速化できると思うのでしっかりとやっていこうな．