JAG夏合宿2024 参加記 (noya2 視点)

はじめに

こんにちは。情報理工学院　数理・計算科学系　22B　（学部 3 年）の noya2 です。

9/14~9/16 に行われたJAGが主催する夏合宿に参加しました。夏合宿は例年と同様、渋谷区のオリンピックセンターで行われます。この合宿では、主にICPCの地区予選以降のレベルを想定したコンテストセットが用意され、そういった大会を目指すあるいは大会に参加するチーム・個人が練習と交流を兼ねて合宿に参加しています。実際にひとつの会場に集まり、PC一台で並列実装なしといった本番さながらのルールでコンテストを走ることができる貴重な場でもあります。早起きの練習にもなります。

私は今年度のICPCには　21B の shobonvip さんと 23M の　Hemimor さんとチームを組ませていただき、AMATSUKAZEというチームで参加しています。7/5 に行われた国内予選を　1 位で通過し、年末に横浜で行われるアジア地区予選への出場権を手にしました。横浜大会の良い練習になるのでチームで夏合宿に参加したいと思っていたのですが、昨年度はもっと強いチームにいた Hemimor さんは昨年度の世界大会に出場しており、なんとその大会の日程が夏合宿の日程と被ってしまったのです。もちろん Hemimor さんには世界大会の方に出てもらうので、我々のチームとしては夏合宿にフル参加はできず、 2 人チームで参加することを考えていました。そんなことをX（旧twitter）で嘆いたところ、大阪大学のチーム kotamanegi_world の KowerKoint さんに、同じような事情で 1 人参加となってしまったので一緒にチームを組まないか、とお誘いをいただきました！嬉しい限りです。夏合宿には AMATSUKAZE_world(noya2, shobonvip, KowerKoint) というチームで参加することになりました。

夏合宿では、1日1つのコンテストセットを走ります。ここからは問題内容に踏み込んでいきます。

day1 韓国ICPC国内予選(3h)

A~L の　12 問のセットでした。 ABDEHIJKL の 9 完で 2 位でした。

初動がかなり悪いです。自分がテンプレートを書き、shobon さんには前から、KowerKoint さんには後ろから見てもらうという動きだったのですが、初手で KowerKoint さんが（結果的には難しかった）Lに挑み、TLEで 2 ペナをつけてしまいます。次手で shobon さんが（結果的には難しかった）Dに挑み、しばらく立って誤読が発覚して戻ってきます。自分は HJ の解法を出していましたが、LDが実装中だったので後回しにしてしまいました。結果的には簡単枠だった　HIJK に取り組むのが 20 分程度遅れてしまう事態になりました。

ここから立て直していきます。　noya2 が J を実装します。矩形和が $10$ になる矩形の個数を数えますが、書かれている値が　 $1$ 以上なので、調べる矩形の個数は十分少ないです。全探索をすると通ります。

KowerKoint さんが　I を実装します。最も簡単な枠でした。問題文を読むと、実装するべきことが書かれており、実装をすると通ります。

shobon さんが K を実装します。LISでの最小個数被覆はLDSです（Dilworthの定理）。勘違いで 1 ペナつけましたが、通ります。

noya2 が H を実装します。真ん中を固定します。　 $i < j, p_{i} < p_{j}, q_{i} < q_{j}$ なる組 $(i, j)$ の数え上げだと思ったら、 $i < j$ は不要でした。 shobon さんに BIT をタイピングしてもらいます。あとは適当にやると通ります。

noya2 ではない誰か（忘れた）が E を実装します。多少の算数とDPをすると通ります。

ここから noya2 は KowerKoint さんから話を聞き、L が幾何だったので、これに取り組みます。TLEを回避する解法はすぐに思いついた（というより知っていた）ので、詳細を詰めます。 KowerKoint さんの実装を引き継げないのは痛手でしたが、やむなしです。辺の真下にある台形領域にいくつ点があるかを事前に計算しておく方針です。境界の処理が面倒で、半開区間にしたり三角形を向き付けにしたり、いろいろ迷走した結果、場合分けに走ることにしました。ここまでで 30 分くらいかけてしまいましたが、B と交代しながら実装をしていました。

KowerKoint さんは天才で、やばそうな見た目の B の解法を生やし、実装を始めていました。 L とお互い細かいところを詰めながら、実装を交代しつつ、どちらも通りました。

