クマーの競プロ精進日記

AtCoder赤とICPC World Final目指して頑張ります．競プロ自戦記、アルゴリズムなどについて

5 年間の ICPC を終えて

計算機は 1 台しか与えず，紙に印刷してきたライブラリを写経させる．初めて ICPC の存在を知ったとき，なんと前時代的で面倒臭いコンテストなのだろうと思った．

私は大学 1 年の 4 月に競技プログラミングの存在を AtCoder から知った．ICPC には SPJ という同一のチームで，メンバーを変更することなく学部 1 年から修士 1 年までの 5 年間参加し続けた．メンバーの 2 人とはもう 5 年近くの付き合いということになる．チームの Discord には競技プログラミングのことだけでなく，受けている授業や進路，趣味のことなど雑多なことをいつも書き込み合っていた．何度か 3 人で遊びにも行き，お互いの性格や特徴についても理解するところが増えた．

学部 4 年くらいの頃から，特に学科が違う nok0 とは関わる機会が減っていた．練習も都合が合わなくて思うようにできなくなった．3 人とも B2/B3 のときほどの ICPC に対する情熱を失ってきたところでラストイヤーが来てしまった．さすがに国内予選は経験の差が生きて貫禄勝ちできたが，結局 World Final に行けるほどのチームの力を育てることができないまま横浜で 5 年間のチャンスは終わってしまった．おそらくチームワークという点ではこれ以上伸ばしようがないので，あとは各個人の地力がもっと必要だったのだと思う．もっと自分が情熱を持って競プロに取り組んでいたら，と後悔したりもする．

ICPC は変なコンテストであり，ずっとその形式について文句を言ったりもしていたのだが，それでも常に自分の大学生活の意識の中心にあったことは間違いないと思う．私の同期 (2001-2002 生まれ) は東大のプレイヤーが極端に少ないのだが，その中でチームメイトの 2 人に出会えて，近い実力のまま 5 年間やり通せたのは本当に良かったと思っている．2 人とも，本当にありがとう．この経験が将来直接自分の人生に役立つかはよく分からないが，確かに私の思い出として心の中に残り続けるだろう．ここまで一つの競技に本気で熱中したのは将棋，天鳳に続いて 3 つ目だ．

ICPC 戦績

過去の戦歴語り．普段だったら誰も聞いちゃくれないんだけど最後なんでここでやります．5 年やってきた特権ってことで，一番気持ちいいやつ，やらせてください．

2020 (B1)

  • 国内: 23 位

kumakumatime.hateblo.jp

(記事の口調や内容から若さを感じる．この頃は競プロが楽しくって仕方なかったんだろうな)

  • 横浜: -

初参加．このときはまだ某感染症の影響で完全オンラインで，3 人ともお互いの顔も知らずに通話でやっていた．このときはライブラリもネット検索も同時実装もありだった気がするので時代を感じる．

国内で ABCEF を解いた．今見ると E や F より明らかに簡単な D が最後までできなかった．それさえ通っていれば横浜進出だったので初回にしては惜しい結果だった．

2021 (B2)

(記事から哀愁が感じられる)

  • 横浜: -

トラウマ回．この記事を見返す度に今でも胸がギュッとする．C 問題の全方位木 DP の実装が遅れたり，D で 2 ペナを払ったりしたせいで 10 位と 10 分差で敗北．ICPC のペナの重さを身をもって思い知った．この回からチームの協力態勢について意識改革を行うようになった．

2022 (B3)

kumakumatime.hateblo.jp

まず序盤でリードを奪い，その後腰を据えて正しく後半の問題を実装する．国内予選での最強の方針に気付いた回．通過の瞬間は嬉しすぎて天にも昇る気持ちだった．横浜では経験の少なさが出てしまって惨敗．自身の不甲斐なさを感じたまま終わった．

2023 (B4)

国内も横浜もかなりうまく行った．両方で DELIAIR に勝てたのが嬉しい．ラズキャンには横浜で借りを返されてしまったが．

2024 (M1)

今回．国内予選は少しヒヤリとしたが概ね OK．企業賞の叙々苑がおいしかった．横浜ではせめて去年より良い順位を取りたかったな．

ICPC 雑感

ICPC について色々思っていることにを脈絡もなく書いていく．

ルールの面白さ

まず思うのは，競プロのチーム戦そのものがとても面白いということ．3 人で相談ありというこの形式を考えた人は本当にすごいと思う．さらに ICPC ルールは利用できる環境に強い制限があり，これがまた面白い．当初このルールには不満もあったのだが，やっていくうちにこの制限こそが独特の戦略性を生み出していて面白いと考えるようになった．1 台しかない計算機を何に用いるのかの判断をするにはチーム間での意思疎通が頻繁に必要になってくるため，各自で問題を解くだけではない，チーム競技としての面白さがあると思う．チームでの連携がうまく取れないうちはこのルールは不自由でつまらないと思うかもしれない．

国内予選の謎システム

細かい話になるが，国内予選で頑なにオンラインジャッジを使わないのはなぜなのだろうか．実行環境の差で有利不利が生まれて良くないと思うのだが…サーバーのアクセス負荷とかが問題になっていたりするのだろうか．

JAG と ICPC ジャッジチーム

ボランティアかそれに近い組織なのにあの問題を用意するのはすごい．

東大の環境

最近は東大の下の世代が全然育たないなーということをよく思っている．東大の層は年々薄くなっており，今年の国内予選では 10 位以内に我々のチームしか入っておらず，正直大丈夫かと思った．中高時代に OI で活躍していた人が大学以降で競プロから離れる例もよく見かける．東大内で競プロをする集まりがないせいか，周りでチームメイトが見つけられずにやめた人も知っている．他大学のようにサークルなどが存在していたほうが育成の観点では良いのかもしれない．来年は我々と双子がいなくなるわけだが…東大内でどこが覇権を握るのか全く予想がつかない．

競プロの今後

競プロというコンテンツ自体がいつまで続くのだろうと考えることも多い．生成 AI が AGC を解けるようになるのは当分先だろうとは思いつつも，ABC や ARC Div. 2 の前半部分を簡単に解いてしまう存在ができるというのは界隈にとって良いことなのだろうか？これまで人間が思考を介さずとも使える全探索などの基本的なアルゴリズムの範囲が広がって，様々なテクニックを駆使する高度な問題が増えたら，それは本当に面白い変化だと思うけど．そんな難しい問題って簡単に作れないからねえ．

またヒューリスティックばかりが人気になってアルゴの形式が廃れるのではという心配もある．ヒューリスティック部門の方が業務との親和性が大きいことはなんとなく想像できるし，実際 AHC のスポンサーの付き方などを見てもそうなのだろうと思っているが，それでも自分は美しい正解のあるアルゴ部門のほうが好きだし，簡単になくなって欲しくないという気持ちがある．存続のために自分に何ができるのかというと難しいが，また AtCoder に問題を提供したり，UTPC を開いたりすることくらいだろうか．

今後競プロ (のアルゴ部門) が廃れたとして，今まで自分がやっていたことはどのように解釈されるのだろうか，ということを時々ふっと思う．今でさえ競プロやってますって人に説明するの大変なのにね．

ICPC も終わったし，これからは競プロへの向き合い方がもっとのんびりしたものになると思う．遅い時間のコドフォとかに出たりはもうしないだろう．AtCoder は赤になるか，それを諦めるまでは続けるつもり．競プロに続く，次に熱中できるゲームもそのうち見つけられたらいいな．

これからも，また Writer とかで見かけることがあるかもしれませんが，そのときはよろしくお願いします．

