合宿中のチームコンテストの振り返りをします。

チーム構成

ICPC チーム DELIAIR の torisasami, tokusakurai, sapphire15 で出ました。

参加環境

ICPC 本番を想定して、昨年度の ICPC 地区予選に向けて配布された仮想環境を使いました。また、キーボードは本番と全く同じものを torisasami が持ってきてくれたのでそれをノート PC につないで使いました。3 日間ともコンテスト開始前に全てのファイルを削除した状態から始めました。

1 日目

セットは 2022 年の韓国 ICPC 国内予選のセットらしいです。3 時間 11 問。

チーム名は sapphire15 が遊んで DELIAIR(おいしい庄内空港) になりました。

始まると私がまず環境構築をし、2 人にはとりあえず考察を任せました。環境構築では、zip の解凍や cpp ファイルをコンパイルしてサンプルを実行するシェルスクリプトを書き、その後は CLion を使って main.cpp を作ってよく使うテンプレートを書きました。初日で不慣れなこともあって、ここまでで 10 分少しかかりました。

A,C,E は既に読めて解けているようだったので、順に話を聞いて実装しました。まず E 問題は「二分探索でいいね」となって実装します (0:17 AC)。次に、A は torisasami から入力と操作を言われるがままに実装してみると WA が出ます。結論から言うと問題文の読み落としが原因でした。問題文は本番を想定して英語なので、使える錘の重さが "1, 2, 5, 10, 20, 50 and 100 g" と書いてあったのですが、"and" の後に改行が挟まっていたため "100 g" だけ浮いてるのに気づいたときには声が出てしまいました (0:23 AC)。C は ABC で最近やったことあるくねと思ってたらつい 1 ヶ月前にありました (0:27 AC)。

とりあえず序盤の簡単枠を解いたところで、F が実質的に functional graph の最長パスの頂点数を求める問題であることを sapphire15 から聞きます。実装方針は迷ったのですが、最終的にメモ化再帰のような dfs でやりました。 $n = 0$ という最悪のケースもあったようで、本番はこれに気づいていませんでしたが、幸運にも答えを 0 で初期化していたため特に問題なく通りました (0:41 AC)。

私が F を実装している間に二人は G の考察を済ませていたようで、高々 30 手でゲームが終わるので状態数は $30(a+1)(b+1)(c+1)$ になるのでメモ化再帰で間に合いそうということです。メモリが結構かさみそうなので生配列で十分な長さの配列を確保しておいた方がメモリ節約に効くかと思い、長さ $3\times 10^7$ の生配列を用意してみたら、仮想環境のメモリが少ないせいで手元で RE しました。仕方ないので unordered_map を使って実装して、提出すると WA が出ます。0 個の山に対して操作するのを許容する実装をしていたので、そこを修正すると通りました (1:10 AC)。

K は torisasami が解けていそうだったので完全に任せることにして私は sapphire15 と J を考えました。同じ x 座標の点の個数で平方分割というアイデアが出て、大と大、大と小の組み合わせは簡単にできそうです。残る小と小は苦戦しましたが、sapphire15 が反対の座標に注目するといういいアイデアを思いついて解決します。toriasami は K でペナを出していたので、一旦コードを印刷してもらってその間に J の実装を進めました。

J の実装で苦しんでいると torisasami が K の修正ができるようだったので、交代してやってもらうと通ります (1:36 AC)。J もあともう少しというところだったので、 $\log n$ を余計につけてしまった気がしますが、制約が小さいこともあってか無事に通ります (1:45 AC)。

残っている問題で通されている問題が B のみだったので、torisasami に B を読んでもらっていたのですが、難読で正しく理解できているか怪しいということを聞きました。一緒に一行ずつ読み進めていきます。彼は挿入した後のものに対して編集操作をできるのかどうかがわからなかったようですが、さすがにそんな訳はありません。それはなしという方向性で考えると、 $T$ の長さ $2M$ 以下の全文字列について $T$ との編集距離がわかれば DP できるのがわかったのですが、これは愚直にやると $O(NM^3)$ 時間かかるところ始点を固定することで $O(NM^2)$ でできます。その後は edit distance のライブラリを写経して無事 AC できました (2:21 AC)。

残るは AC なしの D,H,I 問題で、その中でも H は明らかにグロそうだったので見なかったことにして sapphire15 が D を、torisasami と私が I を考えました。I は良さそうな DP を思いついた気がして時間もなかったので適当に書き始めていたのですが、書いているうちに普通に 2 乗じゃんとなって終了しました。sapphire15 は D の良さげな方針を思いついていたようですが、どう実装に起こすのかを思い描くことができませんでした。

最終結果は 8 完で 3 位でした。解説を聞いても残りの問題は時間内に解くのは相当厳しそうな感じだったので、解けるべきところはきちんと解けたのが良かったかなと思います。一方でソロ参加の SSRS さんにはスピードで圧倒的敗北を喫し、速すぎて度肝を抜かれました。

2 日目

この日は合宿参加者の有志セットらしいです。5 時間 12 問。

チーム名は torisasami が着ていた加茂水族館の T シャツから、その別名を取って DELIAIR(クラゲドリーム館) になりました。