KowerKoint さんは天才で（2）、D の鍵となる考察を思いついていました。自分は全く手をつけていないのですが、一緒に考えてもらっていた shobon さんが実装できそうだということで、書き始めてもらいました。実はここから noya2 は何もしていません。順位表が凍結した直後に D が通りました。FA かつ unique AC です。すごい！

shobon さんに D の実装をしてもらっている間、 KowerKoint さんには A の実装を詰めてもらいます。自分はこの問題を見たとき過半数を発見するアルゴリズムを思い浮かべていたのですが、この問題は最頻値クエリでした。もともと制約メタ読みで Mo で $O (Q N lo g N)$ 時間だと思っていたので、これを通す定数倍に気をつけた実装に集中します。 D が通ったあと A の実装もしばらくすると終わりますが、TLE が返ってきます。Mo のバケットサイズを少し改善したものを投げますが、それもダメでした。残り 10 分程度でしたが、ここで　shobon さんが　std::priority_queue を $N$ 本使ったタイブレーク処理を segtree $1$ 本で行うゴリ押し解法を実装し始めました。計算量のオーダーでは改善していませんが、 segtree の $lo g$ が軽いことを信じます。KowerKoint さんの実装を一部を書き換える形で、実装が終わりました。時間もないので一度提出したあと、手元でランダムケースを回すと、 TL 1.2 sec には間に合っていません。諦め気味に返ってきた結果を見ると、なんと AC でした。すごーい。

ここまでで 9 完ですが、終了直前に C を見せてもらうと、ハノイの塔の変種で、前提知識はおそらく十分揃っていたので、もっと少し早く手をつけていれば C も追加で通せたかもしれないと反省しました。

実装キューを消化し切ったのは偉いです。全員、そこそこバグを埋め込む傾向にあるみたいですが、PCをそこまで占有することなく、印刷デバッグで片付けられたのが良かったと思います。

1 位の Screenwalkers にはペナ差ですが遠く及ばない結果になってしまいました。初動が悪いと完数で差をつける覚悟が必要なため、精神衛生上よくないです。+1 完はあり得るセットだと思っていたので、悔しいです。

day2 有志セット(5h)

A~N の　14 問のセットでした。 ABCEFGHJKMN の 11 完で 2 位でした。

noya2 がテンプレートを書き終わったあと真ん中の G を見ると、探索範囲を少なくするいつものが置いてあったので実装すると WA が返ってきます。なんと $(1, 3, 3)$ を忘れていました、おい！修正して直すと、FAでした。多少の救われと 20分のペナをもらいます。

すぐに A も解法が出たので、 shobon さんに通してもらいます。

K は noya2 がクエリがオフラインであることを利用して平面走査を考えていましたが、天才 shobon さんが $⌊ \frac{L - 1}{x} ⌋ = ⌊ \frac{R}{x} ⌋$ という式を出してくれて、そのまま実装まで行ってもらいました。こういう問題は商列挙か調和級数だと勝手に思っていますが、この問題も例に漏れず商列挙でした。

実はこの辺りで noya2 が M の嘘解法が生やしており、最大値とそれ以外に分ければ良いですねと言って shobon さんに segtree を書いてもらい、実装し、何事もなかったかのように WA をもらっていました。手元ですぐに反例 $(3, 5, 6)$ を挙げられたのはまだ良かったです。

F は noya2 が適当なエスパーや部分木内の $1$ の個数の変化に注目するなどしていましたが、天才 shobon さんが変化がキャンセルし合うから直接の子の $1$ の個数に注目すればいいという考察をもらい、そのまま実装までお願いしました。実装自体は軽く、すぐに通りました。（自分が何もしておらず）

I は KowerKoint さんが読解に苦戦していましたが、解法としてはまともなものが思いついたようなので、実装してもらいました。閉路の積が平方数であることから、適当な始点を決めてポテンシャルを取れば良いパートやハッシュを使うパートは高度典型だなあと思っていました。TLEで 1 ペナつけてしまいましたが、なんとか通りました。

E は構文解析like な数え上げで、　shobon さんが実装しました。 I を実装中の KowerKoint さんから計算量改善を聞き、かなり重そうですが、やればできるとは思うと　shobon さんに言ってもらったので、完数差がつけられる問題だと思うので早めに手をつけて欲しいとお願いしました。