ICPC 攻略法：アジア地区横浜大会編

意外と書くことがない．

  • UC をたくさんやろう
  • オフライン練習も大事

はじめに

国内予選編の続きです．用語などもその記事と共通．

2024 年度のルール

詳細については公式ページを参照のこと．ここでは特に重要な点について述べる．

  • 問題数: 12 問
  • 制限時間: 5 時間
  • チーム人数: 3 人
  • ライブラリ: 紙媒体のみ可
  • インターネット: 使用不可
  • 全問同配点
  • 同点の場合，各問題に書けた時間の合計が小さい方が上位
  • 誤答 1 回につきペナルティ 20 分

昨年度からの変更点

  • 問題数増加 (11 \to 12)

練習

Universal Cup (UC) の登場により 5h ルールを練習できるセットがかなり増えた．Codeforces の Gym も使える (UC で出たコンテストと同じ内容だったりもする)．できるだけ英語の解説や順位表があるものを選んでやるのが良い．

ライブラリ

(2024/12/27 追記)

  • 紙媒体しか持ち込めないため，ライブラリは写経に適したものを持って行く必要がある
    • kactl の pdf を印刷して持って行くのが定番
      • ICPC で写経することを前提としており，タイプ量の少なさと性能の良さの両方を考慮した実装となっている
      • マイナー知識も含め色々書いてあるので ICPC 関係なく便利．普通に知らないことが書いてあって勉強になる
      • github を見る限り 2024 年現在も更新されていそう
      • 余白が狭いため印刷時に端が見切れやすい
      • ぎゅうぎゅう詰めなのでフォントが小さい
      • 多種多様なアルゴリズムに対応しており，今までなくて困ったものは多項式演算 (逆元や exp など) くらいだろうか (FFT くらいならある)
      • 実装量削減のためか，インターフェースに癖があるものもある．基本的に pdf をよく読めば分かるようになっているが，以下の項目は事前に利用法を確認しておきたい
        • LazySegTree (抽象化されてない & ポインタで持つ実装)
        • LineContainer
        • MoQueries
        • hopcroftKarp/DFSMatching
        • SCC
        • 2sat
        • EulerWalk
        • MaximalCliques
        • HLD (可換しかない)
        • ConvexHull (凸包の辺上の点を除去してしまう)
    • その他にも過去の強豪チームなどが公開しているものがいくつかある

(追記終わり)

使用環境

  • 本番環境を再現した iso ファイルが事前に配布される
    • VirtualBox などで仮想環境を作成することで本番の環境を再現することができる
    • 各種アップデートにより iso ファイルが使えなくなることがあるので，その場合は運営に報告して直してもらう
  • OS, キーボード (US)，エディタに慣れておく
    • 本番とほぼ同じ種類のキーボードは Amazon で数千円で買える．コンテストの賞品として貰ったアマギフで買おう！ (ABC は抽選になっちゃったけど)
  • エディタは CLion が無難
    • VSCode とほとんど同じである VSCodium というエディタはある．しかしインターネット環境がないため拡張機能などが入れられず，補完やフォーマッティングが利かないため不便 (追記: 補完はあるらしい．フォーマッタについては不明)
    • コーダー全員が慣れているなら Vim, Emacs などでも良いかも
    • ICPC で提供されるエディタの中では，CLion が補完やフォーマッティングの機能を唯一持っている *1
    • CLion 自体は有料のエディタだが，それを提供している JetBrains 社が ICPC のスポンサーであるおかげで，大会本番では特別なライセンスを用いて利用することができる
      • JetBrains 社がスポンサーを降りた場合は…どうするか考えたくもない．いつもお世話になっております
    • 学生であれば 1 年間無料で JetBrains 社製品を使えるライセンスを入手でき，またそれは学生である限り更新することができる．練習の際にはそれを用いればよい
  • CLion のショートカットキーは独特なものが多く，慣れていないと苦労する
    • 使用頻度が高いため覚える or 再設定した方が良いのは以下の操作
      • ファイルを開く (Shift Shift or Ctrl + Shift + N)
      • ターミナルを開く (Alt + F12)
      • 設定を開く (Ctrl + Alt + S)
      • 行のコピー (Ctrl + D)
      • 下に改行 (Shift + Enter)
      • 行を上下に動かす (Ctrl + Shift + ↑/↓)
  • セーブは自動
  • セーブ時に自動でフォーマットする設定にする

リハーサル

  • 各種の仕様確認は PC に触る人間全員でやる
    • 時間にはかなり余裕があるのでゆっくりやればよい
  • 問題名やダウンロードするサンプル入力ファイルの名前は "A" ではなく "trialA" などとなっている
  • 順位システムについて確認しておく
    • CE を提出するとペナが付くか？ \to 2024 年度は順位表に何も反映されなかった (未提出扱い)
    • 順位表凍結後に CE 提出をすると表示はどのようになるか？ \to 2024 年度は提出数が 1 増加して表示されていた
      • 2024 年度での挙動を見たところ，凍結以前に AC していない問題への凍結後の提出については，凍結後に AC 済であったり CE であったりしても提出としてカウントされるらしい (これらはペナルティとしては可算されない)
  • 用意したスクリプトなどが正常に動作するかを重点的に確認する
  • インタラクティブ問題のテストを行うためのツールが支給されることがあるので，使い方を確認する
  • ゆっくりやっても時間が余るはず
    • スクリプトなどに修正が必要になったら，それを印刷することで翌日にも使える
    • 本番と同じ環境でライブラリの写経練習をするのも良い
    • あとの自己紹介タイムで何を言うか考える

コンテスト中の立ち回り

開始前/開始直後

  • やることが多く，必要な手順を飛ばしたりしやすいためこの部分だけでも練習する価値はある
  • パソコン担当が最初に行う作業は
    • PC ログイン
    • DOMJudge ログイン
    • 全問題のサンプル入出力をダウンロード
    • CLion 起動 \to 設定
    • .bashrc に書き足してターミナルで . .bashrc 実行
    • main.cpp にテンプレートを書きこむ
  • 環境構築の途中で A が解けても，テンプレートが不完全な状態で A を書き始めないことにしている
  • 将来的に SPJ の Github を公開してもっと詳しい内容を書くかも (書かないかも)

序盤 (開始から 90 分くらいまで)

  • 国内予選ほどではないが，ICPC ルールではあるため序盤のリードが保たれやすい
  • 前半の低難易度をペナなく速やかに終わらせることが重要
  • いったん全ての問題に目を通す
  • 英語問題文をある程度の速度で読めるようになっている必要はある
  • AB 以外にも簡単な問題はあるはずなので，解法が見えた問題でも実装が重ければいったん保留することはある
  • 5 時間あるので，20 分のペナルティは相対的には軽いものになっている
  • たくさんの問題を読む必要があるため，国内予選のときとは違い序盤でも担当する問題が分散することになる
  • 情報が少ないうちは順位表の確認を怠らない
  • 英語なので誤読が起こりやすい．問題を各自で読むか 1 人が口頭で伝えるかの判断は慎重に行う
    • 概要を聞いた問題でも，解けないと感じたら読み直すことも重要

中終盤

  • 多くの問題を通すことが必要な非常に苦しい状況でない限り，基本的に考察は 2 人以上でやる
  • 実装を 2 人以上でやるかは実装の複雑さで決める
  • 残り 80 分くらいの段階からは 3 人で 1 問に集中することも考え始める
    • ときには問題を捨てて他の問題の話を聞きに行く覚悟も必要
    • 並列で取り組んでどちらも通せずじまいで終わるのが最悪