例によって環境構築から始まります。1 日目をふまえ、問題ごとに zip を解凍するのが面倒だったので、最初に全問題の zip をダウンロードしてからシェルスクリプトの for 文で全部一括で解凍するようにしました。

この日の序盤簡単枠は A と C のようです。A は torisasami に出された式を言われるがままに書くとちょうど答えが 1 ずれていて、実際ずれる原因もわかっていそうだったので答えから 1 を引くと通りました (0:19 AC)。続く C は sapphire15 から言われた式をそのまま書いたら通りました (0:22 AC)。

sapphire15 は鋭いことにこの時点で K に目をつけていました。話を聞くと、各頂点への直前の頂点で場合分けした上位 2 個の最短パスがあれば良さそうと思って書いてみますが、 $(a_i,b_i)$ が distinct 出ない場合に壊れることがあるのに気づき、一旦パスしました。

その間に torisasami が H の考察を済ませていて、式が降ってきたのでそれを実装することになりました。式に二項係数が入っていたので、まず階乗とその逆元テーブルを作ります。こんなんソラで書けるやろとソラ書きした modpow を少しバグらせてしまいましたが、何とか合わせます (0:49 AC)。K 問題も補グラフ bfs の要領でやればいいことに気づいたので、苦しみながらも実装すると通ります (1:13 AC)。

実装していた間に二人は B,D,E,F あたりを見ていました。mod 998244353 の数え上げがかなり多そうだったので、この辺で sapphire15 に modint のライブラリの写経をやってもらいました。torisasami は B は頑張れば行けそうという雰囲気を出していたので、私はそちらは任せて通されている F を行きました。F の初見の印象は、差分の和を「山を作ったときに、それを高さ 1 の長方形何個で作れるか」の答えに置き換えるのでは？というものでしたが、その方針で考えてもどうにもなりません。一方で、B を書いている torisasami は最後のサンプルだけ合わなくてなんで？と言っていました。印刷したコードをみて、私が「perm(n,k) が $k\lt 0$ のとき大丈夫？」と聞いてみると「それだ！」となって通ります (2:05 AC)。torisasami と協力して今度は F を括弧列に対応させて考えてみることにしました。この筋自体は良かったのですが、その後は解けたと思ったら嘘だったり、鏡像法に帰着できるかという観点でウンウンと考えていても進まなかったり、結局 1 時間以上はこの問題を考えたのですが解けずじまいになりました。

L 問題は sapphire15 から一般グラフの最大重みマッチングがあれば解けるという声が出ていましたが、持っておらず、さすがに別の賢い方法があるんだろうということでパスしました (解説で想定解が最大重みマッチングだと聞いてひっくり返りました)。I も見ましたが、そもそも 1 クエリでもわからないのでパスします。

sapphire15 は D,E に取り組んでいて、ジムニーツリーという共通概念が出てくるようなのでその定義を聞いてました。ジムニーツリーであるためには、片方の色の個数がある部分木のサイズになっていれば良さそうです。とりあえず問題の条件を満たすための必要条件を二人で考えて、「これか？」「やっぱ違うか？」を繰り返していました。途中で sapphire15 が必要十分条件を思いついたのですが、必要性・十分性ともに自明ではないように思えたので、納得できるまでかなり議論をしてもらいました。開始 3 時間過ぎくらいになんとか証明が完成したものの、それを実装する方法が見えません。オイラーツアーや BIT などを使えばできそうなのはわかったのですが、実装をやりたくなさすぎて「この必要条件ほんとにあってるの？」という気持ちになってもう一回考えたりしたのですが、やはり合っていて時間をロスしました。仕方ないので実装をします。一時間くらいやってようやくサンプルがあったので出してみるとなんと通ります (4:37 AC)。

torisasami と sapphire15 は J をやっていて、PC が空いてる間に少しずつ実験を進めていた結果、偶数のときの勝敗がわかっていて、奇数のときはどうかという感じになっていました。実験コードがバグっていたようで、直してみると縦横両方奇数のときも $(H,W) = (3,3), (3,5)$ のとき以外は規則性があることがわかり、時間もないのでこれしかないだろということでそこだけ場合分けしたコードを出します。 WA で「さすがにだめかー」と落胆します。一応コードを印刷してもらって確認していると、torisasami のコードは縦横の長さでの場合分けが if (h > y) になっていたので、私が「これ if (h > w) じゃないの？」と言うと「そうじゃん！」となって出します。AC で爆笑が起こりました (4:58 AC)。torisasami 曰く、「人生で一番科学の力を感じた」そうです。

最終結果は 7 完で 4 位でした。最後に 2 問通して追い上げましたが、中盤の空白が長すぎてだめでした。特に F 問題はラグランジュの反転公式を使うようで、この公式自体は知っていたものの実戦で使えるレベルには習得できていないということなので、自分の未熟さを感じました。SSRS さんは F を実験エスパーで式を見つけたと仰っていたのですが、そんなことができるのかと俄かに信じがたかったです。あとは実装力が課題で、E を実装する時間が長すぎたのと、解法までは見えていた D に取り組む時間がなかったのが悔やまれます。