EM が並行して代わり代わり実装デバッグを行っている時間もありました。E がかなり早いタイミングで通ったのは大きかったです。DPの遷移が大変ことになっていたので、ノーペナで通ったのもすごいです。FAでした。shobon さんがすごすぎる。

KowerKoint さんに M の考察を変わってもらっていたところ、 $2$ 番目の最大値まで持てば良いですと言われ、正しそうとなったので、 segtree の op を修正しました。普通に頭がバグっておりもう 1 ペナつけてしまいましたが、さすがに正しすぎる　op を書き切り、今度こそ通りました。

5h は長いです。まだまだあります。

N は早い段階で　KowerKoint さんが出来そうと言ってくれていましたが、惜しいところで止まっていました。shobon さんと相談していると、計算量がまともな解法が生えたらしいので、実装してもらいました。 shobon さんが実装を始めると言うときはいつも頼もしいです。まもなく通りました。

noya2 は　B の問題内容を聞き、なんとかなる問題であることを確信していたので、そこそこ方針を詰めたあと、実装をしていました。典型事実に気づかず、かなり実直で面倒な方針をとってしまい、実装も大変なことになってしまいました。本当にずっと実装しては印刷デバッグをし、実装方針を練り直し、完全に沼っていました。今思えば、実装ではなくて考察の方を練り直すべきでした。

難しそうに見えていた J ですが、 KowerKoint さんがよく考えると結構簡単だったらしく、気づいたら通っていました。自分は B が大炎上している最中です。

Bはあと実装するだけ（ほんとか？）になっていたので、shobon さんから C の考察を聞きました。これも商列挙の形で、関数の引数の形が限定されるいつものやつでした。計算量が $3/4$ 乗になるのか不安といわれましたが、そうだと言っておきました（この手の問題は典型で、形としても同じ問題をCFで見たことがあるし、本番中に通した）。自分は B が大炎上している最中なので、そこそこ他人事だったかもしれません。

Bの実装がやっと完成し、これで通らなかったら本当に泣いちゃうよ〜とか言いながら出しました。2hくらい実装しているのではないでしょうか。途中で2,3問の実装と交代していた気がします。恐る恐る結果を見ると AC でした。助かりました。

そのままの勢いで shobon さんの C の実装も終わり、そのまま通りました。

残り 40 分ですが、考えるなら L だろうと思い、ようやくPCも空いたので shobon さんが実験を書きました。するとびっくり！カタラン数が現れます。さらに、条件を満たす数列を眺めると、LDS $\leq 2$ の条件も見えてきます。カタラン数と　321-avoiding との対応関係は見たことがあったので、確信しました。しかし、肝心の順列とカタラン数関係のものとの全単射を知りません。考えても出てきません。noya2 は括弧列との対応を取ろうとしていましたが、うまくいきませんでした。終了後に解説を聞くと、グリッド上の経路を考えるとうまくいくようです。

ここまで 11 完で終わりです。またしても 2 位で、 Screenwalkers に負けてしまいました。今度は完数差もつけられてしまいました。ペナ差まで付けられているので、大負けであることがわかります。実力差が明確に現れた結果となりました。

自分の反省するべき点はやはり B で考察を練り直さなかったことです。括弧の個数を揃える必要がありましたが、それを含めてもモノイドになることに気づいていませんでした。

day3 JAGセット(5h)

A~K の 11 問のセットでした。 ABDFGIK の 7 完で 7 位でした。

AB が簡単だという事前情報があったので、shobon さんに A を、 KowerKoint さんに B をお願いしました。どちらもそこそこの時間で通りました。

I を noya2 が実装します。やることはよくある木DPです。

PCが開いたので、実験が早そうなDを shobon さんにやってもらいます。グッと睨むと法則が見えてくるらしいので、実装して通りました。

KowerKoint さんに K を実装してもらいます。典型的なマージテクの問題ですが、やることが多いです。実装はそこそこの時間で終わったのですが、TLEを連発してしまいます。最終的にはマージテクのマージ部分で順番を間違えていたらしく、もったいなかったです。6 ペナもつけてしまいましたが、なんとか通って良かったです。

shobon さんは F をやっていました。多倍長整数が必要ですが、実装自体は愚直なもので大丈夫だということは相談して確認をとっていました。しかし長い間実装が合いません。どうやら手動では無意識に考えられていた挙動を実装に反映できていなかったらしいです。なんとか通りました。