デバッグ

  • 国内予選よりデバッグの機会は多く，チームの力量がかなり問われる
  • 1 人でやらない & やらせない
    • 解法を実装者だけが把握している場合でも，必ず他の人が応援に行って解法と実装内容を確認する
    • 他者の視点がある方がコードの欠陥に気付きやすいため
  • コード印刷も国内予選よりはやる機会が多い
    • 印刷クエリを投げてから紙が届くまでに時間がかかる
    • 通るか怪しいコードを投げたら判定を待たずに印刷
  • バグのあるコードを計算機を使ってデバッグするか，新しく解法が思いついた問題を書くかは難しい判断
    • 事前に ICPC Japan Problems などで実装が重めの問題を利用して実装時間を見積もる練習を行うのが良い．実装時間は大きな判断材料になる
  • 実装が爆発したときは方針ごと変えることも考える
    • この場合でも他の人と要相談

テクニック集

サンプル入出力の扱い

  • DOMjudge で Problemset のページからサンプルをダウンロードすると，それは ~/Downloads/samples-A.zip (A 問題の場合) に保存される．これを踏まえてファイルの解凍をするスクリプトも事前に用意する
    • リハーサルではファイル名が違うので適宜変える

コマンドなど

  • コンテスト開始時に簡単な bash スクリプトを実行しておくことで，よく行う操作をターミナル上の短いコマンドで済ませられるようにする
    • 特に以下の操作についてはコマンドを用意しておきたい
      • ソースファイルの生成
      • コードのコンパイル (コンパイルオプション付き)
      • サンプル入出力 zip ファイルの解凍
      • サンプル入力の実行
      • サンプル出力との差分確認
  • 次の年に使う頃にはコマンドなどはどうせ忘却しているので，ドキュメントを残しておく

オンサイトにおける注意事項

  • 以下の記事が参考になる． blue-jam.hatenablog.com
  • 1 日目に配られる T シャツと名札，および学生証を絶対に忘れない
  • 会場内は絶対に走るな
    • スタッフに強く制止されて注意されるので余計に時間を食う (マジですいませんでした)
    • 普段からコンテスト中に落ち着いて行動する癖を付けましょう
  • 飲食は PC のない方のテーブルで
    • 何かをこぼして PC が動かなくなると大変面倒．最悪続行できなくなる
    • そもそも競技中にあまり物を食うなという話．単純に時間のロス
  • 持ち込み可能かどうか明示されていなければ大体ダメだと思った方が良い．以下はダメだった例
    • 紙の資料を束ねるためのクリアファイル
    • 紙の資料を立たせることで写経しやすくするための書見台
      • なお，モニタにテープで紙を貼り付けるのも禁止されていた
  • 遅刻すると失格になることがある
    • 本番は朝早くからやるので注意

  • 競技開始が早まることがよくある

    • ギリギリに入場すると心の準備の時間が十分取れないかもしれず，良くない
    • アナウンスはちゃんと聞く

  • ホテル

    • 8, 9 月ごろには日程が分かっているはずなので，分かり次第取る
      • 土曜の横浜のホテルは値段が高いしすぐ予約で埋まる
    • 東京在住でも家が会場から十分に遠い場合は宿泊費の補助がある場合がある

  • 参加記

    • 読むの面白いので書いてほしい
    • タイトルに所属チームと筆者の名前を書いておくと他者から共有された際に既読判定がしやすい

*1:という認識．VSCodium と CLion 以外で確認したわけではないので，他にもあれば補足をお願いします

ICPC 攻略法：国内予選編

※ この記事は 2024 年度の国内予選終了直後に書かれました

はじめに

私が参加できる全ての ICPC 国内予選が終了したので，ここでその攻略法についてまとめてみる．想定読者は来年以降の ICPC 国内予選に参加してアジア地区大会への出場権を勝ち取ろうとしている人である．

ICPC は現代の競プロのコンテストの中ではかなり尖ったルールをしており，最大のパフォーマンスを発揮するには事前準備もある程度必要である．しかしそれについて解説されることは少ないため，競プロの実力自体は十分ありそうなチームが力を出し切れないまま敗退している例をしばしば見かける．ここでは細かい点も含めて押さえておいた方が良い項目をいくつか紹介しようと思う．

本記事は 10 位以内で国内予選を通過しようとしている東大チームを想定して書かれたものである*1．他大チームの場合でも，参加する環境や通過ボーダーなどの違いはあるが概ね参考になる内容だと考えている．

またこれは私が 5 年間所属したチーム SPJ における戦略である．チームごとに得意分野は違うので，必ずしも真似る必要のない部分もこの記事には含まれている． なお，参考までにチームメンバーは私，nok0, zkou の 3 人である．3 人とも AtCoder のレートが 2600 前後である．

用語について

同点の順位付けの際に参照される「各問題に掛かった時間の合計」のことを消費時間，誤答の際に加算される 20 分間のことをペナルティと (ここでは) 書く*2．

2024 年度のルール

詳細については公式ページの競技ルールおよび成績判定ルールを参照のこと．ここでは特に重要な点について述べる．

  • 問題数: 9 問
  • 制限時間: 3 時間
  • チーム人数: 3 人
  • ライブラリ: 電子ファイルの持ち込み可
  • インターネット: 予選システムへのアクセス以外使用不可
  • 全問同配点
  • 同点の場合，各問題に書けた時間の合計が小さい方が上位
  • 誤答 1 回につきペナルティ 20 分

昨年度からの変更点

  • 問題数増加 (8 問 \to 9 問)
  • ライブラリの持ち込み制限緩和．紙媒体以外のものも持ち込み可になった
    • USB などの機器がコンテスト中に扱えるようになったわけではなく，必要なファイルはあらかじめ PC に移しておく必要がある
  • 得点するための作業内容の変化
    • 出力ファイルの提出回数が 2 回から 1 回に変更
    • データセットのダウンロードから 6 分以内に提出し，正解することが得点の条件
    • ダウンロードから 6 分間が超過した場合でもそのデータセットに正答する必要がある．ここで誤答した場合は通常通りペナルティが付く．正答した場合はペナルティがつかず，次のデータセットのダウンロードから 6 分以内に正解すれば得点になる

準備物

  • PC
  • キーボード

練習

  • 実は国内予選のルールを練習できるセットは国内予選や模擬国内の過去問以外にほとんどない
    • セットが足りなくなったら AOJ のバチャ機能で適当な難易度の 9 問を選んで 3h を走る
  • 幾何や構文解析は現代ではさほど出題されないので，あまり特化しすぎないように
    • ただしこれらのジャンルを苦手意識なく捌ける人員が 1 人はいた方が良い
  • コーダー全員が同一のキーボードを使うので，それに合わせて練習をする必要がある．
    • アジア地区では US キーボードなのでできるだけそれで練習すべき

リハーサル・模擬国内

  • 用意したスクリプトなどが正常に動作するかを重点的に確認する
  • 序盤でつまずかないことを意識する

コンテスト中の立ち回り

開始前

  • スクリプトやソースファイル，ライブラリなどを準備する
    • 現行ルールなら紙で用意しなくて良い
  • 画面の右半分にエディタ，左半分にブラウザを開いておく

開始直後

  • 印刷を待っている間はできることがかなり制限される
  • ギリギリまで最適化するなら以下の手順で処理する (FA 狙い*3でなければここまで急がなくてもいい)．
    • おおまかには，A を読んで解く人 (人 1)，その間に B を読む人 (人 2)，印刷の受け取り待ちの人 (人 3) に分担する
    • はじめ，人 2 が PC の前に座り，人 1 がその左側に控えておく
    • 人 1 が A を読んでいる間に人 2 が A のサンプルをコピペし，入力を受け取るコードを書く
    • A を読み終わったら人 2 が PC の右側によけて，人 1 が PC 前に座って A を書き始める．
    • A を書いている間に人 2 がマウスでブラウザ画面をスクロールして B を読む or A の制約を読んでオーバーフローやコーナーケースなどを確認する
    • A を提出する