コンテスト後は 9 完して調子に乗った The Raspberry Candies の tabr が煽りに来て、ここまで 1 勝 1 敗なので明日負けた方の atcoder ユーザーネームを勝った方が自由に変えよう (loser1, loser2, loser3 など) みたいな話が上がりました。

3 日目

最終日は JAG のオリジナルセットらしいです。5 時間 11 問。

ここまでチーム名を毎日変えていて、最終日のチーム名で迷っていました。2 日目の夕食のときに torisasami から「鶴岡市がユネスコ食文化創造都市に登録されている」という話を聞いて DELIAIR(ユネスコ食文化創造都市) に決まりました。

いつも通り環境構築から始まりますが、3 日目なのでそこそこ慣れてきました。

前から問題を見て行った torisasami は A が解けているらしいので実装を任せたら通っていました (0:11 AC)。その間に sapphire15 から B,J の話を聞き、どちらもできそうなので実装を始めます。B は頂点倍加して bfs をするだけなのですぐ通ります (0:22 AC)。J はあまり細かいところを詰めずに単純な for 文の dp の実装を始めました。しかしながら途中で閉路ができることに気づいて 01bfs で実装し直しになり、だいぶ時間をロスしてしまいました (0:47 AC)。

ここからは mod 998244353 の数え上げが複数目に入ったのでとりあえず sapphire15 に modint を写経をしてもらいました。E は確率の累積積を使って計算できるという話を torisasami から聞いて実装をしたもののサンプルが合わないので頭を抱えますが、余事象の確率を求めていたことに気づき事なきを得ます (1:11 AC)。

I は torisasami と一緒に考えていたもののわからずに苦労しましたが、torisasami が priority queue で保留しておくやつであることに気づいて通します (1:22 AC)。チームメンバー全員この手の問題が苦手な気がします。

残っている問題で一番解けそうな問題は C で、余事象で立式は出来ていてあとは高速化するだけです。畳み込みを使って計算できそうなものの意外とできず、数十分考えてようやく分割統治でできそうなことがわかりました。sapphire15 にはとりあえず畳み込みは必要になりそうなので前もって書き始めてもらっていたので少しだけ時間を節約できましたが、ライブラリ写経で結構ミスっていたので結局トントンだったかもしれません。分割統治の実装でも結構血迷ってしまって通すまでにだいぶ時間がかかってしまいました (2:48 AC)。

torisasami と sapphire15 は D 問題を考えていて、解けている雰囲気を出していたので torisasami に実装を任せるもサンプルが合いません。この時に sapphire15 が考察漏れに気づいて出直しになります。

K 問題は sapphire15 が辺の削除ができる UF (オフラインダイコネ) があればできると言っていたのですが、「不勉強のため持っておらずすみません」という形になりました。後でオフラインダイコネを勉強してみると、自力で再発明できそうな範囲だったのでライブラリを持ってないからと切り捨てるには惜しい問題だったかもしれません。

H 問題も考えていて、文字列 $t_i$ の長さが全部 1 ならば trie 木でできそうというところから始まり、 $t_i$ の長さで平方分割する方法で考えます。長さが長いものについては個別にダブリングすれば良さそうと torisasami が言うので、確かにと思って実装を始めます。しかし、実装を始めてからこの方法が全くの嘘であることに気づき、torisasami に話をするとやはりだめという結論になって、隣の SPJ がたくさん通してウハウハしているのを横目にかなり萎えました。なんとか sapphire15 が $t_i+s_1+\cdots+s_n$ に対して z-algorithm を使う解決策を思いついて一応できることがわかりました。そこからは実装を頑張るだけで、メモリも計算量もかなりカツカツで正直 2.5 s に間に合う気がしなかったのですが、何とか一発 AC できた時は本当にほっとしました (4:16 AC)。解説で TL がもし 2 s だったら落ちていたチームが 1 つあったという話があったのですが、おそらく DELIAIR だと思います (調整ありがとうございます)。

torisasami と sapphire15 は D の修正案が見えているようで、全方位木 DP でできるとのことです。全方位木 dp のライブラリを写経してもらったのですが、変に抽象化してあるものを使うよりは直に書いてしまった方が良かったかもしれません。写経にもそこそこ時間がかかり、ようやく取り掛かってみるとサンプルが合いません。どうも torisasami が普段使っているライブラリと私が用意してきたものの使い方が大きく違うらしく、そこで揉めているうちにコンテストが終了しました。この件に関しては後日 torisasami の方が勘違いしていたということで解決しました。

最終結果は 7 完で 6 位でした。SPJ に 9 完で優勝されてかなり残念でした。その他にも SSRS さんソロの Speed Star に 3 日間で全敗し、The Raspberry Candies にも最後 K を通されて負け越しするなど、3 日間で一番厳しい結果になりました。解説を聞いてみても通した問題も方針が悪かったりしたので、方針も含めた実装力不足を痛感しました。

さすがに atcoder のユーザー名を変えるのはやばいので 10 月の東京工業大学プログラミングコンテストのチーム名を自由に決められるということになりました。DELIAIR のチーム名をお楽しみに。