チーム
今年も suzukaze_Aobayama です．
- karinohito: 数学，発想ゲー担当
- milkcoffee: 今年加入．最適化，DP，大量の作問ストックで問題を爆破する担当
- sotanishy: データ構造，グラフ，幾何，構文解析，重実装，知識ゲー担当
去年のチームメイトだったむげんさんは今年はコーチとして参加してくれます．参加登録とか大変そうでしたがありがとうございました．
目標
国内10位
正直アジア行ければ何でもいい．
本番前
去年は国内前にACPCやKUPCなど有志コンが多くあったのでチーム練の機会はたくさんあったが，今年はあまりそういうのがないので，自主的にバチャをたくさん走る．本番1ヶ月ほど前から毎週末集まり，Codeforcesのgymにある海外regionalを中心にバチャをやった．練習では非常にうまく行っていたと思う．チーム戦がかなり上手にできていた感じがある．やっぱりチームメイトの得意分野がはっきりしているとやりやすい．
模擬国内に出る．ABCDEG6完，全体8位（guest除く），学内2位．序盤早解きで時間を稼いで，高難易度をじっくり時間をかけて通すという理想的なムーブができたと思う．
本番一週間前に模擬国内2019を解いたが，これも7位相当といい感じだった．
本番も，練習通りのパフォーマンスが出せれば確実に上位を狙えると思っていた．
当日は，14:30に参加場所に集合する．今年も顧問の先生に部屋をいくつか用意していただいた．suzukaze_Aobayamaは去年と同じ部屋を得る．むげんさんが来てくれていたのでちょっと話した．去年みたいな戦いができればいいねみたいな話をした気がする．
リハーサルをやる．僕は幾何担当なので鎖中経路をやる．昔解いたことがあるのでリハーサル終了の15:00までに間に合うだろうと思っていたが，バグらせまくってサンプルがあったのが終了2分前．提出するとWAが帰ってきて終了．よく見たらサンプルあっていなかった．
コンテスト前の微妙な時間を埋めるために，AOJ-ICPC 100~300点の問題を適当に集めて40分位の軽めのバチャをやる．本当に軽めのつもりだったが，点数が低いとはいえ実装が重いやつばかりなので大変だった．まあいい感じの時間つぶしにはなった．
バチャが終わって，本番30分前．流石に緊張してくる．この時間の記憶があまりない．
本番
始まる．今年はちゃんと定刻通りに開始．
A
milkcoffeeさんが4:38でAC．
B
仮の人くんが18:24でAC．
先にCが通っていたのでBが通った時点で3完5位．最序盤の早解きに成功し一安心．また去年みたいな流れになることを期待する．
C
僕がみる．雑に言うと，正整数 \(n,m\)が与えられるので，\(k\)を勝手に選んで \(\sum_{i=1}^k a_i=n,\,\sum_{i=1}^{k+1} b_i=m,\,a_i,b_i>0\)のもとで\(\sum_i a_i^2 - \sum_i b_i^2 \)を最大化する問題．\(\sum_i a_i^2\)の方は大きくしたいのでできるだけ一つに集めるのが良くて，\(\sum_i b_i^2\)の方は小さくしたいのでできるだけ均等に分けるのが良いというのはよくある話．じゃあ\(k=1\)で良いんじゃないかと思って実装してサンプルに対して走らせるとだいたい合うけど微妙にずれる．え，じゃあ無理です，と言いそうになるが，よく見ると \(n,m<10^6\) なので\(k\)が全探索できる．本当にこれだけでいいのか不安だが震える手で提出するとなんと通る．去年や一昨年はCがひたすら面倒だったので，こんなにすんなりCが解けるのは初めてだ．10:05でAC．
D
D, Eを得意分野に応じて割り振る作戦だった．Dが数え上げだと聞いた瞬間仮の人君に投げて僕とmilkcoffeeさんはEに向かう．仮の人君が問題を見てすぐ「これは解けます」と言っていたので託す．
1時間ほど僕はE, Fを見ていたが，Dの音沙汰がないので見に行くと難航していたらしい．大体の方針は立っているが微妙に合わない．僕も問題を見て考えてみると，番号の小さい人間から順に見ていって使う/使わないを確定させていく解法を思いつく．ただこれは\(O(n)\)で，\(n < 10^4\)という制約を全く使い切っていないので正しい気がしない．でもサンプルがあってしまったので一応投げてみる．落ちる．よく見ると，サンプルが合うことが不思議なレベルのミスを犯していた．直して再びサンプルを合わせ，出そうとするが，仮の人君がhackケースを送ってくる．走らせてみると落ちる．出さなくてよかった......．
これはかなり沼になりそうな予感がしたが，仮の人くんの方で実装していたやつがいい感じになったらしく，提出したら通った．1:59:37．
3完してからまったく進展がなく焦りも出てきて苦しいときだったので通してくれて本当にありがとう，という気持ち．
E
Cを解いてすぐ僕とmilkcoffeeさんがEを一緒に見る．構築問題．\(n \times m\)のグリッドの各マスに +1, -1を書き込んでいき，指定された行/列が括弧列として成り立つようにし，それ以外の行は成り立たないようにする．ARCにありそうな見た目．
しばらく考えてみたが全く方針が立たない．データ構造やフローには見えないので，何らかの天才をする必要がありそう．ただそういうのは僕はあまり得意ではないのでちょっと嫌な気持ちになっていると，milkcoffeeさんが天才をして，「端だけ適当に埋めて中は市松模様で埋める」という方針が立つ．端を適当に埋める，というのが可能かどうかは置いておいて，かなり筋が良さそうだし，それができなかったらもう解けません，といいたくなるくらい良い性質が見つからなかったので，しばらくその筋で考える．
1の行/列の始まりと終わりは自明に埋まる．四隅は適当に場合分けすれば埋められる．残りは，+を貪欲に左/上に詰めていけばいいのではないか．ヤバそうなケースがありそうな気はするが，もうちょっとちゃんと考えるとこのようにすれば0の行/列が括弧列として必ず壊れるようにできることが示せた．考えれば考えるほど正しい．実装をmilkcoffeeさんに託して僕はFを見に行く．この時点で開始１時間も経っていなかったんじゃないか．
しばらくFを考えたりDを見に行ったりしていてEに戻ってくる．実装が炎上していたらしい．僕の中では実装のイメージができていたので並列で実装してみる．\(n,m\)を間違えそうなので気をつけて丁寧に実装する．サンプルが合うので投げる．落ちる．よく見たら\(n,m\)を一箇所間違えていた．直す．このとき流石に学習してすぐには出さず，ちゃんと自作ケースを合わせたり，小さめのテストケースを目で見ておかしいのがないか探す．おかしいのが大量に見つかりました．四隅の場合分けを雑にやっていたのでおとなしく16通り場合分けする（実際に書いてみると本当に考えなければいけないのは7通りとかになったのでそこまでひどくはなかった）．今度こそサンプルや自作ケースなどがあったので投げる．また落ちる．途中milkcoffeeさんの方でも何回かサンプルがあったらしいので何回か投げたが全部落ちる．
解法の大筋が正しいことは確信していたのでめちゃくちゃ細かいところで考察漏れがあるか実装ミスだと思うのだが全然わからない．
思い返せば，僕のコードの出力とmilkcoffeeさんのコードの出力を突き合わせてdiffを見るとかやってみればよかったのかも知れないが，あまり冷静になれておらず最後の方は微調整して投げるを繰り返してペナを重ねるだけになってしまった．
結局通らなかった．
F, G, H
Fは，Eと行ったり来たりしながらちまちま考えていたが手がかりが全くつかめなかった．Dを解いた後仮の人くんもちょっと見たらしいがやっぱりわからず．
Gは一瞬目を通したが流石にE, Fを先に通す方が堅実かと思い考えていない．Hは見ていない．
気づいたら終わってた．
本番後
結果は26位，学内2位，アジア進出
めっちゃ冷えた感覚だったので，僕らの上に Aobayama_dropout 以外の東北大のチームがいませんようにと祈りながら順位表を上から見ていったが，僕らが学内2位で本当に安心した．そのまま下にスクロールしていったら同じ4完に東北大があと2チームいることを知って驚愕した．本当に危なかった．Dを通してくれて心から感謝．
隣の部屋で出ていたSeiryo_blockerの人々と焼き鳥を食べたりダーツをしたりして遊んだ．milkcoffeeさんがダーツうますぎ．
振り返り
Cまでは順調だった．D, Eも，問題の担当は最適解だったと思うんだけど，コンテスト中の立ち回りは反省点が残る．
あまり気持ちの良い通過の仕方ではないが，通過できたことには変わりない．コンテスト終了直後は悔しい気持ちが強かったが，1日経つとまたアジアに行けることが素直に嬉しいと感じられるようになった．去年の国内・アジアや模擬国内の成績だけ見ると，勝って当然のチームであるのかも知れないけれど，不安が強かったし，だからこそ本気で準備してきたので通過して本当にホッとした．
アジアは橙橙黄で出たい．チームメイト，よろしくおねがいします．
今年のアジアはオンサイトでできるといいですね．