序盤

  • 国内予選は序盤が命

    • 序盤のリードが保たれやすいことには以下のような背景がある
      • 3 時間という時間が短い*4
      • 問題数が少なく，同点どうしの消費時間勝負になりやすい
      • 序盤の時間のロスが後半で解いた問題の数だけ消費時間として加算されてしまう (ICPC の一般論)
    • 得点で追い越されてしまっても，序盤で優位を取っていたなら得点で追い付くだけで余裕で逆転できる

  • よってまずは前半の低難易度をペナなく速やかに終わらせることが重要

    • 練習としてはやはり過去問をやるのが有効
    • グリッドグラフ上の探索が頻出

  • 速さは重要だが無理して最高速度を出す必要はない．ペナルティ 20 分の罪は非常に重いため慎重さも非常に重要

    • 多少遅くとも堅実にペナなしで行くのが最強．焦った他のチームが勝手に沈んでいく
  • 問題を解く人数の目安は AB で各 1 人，C で 1-2 人，DE で各 2 人，F 以降は状況次第という感じ
    • 問題を読んだ人がすぐ解けたからと 1 人で特攻して実装で沼にはまるパターンもよくある
      • D くらいからは解けたと思っても解法をいったん別の人にちゃんと伝えたほうが良い．計算量や実装方針についても慎重に確認する．1 台しかない PC は貴重な資源．見切り発車で実装を始めない
    • 場合によっては実装も 2 人でやる (ペアコーディング)．1 人が書いている間に細かい点をもう 1 人が精査する．序盤の有利を取るために人員を割く価値はある
      • デバッグもそうだが，チームメイトのコードをスムーズに読むのには慣れが必要．少なくとも使用しているテンプレートくらいは事前に把握しておく
      • 実装途中で補助者が抜けることは可能だが，逆に実装の途中で補助に加わることは難しい
      • よって半分以上の場合で実装を 2 人で始めることになる
    • 遅い戦略のようだが，少なくとも今の環境ならこれくらいじっくりやっても序盤でリードが取れる．本番でミスなく序盤を乗り切るのは意外と難しく，価値のあること
    • 強いチームはこんなことしなくても楽勝なんだろうけど，そういうチームはこんな記事読む必要がない
  • 3 問以上を並列でやるのは最序盤だけでいいくらい (一番伝えたいこと)
    • 10 位に入れば良いことを考えると，むやみに散らばるのは事故率を上げるだけ
    • 「3 人がそれぞれ D, E, F を読んで考察していた」みたいな参加記をよく見かけるが，これをやっていいのはうちより強いチームだけだと思う．難易度順が分かっているセットなので，人員を分散させるメリットが薄い
    • 考察が終わって実装を待っているときでも，変数名や更新式などの実装の細部を詰めたり，ペアコーディングをしたりと，次の問題に行くより先にやるべきことは大抵ある

中終盤

  • 多くの問題を通すことが必要な非常に苦しい状況でない限り，基本的に考察は 2 人以上でやる
  • 実装も多くの場合で 2 人以上でやる
  • 残り 80 分くらいの段階からは 3 人で 1 問に集中することも考え始める
    • ときには問題を捨てて他の問題の話を聞きに行く判断も必要

デバッグ

  • 3 時間は短いので，そもそもデバッグ自体が弱い行動．ペアコーディングでできるだけ回避したい
  • 1 人でやらない & やらせない
    • 解法を実装者だけが把握している場合でも，必ず他の人が応援に行って解法と実装内容を確認する
    • 他者の視点からの方がコードの欠陥に気付きやすいため
  • コードを印刷して計算機を別の問題のために空けるという手法がある
    • ただし問題が想定難易度順に並んでいる国内予選ではこの行動自体が弱い (それでもやらざるを得ない場面は存在する)
    • コードをシンタックスハイライト付きで印刷できるようにしておくと便利
      • 我々は VSCode の PrintCode 拡張機能を使っていたが，今は非推奨らしい？使用は自己責任でどうぞ
  • バグのあるコードを計算機を使ってデバッグするか，新しく解法が思いついた問題を書くかは難しい判断
    • 事前に ICPC Japan Problems *5などで実装が重めの問題を利用して実装時間を見積もる練習を行うのが良い．実装時間は大きな判断材料になる
  • 実装が爆発したときは方針ごと変えることも考える
    • この場合でも他の人と要相談

テクニック集

コマンドなど

  • あらかじめスクリプトを書いておくことで，よく行う操作をターミナル上の短いコマンドで済ませる
    • 特に以下の操作についてはコマンドを用意しておきたい
      • コードのコンパイル (コンパイルオプション付き)
      • サンプル入出力ファイルをエディタで開く (コピペがすぐ行えるように)
      • サンプル入力の実行
      • サンプル出力との差分確認
      • データセットを入力として実行してファイルに出力
  • コマンドの使い方に関してドキュメントを書いておく
    • 少なくともコーダー全員に共有する必要があるため
    • 次の年に使う頃には忘却しているため
  • ファイルの生成などについては，このルールであれば事前にやっておけばよい

データセットファイルの扱い

  • ダウンロードをする際のブラウザの設定が「保存するフォルダを毎回選択する」となっているならば，それを「国内予選本番で作業するディレクトリに保存する」に変更する
    • ダウンロードの際にダイアログが表示されないぶん時短になるし，ファイルの場所を移動したりする手間も省ける
    • 実行するファイル名は，例えば C 問題の 3 番目のデータセットであれば C3 となっている．
      • これに合わせて実行用のスクリプトを用意しておけば本番でファイル名を変更する必要もなく便利である
      • 例えば我々は ans a 1 コマンドで以下の一連の操作を行うようにしていた：
        • a.cpp をコンパイル
        • A1 ファイルを読み込んで実行
        • out_a1.txt に出力

手元実行であることを生かす

  • 実行制限時間は提出やダウンロードにかかる時間を除いても 5 分程度はあるとみなせる
    • 手元の計算機はどのくらいの処理に何秒かかるかを競技前に確認しておく
  • スタックサイズを拡張しておく
    • ulimit -s unlimited
  • オンラインジャッジと違い，手元のデータセットの実行途中に実行時エラーになってもペナルティにならない
    • 気になった assert は全部書く
    • コンパイルオプションはいっぱい付ける
      • 多少実行が速くなることよりもエラーが見つかることの方が偉いので，エラー検出系のオプションも付けたままデータセットを実行してしまって良い
    • _GLIBCXX_DEBUG は (計算量も悪化させるので) さすがに遅すぎるが，エラー時のデバッグにはあり
  • print デバッグのときには標準出力ではなく標準エラー出力を使う．消さなくて良い
  • 提出前に目視で出力を確認する．高々 10 回くらいしか出さないんだからサボらずにやったほうが良い
    • 出力の量が多すぎ/少なすぎないか？
    • 出力の値でおかしいものはないか？
      • (例) 非負整数が答なのに大きいマイナスの値がある \to オーバーフローしていそう
  • WA になった場合，古い出力ファイルを上書きせず保存しておく
    • コードの修正により出力結果に差分が生まれたことを確認してから投げ直す