自分は I を終えたあと、そこそこの時間を CE にかけていました。C の本質考察がわかり、かなり進んだつもりになっていました。Eは完全マッチングを取り続けるゲームに見えていました。しかし、Gが解かれたので先にそちらを見にいくことにしました。 $2000$ 回なら自明ですが、 $1000$ 回は必要です。問題は文字列の終わりがわからないことですが、これを確認するには追加で $1$ 回だけ質問すればよく、しかも頻繁には必要ありません。平方分割の要領で $32$ 回毎に終わったかどうかを判定する方針で考え始めました。左右で行うと　 $32 \times 2$ 回終わったかを聞き、戻ってくるのに $32 \times 2$ 回聞くので、　 $128$ 回余分に聞いてしまいます。ここのパートで実は左右に伸ばす分は合計で　 $32$ 回だと勘違いして実装をしてしまい、WAをもらいます。実装を睨むと、実装に間違いはなく、考察が怪しくてクエリ回数がオーバーしていることを疑うことになりました。とりあえず平方ではないので計算をし直し、 $23$ 回に $1$ 回質問することにしましたが、これでもダメでした。この改善より先に、戻ってくるパートでは二分探索をすればいいというのを shobon さんに聞いていたのですが、これをもう少し早くに実装する決断をするべきでした。最終的には二分探索に切り替えて通しました。

この時点で　2h くらい残っていますが、ここから AC は出ません。そんな〜

CEが解けそうなつもりになっており、KowerKoint さんはHが解けたと言っているので、いろいろなライブラリを shobon さんにタイピングしてもらっていると、どれもいらないことが発覚し、少し後にそもそも解法が間違っていることまで発覚し、考え直すことにします。問題内容を聞くと、01onTree の形そのままであることに気づいたので、すぐにその話をします。自分の頭はバグっており、相手にうまく伝わらないまま反例らしきものをたくさん投げてもらって、やっぱり違いますねとなってしまいました。解説を聞くと本当に最初に思いついた通りの解法が紹介されており、終始頭の中は？でいっぱいでした。悔しいですね。その後、いろいろ説明してもらっている間に、どんどんと思考が汚染されていき、マージテクのマージ部分をすればいいという嘘に合意してしまって、treap でできるので shobon さんに粘ってもらいました。実装が終わってもバグっており、なんと、そこからそのままバグが治らずにコンテストは終了してしまいます。

途中で KowerKoint さんと shobon さんに C　の考察を聞いてもらって、確かに出来そうだとなったのですが、DPを思いつくのに時間がかかったのと、計算量と遷移順が怪しい気がして、どれも中途半端な考察を残して最終的に捨ててしまいました。その時点で C は他チームに通されており、可能枠であることはわかっていたのに。

E についても、とりあえず回数無視なら出来ますね、とか、結局 $M = 2$ に帰着しますね、までは思いついても良かったはずのよくある考察でしたが、そこにすら辿り着かず厳しい気持ちです。

7 完の中ではペナをつけ過ぎており、そもそも 8 完したチームが 4　つもあるので、大負けです。負けているときの雰囲気がずっと漂っており、打破しきらず終わってしまいました。実装が終わらない、バグが取れない、ならまだ良いのですが、その実装が完成してもそもそもの考察が間違っているということに終了直前に気づいたので、かなり最悪の展開です。本当にやばい。

H は 01onTree の正当性を認めれば、実装はかなり重いですが十分可能な範囲だったので、unique AC のチャンスを逃したのは本当に悔しいです。本番じゃなくて良かった。

コンテスト以外

談話室で主に東大のメンバーが将棋を指していたので観戦していました。day2 の夜は自分も指してみたい気持ちになったのですが、あまりにも初心者なのでとりあえず 8 枚落ちでやってもらいました（このハンデでも初心者は負けてしまいがちらしい、恐ろしい）。見るからに厳しい手を何度か打たれましたが、物量で押していけると思ったので、相手の攻めを無視してこちらも攻めていると勝つことができました。その後 6 枚落ちでも対戦してもらったところ、負けました。

おわりに

今年も夏合宿がとても充実したものになりました。JAGスタッフのみなさん、本当にありがとうございました。

それから、東大のメンバーや有志セットの準備陣、JAGセットの準備陣とたくさん話すことができました。とても楽しかったです。横浜大会までのモチベーションがかなり高まりました。ありがとうございました。