東大チームの出場環境

  • 2024 年度は東大から出場したチームはほぼ全チームが浅野キャンパス (本郷キャンパスのすぐ横) にある情報教育棟の Mac を用いて出場していた
    • 10 チーム以上に印刷システムを提供しつつ監督を行う関係上こうなっている
    • この環境は来年度以降も変化しないものと思われる
    • 環境に不満があれば別の教員に個人的に依頼して別の場所で監督員をやってもらうしかない
      • この場合，プリンタやモニタなどを含めた環境も自分たちで用意する必要がある

東大情報教育棟の Mac

  • 普段の環境とかなり違うと思うので，一度は情報教育棟で想定通りの動きができるか確かめた方が良い
    • 駒場の情報教育棟にも同じ端末がある
  • 管理者権限によってソフトウェア等のインストールが制限されている
    • C++ のコンパイラは Clang しか使えない．よって <bits/stdc++.h> も使えない
    • エディタもデフォルトで入っている VSCode 以外の選択肢がほぼない
    • VSCode の拡張機能は入れられる
    • コードの自動フォーマッティングはできるかよく分からなかった (情報お待ちしています)
  • キーボード
    • デフォルトで日本語配列
    • USB 接続の自前のキーボードを接続できる
      • ルール上，コンテスト中に使えるキーボードは 1 台のみであることに注意
  • プリンタ
    • 位置が遠い
    • 印刷の際には端末にログインしている ECCS アカウントのパスワードを求められる
      • パスワードはアカウント所持者しか知り得ないため，毎回同じ人が取りに行くことになり不便．当日だけパスワードを変更してチームメイトに共有する手はあるが，パスワードの変更はすぐには反映されないこと，およびセキュリティ的によろしくない行為であることに注意してやりましょう
  • 実行速度
    • コンパイルが遅い
    • 実行そのものも速くはない
      • 体感だと AtCoder のジャッジの十倍くらいは遅い気がするので，計算量の大きい解法で無理矢理通そうとする場合は注意が必要
    • ただし近年の国内予選の問題はマシンの性能差に配慮してか，余裕をもった制約に設定してあることが多いように感じるのでそこまで心配はいらないかも

さすがに 5 回も国内予選をやっていると色々知見が溜まるものですね．普段考えていたことを文章化するとこんなにも長文になるのかとびっくりしました．他にもこんな Tips あるよっていう方はコメントで教えてください．適宜更新していこうと思います．

近年はアジア地区に行く強い東大チームが少なくなってきていると感じています．実力のある後輩たちが少しでも通過やすくなってくれると良いなと思って書きました．これから国内予選に挑む方のお役に立てれば幸いです．アジア地区横浜大会編もまたいずれ書きます．

*1:今の環境だと東大生でも 10 位以内でなくても通過できるかもしれない

*2:この両者はともにペナルティと書かれていることが多く，混同しやすい

*3:2024 年度はこれで FA が取れた

*4:この感覚は ICPC に毒されているかもしれないが実際とても短い

*5:この記事のために久々に AOJ-ICPC のサイトにアクセスしたら，知らない間に後継サイトが出現していてびっくりした

ICPC 2024 Asia Yokohama Regional 参加記 by Kite_kuma (SPJ)

ScreenWalkers が台湾で優勝したので，ここで優勝するしかなくなった．もともとこちらは圧倒的に格下でスピードも考察力も全く足りていないので，得意ジャンルのどれかで一発当てるしかない．具体的には，私が謎の幾何をやるか，zkou が天才構築パズルを解くか，nok0 が数え上げを解くかのどれかでしか勝ちがない．出題される問題の傾向によってはこちらに全くチャンスがないこともあり得る (というか，9 割くらいはそうなる) と思っていた．

1 日目についてはおまけってことでまた後日に書きます．

あまり良く眠れないままホテルで朝を迎える．普段は部屋を寒くして寝ているため，ホテルの部屋は室温が高く寝づらく感じる．寝汗を流すためにシャワーを浴びて，朝食を取りチェックアウト．会場までの道のりで審判団員の 〇pt さんを見かけ，話しかけて良いか分からず挙動不審にしていたら普通に話しかけてくれた．まあ今日は期待してて下さいよ！と言ったら笑いながら「ノーコメントです」と返されて，こちらも笑ってしまった．

8:40 に集合予定だったが，nok0 が 10 分くらい遅刻して，8:50 ごろに入場．使い古されたライブラリの束を取り出して，自作した環境構築のマニュアルを眺めつつ，ああもう自分にはあと 5 時間しか残されていないのだなと覚悟を決めた．

開始．私がもたつきながらも環境構築を済ませ，nok0 が A を通した後に，私が zkou に教えられながら B を書き上げる．予定通り C から問題を読んでいく．C は最小全域木っぽいがよく分からない．D はなんだか考察が重そうな数え上げに見える．E でも読むか…と思っていたところに nok0 から I の解法を提案される．大筋を納得して，細かい部分を考えつつセグ木を写す．その間に後ろで zkou が K の解法を思いつき nok0 に提案する．実装も軽いので PC を交代して K を書いた．K がペナって焦るもなんとか通し，私が I を通す．

それなりに順調な滑り出しに思えたのだが，この時点で確か 4 位くらいでしかなかったので焦る．本当は 2-3 位であれば良かったのだが，選んだ問題の順序のせいでもありしょうがない面もある．E がよく解かれているので，見てみると文章が長いだけの簡単な DFS なのでこれを書く． 通ったものの，実装がもたついたことと，これを先に読んでいればという後悔により少し落ち込む．

次に取り組む問題が分からなくなったが，順位表を見ると C が解かれている．よく分からんと思ったのだが…これって頂点 1 から重み付きで Prim 法やれば行ける？と提案する．zkou に若干疑われるも，これだけ通されているならこれくらいしか解法がないだろうということで書き始める．ほどなくして AC．実は最短路木を取っているだけであることに最後まで気付かなかったのはここだけの話．

次に私，nok0, zkou の 3 人でそれぞれ L, F, D を取り組んでいた．3 人とも難航していたものの最初に解法を提案したのは F をやっていた zkou. スタート地点の折り返しの点が高々 4 通りしかないので，そのうち 3 つを取って外心を取れば良い，という説明で納得できた．これなら実装も外心くらいしか非自明なところがないし，それほど重くせずに書けそうだ．zkou と 2 人で実装を行い，サンプルが合って提出するも WA になってしまう．ScreenWalkers もペナっている様子だったので焦らずミスを探す．まず制約が小さいので全ケース出力できることに気付き，出力させてみる．今後投げるときはこの出力結果に差分が出たときだけで良い．zkou が折り返しの点として他にも 2 点考える必要があることに気付くと，少しだけ差分が現れる．これで勝ったな，と思い提出するとさらに WA．原因不明，悪夢の連続ペナに心が参る．この問題は愚直解と突き合わせるなどのテクニックが効かないのが辛い．ひたすら自分のコードと向き合うだけの時間が続く．

nok0 が D を書き始める．私は途中ふらっと L に寄り道したりしながらも印刷された F のコードにおかしいところがないか確かめる．何度読み返しても合っている…もうだめか，と思って，諦めつつ実装を少し代わってもらい，もう 1 点，直方体の向かいの点についても調べることにしてみる．

…差分がある．え，うそ…．これが F 問題の FA になり，かなり沈んでいた順位表で 5 位にまで上昇した．続いて解法の正当性が怪しいと話していた D も通り，突然 2 位になった．うおおおおおおお ScreenWalkers 抜いてるやん！！！！…あのーシンガポールの方邪魔しないでもらえますか？とか言ってたら ScreenWalkers も F を通して再逆転され，我に返った．

ここまでで 3 時間強．あと 2 時間で G と L いけるやろ，と思っていた．L は解けそうなのだが，微妙に解けない．G で二分探索するアイデアだけ zkou に渡して詳細を詰めてもらい，L を nok0 と 2 人でやるも，なかなかアルゴリズムに辿り着かない．

ここで zkou に G の解法を提案される．これは解説スライドにあるものと全く同様のもので，これをシビアなクエリ制約で出題することに震えたが，どうせ勝つのには必須だし，解けるものは実装するしかない．zkou にそばで見てもらいながら実装を始める．

中央から始めるせいで初回のみ場合分けが必要なのもかなり面倒だ．ちなみにこのとき L はまだ計算量解析が分かっていない箇所もあるのでいったんやらないことにしていた．悶え苦しみながらもなんとかサンプルが合い，残り 40 分ほどで提出するも WA．焦りが頂点に達しつつ必死にデバッグする．残り時間が少なくなっても焦らない余裕が本当に欲しいといつも思う．幸い入力を作るのは簡単なので，色々なケースを試してみると…コードに色々と穴が見つかっていく．それらをひとつひとつ潰して，最後に提出したのが 4:54 経過時だった．どうせこれが通っても L をやる時間はないので，ジャッジ結果を見ることなく G に他のサンプルをいくつか入れてバグがないかを確かめていく．どうやらバグもなさそうだなと思ったところで順位表を見ると，緑色の四角が見えた．残り数分．L が詰められていない以上もう何もできない．ああ，これで俺は終わるんだ，もう...．nok0 が L を説明しているのに，放心状態になってしまい，何もまともに聞けなかった．

The contest is over. 順位表から見えているだけでも正解数で負けているので，自分の ICPC が終わったことが確定的だった．

「5 年間ありがとうな…本当に」

2 人の肩に手をやって言葉を掛けたとき，急に目頭が熱くなって，泣き出してしまった．なんか 2 年前もこんな感じだった気がする．そこからしばらくのことはあまり覚えていない．泣きじゃくりながら，来年も誰か見つけて出てくれよ，俺がコーチやるからさ，みたいなことをずっと言ってた気がする．

解説会．L 解けなかったことを強く反省した．H, J は面白そうなので後で解説片手に考えてみたい．LP 双対とか，マトロイド交差とか，なんか東大数理情報で聞きまくる単語ばっかりなんですが？そこまで辿り着けるレベルにはなれなかった…．全体的にはどの問題も非常に面白く，最後の ICPC がこのセットで良かったなと心から思えた．

Yes/No セッション．横浜で Yes/No をいつもやっているあの方は本当に手慣れていてすごいと思う．特に "nyo!" が良かった．結果は去年と同じ 5 位．結局 AMATSUKAZE と KUB1 の両方に負けてしまった．どちらかには勝ちたいと思ってたんだけどな．こんな弱いやつの言うことなんてほっといてこれからも強くなって欲しい．

写真撮影で少しふざけたら 2 人に呆れられた．あれはまあただ単に，なんとなくそのまま帰る気分になれなかっただけなんです...．

懇親会．阪大の vwxyz, 京大の naniwazu と雑談．この 2 人とは高校時代から縁がある．こたまねぎさんは ICPC ではめっちゃ頼りになるとか，WF で KUB1 は SPJ より明らかに強いと思ったとか，そういう話を聞いた．SPJ はどちらかというとチームワークでなんとかしているチームなのだが，結局もう少し個人の力を伸ばさなければ上では戦えないのだろうなと感じたりもした．あと vwxyz のインベーダー将棋が強すぎて勝てる気がしなかった．

解散後はチームの 3 人でジョナサンで軽く食べつつ喋った．私は来年以降の出場権を失ったが，実は 2 人はまだ早生まれとコロナ関係の特例で出ることができる．私の後継も見つかるかもという話をしていた．誰に来ていただけるか分かりませんが，幾何と構文解析，あと 2 人がやりたがらない諸々のことをよろしくお願いします．数え上げと閃き一発ゲーなら，本当に頼りになる 2 人です．5 年間一緒にやってきた私が保証します．

帰りの駅に向かうとき，話しながら歩く 2 人の後ろ姿を見て，おぞましいくらい強烈な物寂しさに襲われた．これからこの 2 人と遊びでチーム戦をやることはあっても，もう 1 台の PC と使いにくいキーボードをわちゃわちゃしながら取り合うことはないのだろうし，以前ほど本気で取り組んだりもしないのだろう．

私にとっては，SPJ とは競プロそのものだったのだ．大学で熱中していたこと，そのものだったのだ．

3 人で本当に，本当に色々な問題を解いた．走ったセットももう数えきれないくらい多い．最初の年は顔も知らないままずっとやっていた．2 年以降は大学の野外のベンチでやったり，カフェでやったりカラオケでやったり，くだらねーと言いながら重実装をしたり，チームメイトの天才的な解法に惚れ込んだり，旅行中にふざけて日本語禁止競プロもしたし，一緒に ARC を作ったりもした．

そして何よりの思い出は，残り少ない時間，全員で一丸となって一つの問題と PC に向き合い，一つでも多く正解をもぎ取ろうと戦ったことだ．うまく行ったときも，行かなかったときもあったが，どんなにつまらない問題セットだったとしても SPJ でのチーム戦は楽しかった．

なんで俺だけ先に終わっちゃうかねえ，ほんとに．そういうことを考えながら帰路についた．

これにてチーム SPJ (Kite_kuma, nok0, zkou) の ICPC は終了となります．nok0 の顔が広いこともあってか，これまで様々な人に応援していただきました．あとの 2 人が来年どうするかは分かりませんが，出ていたら応援してあげて下さい．JAG スタッフの方を含む ICPC 運営の方々，及び大学でコーチや監督員を引き受けて頂いた方々，今まで本当にお世話になりました．

ネットワークフロー関連のまとめ

先日の ABC174 を終え，自分の理解の甘さに気付いたためネットワークフローについて簡単にまとめてみる． 新規性のある内容でなく，すでに競プロ界隈で議論されている内容を中心に，私自身が理解しきっていないものも含めて書いていく． 主に他サイトへのリンクなどをまとめる役割． 理解が進んだり，分からないことが出てきたりすれば随時加筆する． 内容が間違っているとか，まだこういうトピックがあるとか，そういうコメントを頂けるとありがたいです．

問題設定

特に指定のない限り，最大流問題や最小費用流問題は次の問題設定であるとする． 特に最小費用流問題については色々と流儀がありそうだが，いったん以下のものを通常の問題とする． 厳密な定式化については時間があれば書く．

最大流問題 (以下 MF とも)

入力
  • 有向グラフ G = (V, E) : フローの文脈だとネットワークと呼ばれることも多い
  • 容量 c \colon E \to \mathbb{R}_{\ge}
  • 始点 s \in V
  • 終点 t \in V, t \neq s
出力

s- t フロー f \colon E \to \mathbb{R}_{\ge} であって，流量最大のもの

最小費用流問題 (以下 MCF とも)

入力
  • 有向グラフ G = (V, E) : フローの文脈だとネットワークと呼ばれることも多い．
  • 容量 \text{cap} \colon E \to \mathbb{R}_{\ge}
  • コスト \text{cost} \colon E \to \mathbb{R}_{\ge}
  • 始点 s \in V
  • 終点 t \in V, t \neq s
  • 流量 {F}
出力
  • 流量 F の s- t フロー f \colon E \to \mathbb{R}_{\ge} であって，コスト最小のもの

まあまあちゃんと理解したものたち

一度証明などを追ってはいるが，簡単に忘れるため定期的に勉強し直したほうが良さそうなもの．

理論的な話

  • 双対関連
    • 最大流-最小カット定理
      • (関連として) Kőnig の定理
    • 忘れても導出しやすい証明がないかなあと思ったり
  • antichain とパス被覆
    • Dilworth の定理
    • パス被覆/分割と bipartite matching との対応
      • 被覆のときは推移閉包を取り，分割の時は取らないっぽい

MF の実装

k 値カット

  • これ
  • 普通の燃やす埋める問題においては，各頂点が s- t カットにおいて s 側か t 側のどちらに含まれるかで最適化問題を解くというのが主なアイデアとなる．
    • このとき，関数が劣モジュラな 3 変数以下の関数の和で表されるならこれが最小カット (最大流と等価) で解ける
  • これを拡張して各要素 v \in V について選択肢 0, 1, \dots, {k}_{v}-1 がある場合の最小化を解く
  • これも 2 変数以下の劣モジュラ関数*1 の和で表されるならば解ける *2．
    • 各要素 v\in V に対応する選択肢の頂点を v_0, v_1, ..., v_{k_v - 2} の k_v - 1 個用意するのがポイント．適切に辺を貼ることで k_v 通りの選択を表現している．
    • あとはこの各頂点について辺を貼ることで通常の燃やす埋めるのようにできるが，劣モジュラ性のおかげで辺が張れるようになっている

十分な理解をしていない事項たち

聞きかじったりして詳細が不明な知識をまとめてある． これから調べるもののリストのようなもの． 以下の記述には筆者の記憶や偏見によるものが含まれており，誤りを含んでいる可能性が大いにある．

MF の実装

  • Push-Relabel の方が計算量も実装量も小さいと聞いたことがあるけど本当？
    • そもそも中身も忘れてしまった．

MCF の実装

  • そもそも実装をよく知らない
    • 残余グラフでダイクストラを流量と同じ回数実行してして…というのがすぐ思いつく
      • atcoder::mcf_graph.flow() の計算量は O(F (n + m) \lg (n + m)) となっているので，たぶんこれをやってそうな気がする
  • primal-dual とかポテンシャルの話
    • 特殊なグラフだとポテンシャルが高速に求まって… \gets なに？
    • コストが負でも Bellman-Ford をやればいいらしい
  • scaling って何者？速いらしいが
    • 容量スケーリングとコストスケーリングの両方を聞いたことがある気がする

理論的な話

  • パス集合で辺を被覆するやつ
    • ABC374 ユーザ解説より．もっと高速にできたりするのか？

min cost slope

  • atcoder::mcf_graph::slope() のやつ
  • 大した話ではなさそう

負辺除去・流量下限制約

  • あらかじめ流すことで b-flow に帰着できる
  • 流量が大きくなるぶん見かけより計算量が大きくなる
  • 特殊なグラフでどのように計算量を抑えるのかが腕の見せ所だが，自分にそういうノウハウがないため具体例で知りたい
  • 参考: 容量下限などが付いている最小費用流 - noshi91のメモ

b-flow

  • 超頂点を設けることで通常の MCF と等価な問題にできる
  • 計算量的に等価じゃなさそう
  • MCF の実装によっては b-flow を直接処理するものもあった気がする

*1:引数の各要素が 2 値でない場合の劣モジュラ関数．定義: 「 f \colon \mathbb{R}^{n} \to \mathbb{R} が劣モジュラであるとは， f(a) + f(b) \ge f(a \wedge b) + f(a \vee b) が成り立つことをいう．ここで a \wedge b, a\vee b \in \mathbb{R}^{n} はそれぞれ要素ごとに最小値，最大値をとったものを表す」

*2:3 変数の場合にできるかはまだ確かめていないができそうな気がする

JAG 夏合宿 2024 参加記 (Kite_kuma)

今年も夏合宿に行ってきた．現役世代としては最後の年．来年スタッフ側として参加するかは正直分からない．

1 日目

去年同様韓国の国内予選 (3 時間)．K 問題で入力が validate されていなかったせいでずっと WA が取れず，崩壊してしまった．変わった入力テンプレートを用いているせいで我々のチームだけが被害を受けていたようだ．これを受けて今後テンプレートを変えるかどうかは考える余地がありそう．あと，普通にその他の部分でもいろいろやらかして散々な順位になったのは反省．久々のチーム戦で動きの鈍さを実感した．

去年の合宿では夜に ABC と ARC があり，両方に出場したせいで疲労がとんでもないことになっていた．その経験を踏まえて ABC に出ずに談話室でボドゲでもしておこうかなと思っていた．しかしルームメイトに「全完してるところ見たいな～」と言われて出場することにした．我ながら性格が短絡的すぎる．G が 575 点の比較的簡単な回だったが，普段使っている PC と違うせいで F で有り得ない量の時間を溶かしてしまい，G が間に合わず終了した．芸人力が高すぎるだろ．

2 日目

有志セット．調子はまあまあだったが，ずっと双子が FA を取りまくるのを見て，こんなやつらに本番で勝たないといけないのかよと思った．

速度で勝てないなら天才問題枠で一発当てないと勝てないと思い中盤あたりで幾何の H 問題に取り掛かる．それっぽい解法を zkou に相談して，通る自身をもって提出するも 2 ペナを喫する．仕方がないので確実にできるがめんどくさくて後回しにしていた E を実装し始める．その間に H の増援に来た nok0 が H の考察の反例に気付く (ナイス！)．zkou が別の解法を提案して，H の解法が解決した．一方私は初歩的なミスで E をバグらせ続けていたが，残り 40 分を切ったタイミングでようやく通す．一息つく間もなく H の実装を伝え聞いて書き始める．どんなに疲れていても幾何の実装は私がやるしかないのである．時間がないため解法の正当性については 2 人を信じるしかなかった．実装を 2 人に監視してもらいながら書き上げる．N=4000 の O(N^{2}\log N) 解法なので計算量も不安だったが，追加のペナを生むことなく AC となった．残り 10 分を切っていたため，ここで終了モードに．

解説を聞いて，C は解けたなあという気持ちになった．入力形式に惑わされて基本的な方針を見逃がしたのは反省．あと K の言い替えが素晴らしい．全体的に問題の質が良く，問題数も 14 問と多かったので大満足．個人的には 3 日間の中で最も楽しいセットだった．誰がどの問題を書いたかについては全然当てられなかった．

今年は ARC がないおかげで (?) 懇親会があった．もう現役世代の中では一番上の世代なのだなと実感する．最近こういう場面で東大東工大京大の人ばかりと話してしまうようになった．実力が遠いと (自分より上であっても下であっても) 話題に困るのをどうにかしたい．あとは合宿運営をされている方にも少し話しかけた．

夜はまた将棋を指した．将棋経験者が私含めて 5 人いたので 3 人 (先手) 対 2 人 (後手) のペア将棋をやることに．私は先手チームに入っていたが，後手チームの miscalc 君と tokusakurai さんのペアを見て強くない？ってみんなで言っていた．

角換わりのいつもの局面．ここから

△３一玉 ▲７九玉 △６五歩 ▲同歩 △７五歩 ▲６四歩 △７六歩 ▲同銀 △８六歩 ▲同歩 △同飛 ▲８七金 △８四飛 ▲８六歩 △６七歩 (下図)

と進み，後手の攻めを受ける展開に．最終手△６七歩が結構嫌味な手で，対処が悩ましい．本譜は

▲７五銀 △８一飛 ▲６三歩成 △同金 ▲７四歩 △６五桂 ▲同銀 △同銀 ▲７二角 (下図)

と強気の対応．それなりにいい勝負かなと思っていたが，ここで miscalc 君が指した△５四銀 (下図) が金にヒモを付けつつ△６五角の両取りを用意する妙手で，先手が困ってしまった．

以下は後手が快勝．対局を見てくれていた人に手の意味を解説しながら指していたおかげで，将棋のダイナミックな面白さが伝わっていたようで良かった．

3 日目

nok0 が旅行に行っていて不参加だったためコーチの tokusakurai さんに加わってコーチングしてもらうことにした．

AB の後に zkou に G の解法を提案されてインタラクティブかよ…となって困った．実装してみるとペナを出したりしてグダグダに．どう考えても I を先にやるべきだった．今度からインタラクティブやるのはもうちょっと後からで頼むぜ．あれが速攻で解けるのはすごいんだけどさ．

あとは私が実装した K のバグが全然取れなくてごめんなさいという感じだった．印刷デバッグしている間に tokusakurai さんは C を 1 人で AC していて赤って強いんだな…となった．K をなんとか通したあと残りの 1 時間強で H を tokusakurai さんと検討していたが， O(N^{2}\log N) から全く落ちず絶望．E をやっていた zkou もずっと苦しそうにしていて，結局解けなった．構築に真っ向から挑んで敗北した zkou 選手を久々に見た．

序盤が爆速だった双子が C を解いていなかったためなぜか優勝した．本番もこういう感じで頼む～～～．これも面白いセットだったが中間の難易度がもう少し欲しいとも思った．

競プロチーム戦のわちゃわちゃした楽しい感覚を思い出した合宿だった．最近の自分は競プロを半分くらい惰性でやっているのだが， SPJ でやるチーム戦はやっぱめっちゃ楽しい (3 日目は SPJ ではなかったが)．

横浜まであと 3 か月くらい．悔いのないように準備したい．今年も楽しい合宿を開催して頂いてありがとうございました．

ICPC2024 国内予選・Kite_kuma (チームSPJ) 視点

明日は朝が早いので，簡単に更新．2 位でした．やったぜ．正式な発表はされてませんが，変なことか起こらなければ通過です．

2 位はこれまでで最高順位．

いつもみたいに詳細についてだらだら書く余裕がないので，要点をかいつまんで書く感じで．

前日まで

もう 5 年分の蓄積があるので，ほとんど何も練習はしていない．事前準備できるらしいし，構文解析も幾何も出たとこ勝負でなんとかなるだろうと思っている．

大学の情報教育棟の端末を使ったことがなかったので，2 回ほど浅野キャンパスに立ち寄って挙動を確認していた．私は Mac は初使用だし，管理者にあらゆるインストールを制限されているせいで clang しか使えなかったりとかなり不便だったが，それでも出来る限り普段の環境に近づけるように当日のセットアップを考えた．

当日

午前の授業を受けた後，zkou と大学近くのカレー屋に行ってお腹一杯になるまでナンを平らげた．とても暑かったので帰りにコンビニで買ったパピコを半分に分けて食べるなどした．

nok0 とも合流して浅野へ向かう．到着．そそくさとセットアップを始める．サンプルをコピペしたりテストデータをダウンロードして提出したりする手順を nok0 と確認する．zkou は PC に触らないためか，眠たそうに聞いていた．

開始．ABC をまず通す．nok0 が狙い通り A の FA だったらしい．nok0 が問題を読んでいる間に私がサンプルをコピペしてファイルに貼り付けて入力できる状態にしておくなどの細かい時間短縮が効いたらしい．D はまあやるだけなのだが，なんか微妙に怖くなって慎重に実装を確認していたら AC する頃には結構時間が経ってしまった．反省．E はちょっと nok0 が苦しみつつ zkou とデバッグしていたがまあなんとかなったっぽい (よく知らない)． その間に F のアイデアが湧いてきたので，手が空いた zkou に説明．zkou はゴールから 4 方向だけ考えれば良いことを教えてくれて，私が実装．zkou は nok0 がやっている G の応援に回った．

私が F の実装に苦しんでいたら 2 人が G が解けたと言う．まだ実装が煮詰まり切っていないらしいので F の実装を続行．G が整理され，あと何分？と聞かれて 15 分と答えるも，15 分ではバグが取り切れず，やむなく G に交代する．その間 F のコードの印刷をして (これにもかなり手間取った) バグを探す．バグはいくつか見つかったが，これを取り去ってもまだ正しく動かないはずだ．G もバグっているらしいので，また PC を交代して F のデバッグをすることに．2 問を並列で触って両方炎上するという非常に厳しい展開になってしまってかなり焦った．適当に print してみたら問題の箇所はすぐ分かった．F を AC．G もほどなくして直った．

順位表を確認したらかなり上位 (確か 2~4 位くらい？) にいて一安心．H を考え，フローか？と言っていたら nok0 が I の怪しい解法を提唱する．え～そんなんで最終問題通るのか？でもなんかあってそうだし…とサンプルを実行してみると全部合ってしまう．マジ？といいつつそのまま AC までしてしまった．興奮して nok0 の背中を強めに叩いてしまった．これでにより 8 完で 1 位に躍り出た．

そういえば双子のチームはどこだろう？1 位どころか上 10 チームにもいないが…と思って探したところまだ 5 完しかしていない！

………？！？！？！ 何が起こってるかよく分からないが，もしここが落ちたら，うちが WF に行く大チャンスなんじゃないか？双子の参加を知ってから半ば諦めていた WF が現実になるかもと思うと，思わず胸の鼓動が速まった．他力本願みたいで嫌な話だが，赤 3 人様と違って，こっちにしてみれば最後に残された細いチャンスなのである．

ずっと順位表を見ていてもしょうがないので全完目指して残りの H を 3 人で考察する．あるマスをふさいだ時に侵入できなくなる点の集合は計算出来て，それで左下から右上をつなげば…というのは分かったが，それの実装は…残った 20 分でできる気はしなかった．頑張ってみるも撃沈．10 分前に AMATSUKAZE に抜かれて，君たちやるねえ！って言ってたら終わった．終わってから知ったが，2 位に企業賞あるらしいしまあこれで良かったかな．

現実的な範囲で目指せる最高順位が 2 位だと思っていたのでとても満足している．1 位は思っていたチームとは違ったが… AMATSUKAZE おめでとうございます．最近本当にどんどん強くなってますね…．Screenwalkers は期待させたくせに結局残るんかい．しかも 11 位．3 年前なら落ちとるからなそれ (経験者)．はーーーーーーーーーしゃあねー横浜で倒すしかねーかー．めんどくせー．

東大チームが 10 位以内に 1 チームしかいないことが話題になっているが，個人的にはそれほど驚きはしなかった．2 年前は 6 チーム，去年は 5 チーム通過していたわけなので，傍から見ると突然弱体化したように見えるかもしれないが，それは 1 年上の DELIAIR, ラズキャン，noimi さんあたりのチームの層が厚かったためである．今年は既にそれらのチームがこぞって引退しているので有力候補も少ない．(それでもこの下振れはやはり意外ではあるが)

というかそもそも全体で赤以上が在籍しているチームがほとんどないのである．橙以上ですらかなり少なく，10 チームくらいしかないらしい*1．ICPC オワコンなのか？とちょっと変な心配をしてしまうが，参加チーム数は増えているらしいしたまたま今年は上位層が薄いだけなのかもしれない．まあともかく私は最後の年なのでもう関係ない話だ．横浜では全員倒す．もっかい勝負や．

簡単に書く，って書いてたのに結局いつもみたいにだらだら書いてしまった．

*1:自分が数えたわけではないので正確なところは知らない