ACPC2025 参加記

03/22 - 03/24 に会津大学で開催された ACPC2025 に参加した．1日目の立命館大学セットと3日目の会津大学セットではコンテスタントとして，2日目の東北大学セットでは運営として参加した．

03/22

朝6時に起床し，東京から高速バスで会津若松へ向かった．最後に会津に来たのは小学校6年生のときの修学旅行以来だ．当時は鶴ヶ城などを見て回って，風情のある街並みがあっておもしろい場所だと思った記憶がある．ただ今回はあまり観光する時間がなさそうだ．

バスが30分遅れ，会津若松駅についたのが13時頃だった．受付は13:30までなので，昼ご飯を食べる暇もなく会津大学に向かう．

高レート牛

着いてすぐにチーム分けが始まる．ある程度レートの近い人で集まって，名札をシャッフルしてくじ引きをするという方法でチームを決めた．1日目のチームメイトは m_99 さんとかっつさんになった．

チーム名としてかっつさんが Give_us_Aobayama を提案したが，それは数年前の UTPC でも使った記憶があったので，Aobayama を Bandaisan に変えることを提案して Give_us_Bandaisan というチーム名になった．

14時から立命館セットが始まった．
https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2025Day1

僕はBCEFJK を担当した．

E
最大の数字を根にするのが良いとはすぐにわかったものの，謎の制約が気になり，とりあえず後回しにすることにした．しばらく F を考えていたが，順位表を見ると E がかなり早く解かれていたので，改めて考え直したらギャグだった．まんまと制約に騙されました．

F
高さごとに2次元累積和をするという自明な方針がすぐに立った．制約的に怪しかったが，まあ通るだろうと思い実装してみたら通った．

C
m_99 さんと考えた．素直に考察して \(O(N^2\log N)\) の解法がすぐに得られた．制約が怪しかったが，定数倍が軽いはずなので通るだろうと思って投げたら通った．

B
かっつさんが苦戦していたので見に行った．僕はこういうのを見ると何も考えずに平衡二分木を貼りたくなるので，貼った．僕のライブラリがバグっていて手間取ったが，通った．

J
m_99 さんから，この問題がハッケンブッシュというゲームであることを伝えられた．ハッケンブッシュは昔「石取りゲームの数学」という本で読んだことがあり，解法の雰囲気を覚えていたので僕が取り組むことにした．といっても，調べたらこれをそのまま解いてくれるライブラリが見つかったので，貼ったら通った．ちなみに「石取りゲームの数学」には他にもマヤゲーム，Wythoff の二山崩し，逆形ニムなどいろいろなおもしろゲームの解法が載っているので，非常に面白い．おすすめである．

K
m_99 さんと考えた．同じ文字から始まる命令は消して良いこと，グラフのサイクルを見ることで無限ループの判定ができることは順調にわかった．あとは本質部分だが，一緒に考えているうちに，筋が良さそうな方針が立った．言葉で説明するのが難しいのだが，命令を最初から見ていって，後ろの命令とマージしていくことで文字を減らしていくみたいな感じである．チームメイトが他の問題を通すのを待ち，最後30分余ったので実装をした．1ペナを出したが，残り2分で滑り込み AC した．

単独 11 完で優勝した．コンテストで優勝したことってない気がするので，素直に嬉しい．JKが通せたのが大きかった．

解説を聞いた．F の想定は賢いなあという感じだった．G は不可能すぎてすごい．J は writer の方が自力証明したらしくてびっくりした．実質 John H. Conway である．K は想定解の方針が自分のと全然違っていて面白かった．楽しいセットでした．

その後は一旦ホテルにチェックインしたあと，何人かで集まって飲みに行った．僕と東北勢 4 人と，かっつさん，olphe さん， MMRZ さん．今日の立命館セットの運営の裏話とか，共通の知り合いの某競プロ er の近況の話とか，いろいろな話をした．あと会津の地酒が大変おいしかった．

その後，昼をほとんど食べていなかったこともあって腹が満たされない気持ちがあり，ラーメンを食べに行った．


03/23

9 時頃に起きて，会場に向かった．

この日は東北大セットである．僕はもう東北大を去ってしまったが，また今年も運営として関わらせてもらっており，嬉しい限りである．また，TUPC を会津オンサイトで開催するというのは初めてのことで，今までと違うワクワクもあった．

今年は 5 時間 18 問とかいうバカデカセットである．それでいて，事前の個人的な感覚では，難易度も去年より全体的に上がっている感じがあるので，かなり重いコンテストであると思う．一体どれだけ解かれるのか楽しみだ．

11 時にコンテストが始まった．
atcoder.jp

以下，問題のネタバレを含むので，Universal Cup 参加者は見ないほうが良いです

簡単枠（？）のP, Q, R は序盤から順調に解かれていった．前の 15 問はランダムに配置されている上に全体的に難しいので，解ける問題を見つけるだけでもかなり時間がかかるだろうなと思っていた．E, H, L, M あたりの（比較的）簡単な想定の問題は 1 時間くらいで見つかり，解かれていった．

意外だったのが N 問題がかなり速く解かれていたことである．これは writer も tester も少なくとも橙はあると信じており，また実装難易度もかなり高いので，終盤まで解かれることはないだろうと思っていた．ところがかなり序盤に通されて，順位表が破壊されていた．

さらに衝撃だったのが，A, B に AC が出たことである．A は自分で考えていないが，関係者によると恐ろしく難しいらしい．B はテスターをして，20点分の部分点をかろうじて取ることができた（これだけでも恐ろしく難しいと感じた）程度で，満点はまったく意味不明なので，AC は出ないと予想していた．しかし，出た......．すごすぎる．

コンテスト中に運営何人かで抜け出して，会津若松駅まで昼ご飯を食べに行った．ソースカツ丼が会津で有名であることを知らなかった．非常に美味しい．

コンテストが終わった．大変なセットだったと思う．もともとこのセットは UCup 向けに組まれたものなので，難易度もそれ仕様になっていたが，このセットにオンサイト合宿で取り組むのはかなり大変だろう．オンサイト1位も5完にとどまっていた．18問あるのに......．UCup の方ではどれくらい解かれるのか楽しみだ．

僕が writer を務めた H, N についてコメントする．

H - 12 Grid
P, Q, R を除いて最易のつもりだった．全体の順位表では E, L のほうが少し解かれたという感じだった．ただ，オンサイトで AC が出なかったことには驚いた．
僕はこういう問題が苦手なので難しいと思ったが，テスターのみんなは簡単だと言っており，1600 diff くらいが想定されていた．実際は 2200 くらいだと推定されていて（参加者が多くないので，あまり信頼はできないが），やっぱり難しかったらしい．
僕は問題設定を考えたあと，BFS を使う泥臭い解法を思いついて提案したが，とりゐ君がエレガントな解法を見つけてそれが想定解として採用された．他のテスターも皆きれいな解法で解いていて，すごい．

N - Palindromic Path
去年の TUPC で僕は回文ネタの問題を 3 問くらい出した．その時に作った問題の余りを今回出した．考察は素直だが，ライブラリ要素が強いので，作問者としてはあまり満足度が高くない．また，もともとこの問題は頂点1から始まる回文パスの存在判定だけだったが，全部の頂点について求められることをとりゐ君に指摘され，この形になった．嘘には強くなったと思うが，実装量は多分1.5倍位になった．
それでも嘘解法は落とせなかったらしい．N を爆速で通していた2チームは，とても少ない実装量で解いていたことに驚いたのだが，この BFS 解法は hack ケースがあるとコンテスト後に Twitter で議論があった．この解法を全然考えていませんでした．申し訳ない......．

想定解どおりに解いてくれたチームもあった．


他の問題だと，D, O が個人的に好みだった．

今日もコンテスト後に飲みに行った．東北勢6人と，m_99 さん，かっつさんで居酒屋に行った．馬刺しがうまい！

あと日本酒がとても美味しかった．いろいろなお酒を頼んで飲み比べていた．写真には写っていないが，「一生青春」という地酒が個人的ベスト．名前も味も良い．

地方で1日だけのオンサイトだと，終わったあとに参加者とご飯に行くみたいなことがしづらいが，こういう合宿形式だとそういうことができるので，楽しい．

その後なぜか仮の人君，ののん君と作問しながら歩いて夜の鶴ヶ城を見に行った．


03/24

9 時頃に起きて，会場に向かった．

最後は会津大セットである．チームを決める．初日と同様に，レートがある程度近い人の中で名札くじ引きでチームを決めた．この日のチームメイトは m_99 さんと ripity くんになった．チーム名は Maximum_Bandaisan.

11 時開始．
https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2025Day3

僕は BGHJ を解いた．K にも取り組んだが通しきれなかった．

B
実装をミスって 1 ペナしてしまった．

G
桁ごとの寄与を考えると簡単だった．

H
一見やばそうなので放置していたが，結構解かれていたので見に行った．倍数の辺は全部愚直に張れるが，非倍数の辺が大量に出るのが問題である．実は隣接頂点に張るだけでいいというのは面白かった．

J
まあ suffix array を適当にガチャガチャやればいいだろうとは思ったが，異なる位置の同じ部分文字列を区別しないというのがめんどくさそうだなと思っていた．実装してみると全然そんなことはなく，かなりきれいな形になって面白かった．

K
結構序盤に読んで，実装の大変さはともかく解法はスムーズに浮かんだので実装していた．しばらく実装してサンプルがあったので投げると落ちたので，放置してしばらく他の問題を見た．終盤にまた戻ってきて再度取り組み，いくつかバグを見つけて直したはずだがそれでも通らなかった．悲しい．

12完，全体 6 位オンサイト 3 位だった．初日のような優勝を狙っていたので悔しい．

解説を聞いた．自分が取り組んだ問題は概ね想定解通りだった．K 通したかった......．面白いセットでした．

終わったあと，会津大の学食でソースカツ丼を食べた．学食でこれが食べられるのか．いい大学だ．

その後，会津若松駅周辺ですこしお土産を物色し，高速バスで仙台に行った（実家に帰省するため，東京ではなく仙台に）．

おわりに

僕が大学に入った年からコロナだったので，会津合宿なるものがかつて存在していたという噂は聞いていたが，参加することが叶わず5年経ってしまった．今年ついに参加できて，長年の夢の1つがかなったような気持ちである．

ICPC が終わってからあまり競プロに触れていなかったが，今回3日間みっちり競プロに取り組んで，やっぱり問題を解くのは楽しいなと思った．特にチーム戦は楽しい．

皆さんありがとうございました．

ICPC2024 国内予選 参加記

チーム Magic Strijk (eijirou, ikefumy, sotanishy) で，ICPC2024 国内予選 に参加した．

チーム

僕は大学院から東大に来たので，入学時点でチームが決まっていなかった．できればチームメイトを見つけて国内に参加したいなあと思っていたら，4月末に Twitter の DM で声をかけてもらってチームが決まった．

チームメイトを紹介するぜ！

  • eijirou
    • AtCoder Algorithm 黄．ICPC 初参加．圧倒的なヒューリスティック力（執筆時点で AtCoder Heuristic 世界 4 位）で，すべての最適化問題を焼き鈍してほしいと考えていたが，今年から実行時間制限がついてしまった......．
  • ikefumy
    • AtCoder Algorithm 黄．彼も大学院から東大．学部のときは早稲田でバリバリ ICPC に出ていて，去年 playoff に出場した経験もあり，ICPC 経験値が高い．だいたいなんでも解け，強い．
  • sotanishy
    • AtCoder Algorithm 橙．僕．学部は東北大．

メンバー全員 M1 で，今年が ICPC ラストイヤーである．

Strijk は eijirou の ij, ikefumy の ik, sotanishy の st を含む．Dijkstra なんかもいい感じの単語だが，様々な案を慎重に検討した結果 Magic Strijk になった．マジックストライクと読む．（あとで気付いたが，東大の Magical Fish という他のチーム名と被っていて申し訳ない......）

目標

国内予選通過．東大のチームは，全体10位以内に入ることを実質的に要求されるが，今年は橙以上を擁するチームがあまり多くないので，僕らもそこそこ希望はあった．

本番前

5月から週1で集まってチーム練習を行った．Codeforces の gym や，AOJ にある各種コンテストの過去問のバチャを走りながら，チームの動きを確認していった．

チーム練習ではなかなか調子が良かった．しかし，去年もチーム練習では調子が良かったのに本番だけ大コケすると言う事態があったので，下振れを防ぎできるだけパフォーマンスを安定させるために，以下のような考え方で戦うことにした．

  • ABCD を eijirou, ikefumy が解いている間に， sotanishy が E 以降に目を通す．
    • 10位以内に入るには，EFG をどれだけ速く多く解けるかが勝負だと思っているので，中盤の考察時間はできるだけ多く取りたい．
  • 分野による分担は，特に行わない．
    • 各々多少の得意苦手はあるとはいえ，極端に尖っているメンバーはいない．だから，見た問題は基本的に自分で解く．
  • D 以降は，各問題に少なくとも2人つけ，1問ずつ着実に解く．2人以上が問題と解法を完全に理解した状態で実装する．
    • 先に1人が問題を読んでいて解法までわかっている（つもりになっている）という場合でも，2人目をつける．
    • 解法をわかったつもりになっているときは，3分の1くらいは嘘解法であるから，2人目は重要である．
    • 誤読による事故を防ぐため，問題設定を2人目に口頭で説明するだけじゃなく，問題文を完全に読んでもらう．

特に誤読チェックは結構重要で，議論している間に片方が問題設定を間違って理解していたことが発覚するというのは練習中にしばしばあった．2人が問題を読むことで時間を少し失うが，誤読により失われる数十分＋ペナルティに比べたら微々たるものだろう．

週1のチーム練以外は，競プロをしていなかった．言い訳をすると，平日はだいたい朝から晩まで研究か勉強をしており，帰ってから競プロをやる頭の元気があまりない．週末にコンテストに出たり，たまに作問するくらいしか競プロをしていなかった．そのため，練習不足なんじゃないかと不安だった．

本番前の1週間はできるだけ競プロに触れる時間を確保して，溜まっていたABC/ARCのupsolveやAOJ-ICPC埋めに取り組んだ．

模擬国内 06/29

開始が30分遅れるというトラブルがあった．本番で突然起こったらかなり心臓に悪いので，これも含めて練習．

eijirou, ikefumy が ABCD を解いている間に僕が EF を読む．E はすぐ解法がわかったが， F はしばらく考えてわからなかった．ABCD が終わった段階で E を実装する．細かい考察漏れがあり 1WA を出したが無事 AC．

F を全員で考える．ここで天啓が降ってきて，ダブリングみたいなテーブルを作れば O(N log N) 時間で遷移のコストがわかり，あとは前から DP すればいいということがわかった．実装して AC．

F を実装している間に2人が G を考えていて，ほとんど分かったらしい．F のあとに実装してもらい，少し手間取ったようだが AC．ここまで2時間位で，この時点で5位．

残り1時間で全員で H を考え，考察はそこそこ進んだが本質部分がわからず終了．

順位は2つ落ちて全体7位．ゲスト除いて6位，東大内3位で，なかなか良い結果になった．ちゃんとチーム戦をできたので感触も良い．

とりあえず，模擬国内では国内通過圏内の順位を取れて安心した．ただし上位がだいぶ詰まっているので，全然油断はできない．

本番2日前

「響け！ユーフォニアム」3期最終回を見た．コンクールが ICPC と重なり，涙腺が崩壊してしまった．主人公たちがラストイヤーというのも感情移入ポイントだった．

本番前日

本番の会場が練習用に解放されていたので，集まって環境の確認をし，最後のバチャを走った．印刷やエディタの設定など，いろいろ非自明ポイントがあったので，このときに確認できてよかった．

本番 07/05

13時半にチームメイトと合流し，リハーサルに出る．毎年，鎖中経路の実装タイムアタックをしていたはずだが，今年のリハーサルではここ数年の国内予選の問題が集められていて，懐かしい気持ちになった．

15時頃会場に移動する．環境のセットアップをしたり他のチームと喋ったりしていたらあっというまに時間が来た．過去の国内予選では開始1時間前くらいから極度の緊張に見舞われていたが，今年はなぜか全然緊張しなかった．

遅延なく16:30に開始．ABCD を2人に任せて僕はEを見に行く．ABC は19分で通る．Dはめんどくさそうだが，eijirou くんが50分でノーペナで通してくれる．割と順調だと思っていたけど，この時点で確か30位くらい？みんな速くない？

E を，C を終えた ikefumy くんと一緒に考察する．両端が一致したら自明にOK．そうでない場合，つまり両端が異なる数字の場合は，1A2B1C2みたいな形だったら |A|=|C| のときすぐに構築できた．ここが等しくない場合にどうすればいいかなあと悩んでいたら，ikefumy くんが再帰的に問題を小さくしていく解法を思いつく．両端に出てくる数字を外周に置いたのち，内側の部分を再帰的に埋めていく．怪しかったのでいくつか hack ケースを提案したが，アルゴリズムを微妙に修正すればだいたい回避できた．もっときれいな構成がありそうな気はしたが，再帰解法も正しそうだと思ったので実装を任せる．

Dを終えた eijirou くんとFを見に行く．大まかな方針はすぐに思いつく．コインから4方向に進んで最初に当たるボールが答えの候補であり，逆にそれぞれの候補からみて最初に当たるのがコインかどうか判定すれば良さそうだ．最初に当たるボールの判定は，それぞれのボールに対してそれに当たるまでの時間を求めて，それの最小値を求めればいいだろう．盤面を2回折り返すとトーラスになるので，拡張ユークリッドをやれば当たるまでの時間を求められる．

しばらくしてEの実装が終わり，提出するもWAが返ってくる．Eをデバッグしてもらう間にFを実装する．実装が少々難しく，大いにバグらせた．Eと適当に交代しながら実装を続ける．Eは細かな実装ミスや考察漏れが見つかったそうが，どれも微妙に修正すれば大丈夫らしい．しかし，修正して提出するもWAを出すことを繰り返していた．

Fはようやくサンプルが合ったので提出したところWA．Fの解法にはかなり確信を持っていたので，細かい実装ミスだろうと思いデバッグを頑張る．コードを印刷して，チームメイトに処理を説明しながら怪しそうなところを探していたが，よくわからない．拡張ユークリッドのところが怪しいのだがちゃんと落ちる理由を見つけられていない．

こう文章で書くと1時間半位の出来事のように見えるが，実は3時間の出来事だったらしい．気づいたら終わっていたが？

コンテスト後

66位！？意味わからないくらい冷えて感情がない．

全体的に大波乱の順位表だったようだ．上位10位に東大が1チームしか入っていないのはかなりびっくりだった．ということは10位以内に入らなくてもアジアに行ける可能性があったわけだが，可能性を考えるのが馬鹿らしいくらいの順位を取ってしまった．

終了後，Eの解法を他のチームに聞いた．先程悩んでいた，1A2B1C2みたいなやつは |A|≠|C| でも常に可能と聞いてマジ！？となり，考え直したら3秒位で構築がわかってしまった．|A|=|C|のときで思いついていたやつをちょっとずらすだけで良いので，なんでこれを本番中に思いつけなかったのかわからない．

Fは解法は概ね合っていたらしい．ただ，拡張ユークリッドをやらなくても，反射回数が少ないのでうまいことシミュレーションしても間に合うというのを聞いて賢いなと思った．ただ，拡張ユークリッドで通した人もいたので，シンプルに僕の実装が下手だった．

終了後，チームメイトとハンバーグ屋に行って打ち上げをしていたら，示し合わせたわけではないのに別の東大チームがぞろぞろ入ってきてウケた．本郷まわりたくさん飲食店あるはずなのになんで被るんだ．

感想

ま，魔法のせいにしておこうかな．

去年も同じように，勝てるはずのチームで完敗した．ただ今年は，去年の反省を活かして，ちゃんと各問題に2人つけてパフォーマンスを安定を図ったはずなので，今回は単に脳みそが全然足りなかったとしか言えない．練習ではかなりいい感じなのに，本番でその年一番冷えるということを過去3年間くらいずっとやっているんだけど，一体どうしたものか．

全然解けなかったけど問題面白かったです．Eの構築は美しい．本番中に見れなかったGもあとで考えたけど，ARCっぽい，楽しく考察できる感じの問題で良かった．問題が面白かっただけに余計悔しい．

ICPC 5年間の振り返り

国内予選の参加記はここまでです．これで ICPC 現役引退なので，ここからは過去5年間の大会を振り返り，感傷に浸る．

2020年（B1）

チーム：state_of_the_art (むげんさん，クマノミさん，僕)
国内：73位

当時4年生の先輩方に誘っていただいて組んだチーム．実力的には学内2位を狙え，模擬国内とかでは実際にいい感じだったが，本番でうまく行かず負けた．とても悔しかったが，はじめてのチーム戦はとても楽しかった．来年は絶対にアジアに行くと誓った．

2021年（B2）

チーム：suzukaze_Aobayama（むげんさん，仮の人くん，僕）
国内：6位
アジア：10位

sotanishy.hatenablog.com
sotanishy.hatenablog.com

僕と同期の仮の人くんをチームに迎えた．天才枠を仮の人くんが，それ以外を僕とむげんさんが解くという，分担がはっきりしていてバランスの良いチームだった．正直アジアの通過可能性は1年前と同じくらいだと思っていた．模擬国内では冷えて通過圏外だったのでなおさら不安だった．しかし国内ではどうしてか早解きに大成功し，国内6位，学内1位という信じられない順位を取ることができた．大学生活で一番輝いていた瞬間，間違いなくこのときだと思う．

アジアは残念ながらオンライン．国内の高順位はまぐれだと思っていたが，アジアでもなぜか早解きに成功し，一時は全体2位にまでなった．強豪チームの中でトップ10に食い込めたのは今でも驚いている．来年はオンサイトでアジアに参加したいと思った．

2022年（B3）

チーム：suzukaze_Aobayama（milkcoffeeさん，仮の人くん，僕）
国内：26位
アジア：13位

sotanishy.hatenablog.com
sotanishy.hatenablog.com

むげんさんが引退されたので，milkcoffeeさんが加わった．前年のチームでコツを掴んだのか，練習ではいつもいい感じのパフォーマンスを出していた．国内本番ではかなり失敗したが，辛うじて学内2位に食い込み，2度目のアジア進出．

この年からアジアがオンサイトに復活した．本番では，僕はほとんど貢献できなかったものの，チームメイトが頑張ってくれて13位．前年の記録を超えられず悔しかったので，次はもっと上を目指そうと思った．　

2023年（B4）

チーム：suzukaze_Aobayama（milkcoffeeさん，仮の人くん，僕）
国内：29位

sotanishy.hatenablog.com

2年連続同じメンバーで出るのは初めてだ．練習ではびっくりするほどうまくいき，模擬国内では3位という信じられない順位も取った．東北大のトップに君臨していた Aobayama_dropout が前年を最後に解散したので，僕らは余裕で学内1位で通過できるだろうと思っていた．しかし本番では実力が発揮できず学内3位で負け．milkcoffeeさんはラストイヤーだったし，僕は東北大でICPCに出られる最後の年だっただけに，大いに落ち込んだ．大学生活で一番悔しかった瞬間，間違いなくこのときだと思う．

2024年（M1）

チーム：Magic Strijk（eijirouくん，ikefumyくん，僕）
国内：66位

今年です．勝ちたかったな〜．

全体を通しての感想

2年目をピークに国内の成績が単調減少している．個人的な本番のパフォーマンスも2年目がピークで，それ以降はほとんど何も貢献していない．本番時のレートは単調増加しているはずなのにな......．特に，橙になってからの国内予選はすべて落ちている．本番にめちゃくちゃ弱いタイプなのかもしれない．逆に，2年目にうまく行ったことのほうが不思議に思えてくる．

思い残すことはたくさんある．アジアで一桁順位を取りたかったとか，海外でのコンテストに行ってみたかったとか，めちゃくちゃ難しい問題を本番中に解きたかったとか......．あとは，東北大が WF に行っているのを見たかったかな．東北大の入試の面接で血迷って「東北大を ICPC WF に連れて行くぜ！」みたいなことをしゃべったというエピソードがある．結局僕が東北大にいる間は実現しなかった（2年目，割と惜しかったけどね）．ただ，去年まで所属していた，東北大の suzukaze_Aobayama というチームが，今年もメンバーを替えて存続しており，めちゃくちゃ強くなっているので，今年はあり得るんじゃないかと思っている．夢の代走をさせるなんて情けない話だが，全力応援するのでアジアではぜひ頑張ってほしい．

年を取るにつれて，感情を大きく動かせるイベントが少なくなってくるように感じる．だから，期待と不安が混ざった吐きそうなくらいの緊張とか，大勝ちしたときのキラキラした感情とか，温かい椅子の途方もない無力感とかといった，ICPCがくれた思い出は大切にしたい．

5年間楽しかったです．今までチームを組んでくれた人たちには特大の感謝をしています．
競プロ自体はちまちま続けていくつもりです．今後はスタッフか何かとしてICPCに関われたら良いなと思います．

TUPC2023 感想

東北大学プログラミングコンテスト TUPC2023 を 2024/03/09 に開催した．公開が遅くなってしまったが，準備の裏話や，問題と当日の感想を書く．

準備について

夏頃に運営の募集をかけた．今年はwriterとして，去年からの僕，仮の人君，とりゐ君，milkcoffeeさんに加え，Dispersionさんとnonon君の計6人が集まった．Dispersionさんは一昨年のTUPC2021ではwriterをしていたので，新顔は1年生のnonon君．人数が増えた分，問題が集まりやすくなってよかった．
それから半年以上時間をかけて準備を進めた．運営陣のほとんどが学部4年生以上で，それぞれ本業が忙しかったりするので，これくらい余裕を持って進めるほうが楽である．また，時間をかけて問題を熟成させたほうがクオリティが上がることは間違いない．

準備は非常にスムーズに進んだ．TUPC2021から蓄積してきた作問ノウハウに加え，去年のオンサイト運営の経験もあったので，特に何も困らなかった．

去年の反省点を鑑みて，いくつかの変更や改善を試みた．去年の一番の失敗は難易度予想を外しまくったことだったので，今年はちゃんと各testerが初見のときの気持ちを重視して難易度評価をするようにした（本当？少なくとも僕はそうしたつもり）．また，コンテスト時間は5時間にした．さらに，難しすぎて緑〜黄くらいの人が終盤暇になってしまう（去年そうだったのかは知らない）という点に対処するために，いくつか部分点をつけてみた．

超強い全体testerの方々だけでなく，一般人（失礼）の感想も調べるために，サークルからsuo君，ripity君，tanaka2_55君を呼び寄せて走ってもらった．手頃な部分点がいろいろあるおかげで，暇にはならなさそう，という感じだったので安心したが，本番では果たしてどうなるか......？

ところで，AtCoder上のTUPC2023のトップページにはTTPC，OUPCをまねて虹色marqueeを配置した．クリックするとなんらかのエフェクトが起こるのが恒例なので，我々はクリックする毎にサイズがランダムに変動するように仕掛けた．大きく育ててツイートをしている人を見ると，作りがいを感じる．

問題について

今年は共同作問や魔改造が多かったと思う．今までのTUPCでは，解法まで出来上がっている状態でテスターに共有することがほとんどだったが，今年は解けてない原案も積極的に共有されていた．

僕がwriterを務めたE, G, H問題の話が主になるが，他の問題もtesterやsolverとしての感想を書きたいので書いちゃう．

A - Namboku / Tozai Line

東西線の西端である八木山動物公園駅は，「日本一標高が高い地下鉄駅」として有名である．

B - 012 Grid

testerをした．超難しく，自力で解いていない．経路問題になってLGVを使いそうということはなんとなく分かるが，そこから先の議論が鮮やかで，めちゃくちゃおもしろい．
B問題から難しくて申し訳ないが，ランダムシャッフルしたらこうなったので仕方がないのです．

C - Topological Sort

testerをした．設定も解法もシンプルで面白い．僕はかなり難しいと思った．ARC-BとかCに置かれていたらかなり詰まりそうな感じ．

D - Shift Puzzle

数時間かけて自力で解いた．3点の回転で2点swapができるのめちゃくちゃ面白くないですか．実装はちょっと大変．

E - And DNA

writerをした．下の桁から考えていくのは典型的で，それが結構うまくはまる．

問題文が回文の問題を作りたいと思い，問題名が生えた．DNAみたいなはしごを描いて，数字とか&とかを適当に配置することで設定を生んだ．

ところで，この問題みたいに行列累乗してトレースを取るという操作は，統計力学の「転送行列法」っぽさがある．卒研が統計力学なので統計力学を結構勉強したが，いろいろ競プロに応用できそうなテクニックが眠っていそうな雰囲気を感じている．

F - Hotel

このセットでは唯一ABC-likeな問題だと思う（writerもそれを意識して作ったらしい）．題材が面白い．

G - Min Nim

writerをした．回文シリーズ2．これも問題名から設定を生やした．実験をしたところ，Nが奇数なら先手が必ず勝てることがわかった．理由を考えると，偶数のときの解法もわかる．

これは人によって難易度評価がかなり違った．速い人は2分で解いたけど，詰まってしばらく解けなかった人もいた．僕自身は緑くらいだと予想していて，結果的には的中した．

H - Count Pseudo-Palindromes

writerをした．回文シリーズ3．これは回文というテーマから設定を生やした．K問題の101点を除いて，予想難易度が一番高いボス問である．本番も1ACだった．

僕は問題設定と計算量の悪い解法だけ生んでtesterに投げたら，気づいたら線形時間になっていた．この問題は，チーム作問がかなりうまくいった例だと思う．

準備はひじょ〜〜〜に大変だった．作問の背景を話す．

去年の春に，擬回文の存在判定の問題を考えた（1からXが1つ，X+1からX+Yが2つずつ現れる，というふうにすると非自明になる）．僕はそれをdominator treeに帰着させることでO(N (log N)^2)で解いた．判定問題だと嘘解法がいろいろありそうなので，数え上げにしたいなあと思っていたが，よくわからずしばらく放置していた．秋頃に考え直したところ，すごく頑張ると解けることがわかった．dominator treeはやっぱり使う．実装がライブラリを除いて200行を優に超えるような大変な解法である．まあ有志コンのボス問としては許されるだろうと思って準備を進めた．
しばらくこれが唯一の解法だったが，年が明けてから新しい解法がいろいろ提案された．とりゐ君が天才考察によりO(N)の解法を見つけてそれが想定解となったほか，仮の人君，Dispersionさん，こたつがめさんが O(N√N) や O(N log N) で解いた．人によって解法がかなり違っていて面白い．
O(N)で解けることがかなりすごいので，制約を大きくすることで O(N)を強制しようとしたが，O(N log N)はともかくO(N√N)も爆速で落とせそうになかった．O(N)解法はハッシュマップを使うので定数倍があまり良くないというのもある．それでも，O(N)解法に少しでも考察量を近づけるために，擬回文の中心ごとに個数を数え上げさせることにした．これで難易度がだいぶ上がったと思う．
それでもちゃんと全体testerのhenoさんには解かれて，やっぱりすごいなあと思った．

本番では，4時間経過しても0ACだったので，ACが出ることをほとんど諦めていたが，唐突にhamamuさんがACを取ってびっくり仰天した．それも，計算量の悪い解法をひたすら高速化する感じではなく，多分想定解に近い考察がなされていた（？）ので，すごい．なんなら想定解の実装より短くて高速．0ACだと悲しいので，ACが出てとても嬉しかった．

I - Maximize Array

セットの中では簡単枠だけど，ちゃんと考察が要求されていてそこそこ難しいし面白い．

J - Colored Complete Graph

testerをした．インタラクティブとしてめっっっっっちゃ面白い問題だと思っている．まず2N回でできるというのが驚き．僕はしゃくとり法みたいな方針で考えて，整理すると想定解と一致した．あとで「赤の連結成分数＋青の連結成分数を減らす問題と捉えると筋が良い」と聞いて納得したが，このレベルの理解を短時間でできたらすごいと思う．

僕は橙くらいあると思ったんだけど，かなり解かれて水くらいになった．

K - (mod HW+1)

100点 (mod N^2+1) の方は2時間くらいで自力で解いた．合成数のときはほとんどできないが，1個だけ例外があるというのが面白い．素数のときの構築も楽しい．101点は，解いていません．100点の方は普通に解かれると思ったが，結局誰にも解かれなかった．

L - Random Mex

nonon君が原案．提案時の想定はO(NM)のDPだったが，tester陣により魔改造された．FPSで殴ると，Stirling数を含むかなりきれいな式が得られる．組合せ論的な解釈を考えると，公式解説にあるような議論が出てくる．ただこれをいきなり思いつけるかと言われると無理なので，実質的には式変形を頑張る感じの問題だろう．

M - Vivid Colors

testerをした．2次元の問題に落とし込むというところまではすんなりわかったが，実装があまりにも難しい．誤差が怖かったのですべて整数で扱おうとしたら，複数の点が同一直線状に乗るときに壊れまくるらしくて永遠に答えが合わなかった．浮動小数点数で雑に処理したら逆にうまく行った．ユーザ解説参照．

テストケースづくりが大変だったみたい．他のtesterがたくさん嘘解法を提案してくれて，それらを落とすのが難しかった．焼きなましでテストケースを作ったらかなり強くできたみたいで，すごい．

N - Do Not Turn Back

testerをした．サークルで雑談をしているときに，「この問題ってどれくらい速く解けますか？」とnonon君に出題されたので，その場に一緒にいた仮の人君と考えた．制約無しで問題を考えるのって結構難しいんだよな．戻らないという条件がない場合はO(N^3 log K)より速くなることはないと思っていた（実は速くなるらしい！後述）ので，これにどれくらい近づけられるかが問題．結局，同じO(N^3 log K)まで計算量が落ちてびっくりした．行列の3項間漸化式ってはじめて見た．すごく面白かったのでTUPC行き．BMBMを使うと2乗になるらしい．

O - 0100 Insertion

testerをした．解けていない状態で原案が共有された（もとは0010で，判定問題）．サンプルをいくつか作って数時間睨むとすごい条件がエスパーできて，証明もうまくはまる．
考察を積み重ねて解く感じではなく，見えるか見えないかみたいな問題でしか得られない栄養素がある．個人的にはこのセットで一番好きな問題．

0100に反転することで難易度が大きく上がると思っていたが，これをコンテスト中に唯一解いたHemimorさんは結構違う方針を取ったらしくて，0010でも0100でも難しさが変わらないらしい．20分くらいでわかったと聞いて驚愕した．

P - Sub Brackets

testerをした．一番contestantの反応が良かったように見える．面白いですよねえ，これ．最大独立集合になるところまでわかって，そこからどうすると考えたときに，グラフが二部グラフになっていると気づいたときは感動した．どこにも二部グラフ的な構造は明示されていないのに，都合よく二部グラフになってくれているのがあまりにもきれい．

当日，オンサイト会場について

内職をするつもりだったが，順位表が気になりすぎて5時間張り付いていた，って去年も同じこと言っていたな......．張り付いていました．

序盤の解かれ具合が想像よりだいぶ遅くて焦った．難易度シャッフルがあるせいだろうか．
時間が経つと，想定に近いAC数順に落ち着いてきて安心．
4時間経っても，H, K, MにACが出ていなくてちょっと不穏になってきた．毎年，「すべての問題にACが出るが全完は出ない」を理想としてきて，実際に達成してきたが，今年は0ACが3問も出てしまうのかと心配した．ただそこからH, Mが解かれた（本当にすごい）．一方Kについては，101点は端から期待していなかったが，100点すら出なかったのは驚き．まあ全体的には耐えたかな〜という感じ．

終了後，difficultyを算出して予想と比較した．解説スライド*1に載っているので見ていただきたいが，多くの問題でめちゃくちゃ正確に予想が的中していて驚いた．去年の反省が効いていて良い．大きく外したのはJ (過剰な見積もり) とD, K, M, O (過小な見積もり) くらいで，それ以外は±100くらいに収まっている．

終了後の懇親会で参加者の感想などを聞いた．問題がおおむね好評でうれしい．あとは，部分点をつけたおかげで暇にならなかったという声も聞いて，狙い通り．

最後に

僕は今月で東北大学を去るので，TUPC2023がpuzzleknotのメンバーとしての最後の活動であった．いろいろ言いたいことはあるが長くなるので，非常に感慨深いとだけ述べておく．

皆さんご参加ありがとうございました．
puzzleknotのスタッフの皆さんと全体テスターのhenoさん，ありがとうございました．

来年もTUPCにどうにかして関わりたいので，運営陣にまぜてください．

*1:https://docs.google.com/presentation/d/1QuJ0Hz8VG_Ll7p0op5FTi1J-6y1MKUeNlkBqL6J0WTU/edit#slide=id.p

JAG 夏合宿 2023 参加記

9/16〜9/18 に国立オリンピック記念青少年総合センターで開催された JAG 夏合宿 2023 に参加した．

jag-icpc.org

Day 0

高速バスで仙台から東京に移動．合宿参加費 <<<<<<< 交通費 (安くしてくださってありがとうございます)

Day 1

12時半ごろにオリンピックセンターに到着．建物がめちゃくちゃでかくてびっくりした．

参加者は思ったより多くて60人くらいいた．色々な大学から人が来ていた．自己紹介のあとチームを組んだ．ICPC チームの suzukaze_Aobayama からは僕と仮の人くんが来ており，一人足りない． houren さんがチームに加わってくれて，チーム Aobayama_rHAPsody が結成された．

この日は 14:00-17:00 の3hコンテスト．全11問．韓国の国内予選2022で使われたセットらしい．

https://www.acmicpc.net/category/detail/3217

当日の順位表が見つからなかったのでどういう順番で解いたのか覚えていないが， 僕は CEGJ を解いた．CEは簡単，Gはチームメイトが考察していたのでそれを聞いて実装，Jは難しかったが頑張った．Jは面白かった．平方分割の方針で考えても何を平方分割すればうまくいくのか見えづらいし，うまく平方分割したあともそのあとどう処理すればいいのか結構考える必要がある．解けてかなり達成感があった．

結果はたしか7完？で順位は覚えていないが1桁の悪くない順位だった気がする．

解説を聞いた．HIが不可能でやばかった．韓国の国内予選ってこんな感じなんだ．この問題数を3hでやるのは大変そう．

その後部屋に行った．ルームメイトと話したり風呂に入ったりABCに出たりした後12時に寝た．次の日の朝は早い．

Day 2

7時起床．10時から5hコンテスト．この日は有志セットで，全12問．この日も Aobayama_rHAPsody で参加．

yukicoder.me

僕は後ろから見て行って，Kでそれっぽい解法が生えたので実装した．ただ投げても投げても通らない．チームメイトに救助を要請すると， (a, b) が unique でないときに壊れていることが指摘される．勝手に (a, b) が unique と仮定してしまい，それでしか動かない解法を考えてしまったので振り出しに戻ってしまった．ところがすぐに houren さんがいい感じの解法を生やしてくれたので実装して AC．5ペナも吐いてしまって申し訳ない．

Kで悪戦苦闘している間にチームメイトがACHを通していた．また，Kを通したちょっとあとにBも通る．

Dが解けた気になったので実装に移る．かなり面倒なことをする必要があって， houren さんと話しながら丁寧丁寧に書いていった．オイラーツアーを取って区間加算区間 min を頑張るのが解法だが，遅延セグ木を使いたくなって絶望していた．ここで，平方分割でサボれないかと指摘され，それを採用することに．遅延セグ木を平方分割で代用するみたいなコピペなしコンテスト特有の発想がなかったので，これはかなり勉強になった．めっちゃしゃべりながら実装したおかげでいろいろ整理できてスムーズに実装できた．チーム戦のいいところ．サンプルがあったので提出すると，一発でAC．特大のガッツポーズが出た．

それ以外は解けずに6完7位で終了．この日も悪くない順位を取ることができた．KでやらかしたがDで取り返せたのも満足．

解説を聞いた．なんかいろんな意味ですごい問題だらけだった．コピペなしのコンテストで重み付き一般マッチング想定が出たのにはさすがに笑ってしまった．

飯を食べて風呂に入って部屋に戻る．ARCまで1時間半くらい時間があったので，ルームメイトと大富豪をやった．久しぶりに大富豪やったけど楽しすぎる．潜伏して tourist 出しする人がいてウケた．僕は基本的に貧民をやっており，資本主義の残酷さを思い知らされた．

9時からARCに出る．いつもratedコンテストのときは耳栓をしているが，今日は持ってくるのを忘れてしまったという話をしたら，ルームメイトが大量に耳栓を持ってきていたので1組譲ってもらった．この日の配点は 4-6-6-7-7-8 というなんともやばそうな配点でビビっていたが，結局Dまで解けて暖まったのでうれしい．Dがかなり面白いと思った．

ルームメイトと軽く感想戦をするなどしたのち12時に寝た．

Day 3

7時起床．9:45から5hコンテスト．JAG セット．11問． Aobayama_rHAPsody.

ABが簡単らしいので，Aをチームメイトに任せてBを見る．すぐ解ける．

その後，後ろから問題を眺めていった．IJにACが出ていたので，僕はJを見に行く．グリッドでうまく動いて，パス上の文字列を並べたものと目標の文字列の編集距離を最小化する問題．編集距離の気持ちになると，グリッド上の位置と，何文字一致させたかの状態を持ってDPすれば良い事がわかる．遷移がDAGじゃないので，01BFSをする必要があるということにちゃんと気づけて，AC．

その後チームメイトがCとIを通す．偉すぎる．

Eが解かれているのでEを見る．余事象を考えると，出現した数字の集合が常に区間になるようにすれば良いことはすぐ思いついたが，立式が下手すぎて計算できない形にしかならなかった．仮の人くんに見せたらいい感じに整理してくれて，実装してもらいAC．

Kを見ていたら解けた気になる．ある頂点に行って戻ってくるという操作の性質に気づいて，頂点数の偶奇とパスの偶奇を考えれば，動的なグラフで連結性判定と二部グラフ判定ができれば良いとわかる．Offline dynamic connectivity を写経してサンプルを合わせて投げるが通らない．チームメイトにも考えてもらい，解法の正当性を検討してもらったが，考えれば考えるほど正しい．全然わからないので諦めて昼飯を食べていたら，連結性判定がバグっていることに唐突に気づいた．UFで二部グラフ判定をするときに頂点倍加をするので，そこで連結成分のサイズをみるような連結性判定が壊れていた．直したら AC が帰ってきて大喜びする．

他に解かれているのがHしかないので見る．k=1の場合はトライ木で処理できることにチームメイトが気づき，あとは平方分割して大きいやつをロリハ，小さい方をトライ木で処理できることがわかった．制約とTLに対してこの解法の計算量が重すぎるので通る気がしなかったが，ダメ元で書いてみる．サンプルを合わせて投げたらなんか通ってしまって，チームが沸いた．

残り1時間位で，残りの問題を考えてみたが全然分からなかった．

8完4位で終了．最終日にとても良い結果が出て良かった．即席のチームだが，3日間を通してチーム全員が結構貢献できたのでとても楽しいチームだった．

解説．HのTLを2secにするか2.5secにするかで迷い結局2.5secにしたらしい．2secと2.5secの間に入ったチームが1つあったと聞いて我々のことかな？と言っていた．解けなかったDFGのうち，DGはかなり大変そうで，Fは思いつきたかったな〜という感じの面白い解法だった．

解説後に解散．東北勢と夜飯を食べて深夜の夜行バスで帰った．

最後に

3日間でAtCoder含め計16時間40分のコンテストに出るというハードな体験だったが，面白い問題が多くとても楽しかった．また，多くの競プロerと知り合えたのも楽しかった．

夏合宿を開いてくださったJAGの皆さんには感謝しています．とてもいい思い出になりました．

来年は，国内予選を通過した状態で参加したい．

ICPC2023 国内予選 参加記

チーム suzukaze_Aobayama (milkcoffee, karinohito, sotanishy) で，ICPC2023 国内予選 に参加した．

このチームは，今のメンバーでは2年目である．そして，milk さんの参加資格が今年で最後なので，このメンバーでやれるのは今年が最後になる．

コーチはこたつがめさんに担当していただきました．ありがとうございます．

目標は国内5位 & 学内1位．

本番前

今年の国内予選はコロナ以前のルールに戻った．PC1台ライブラリ写経ルールは去年のアジアのときに練習してある程度慣れていたので，そこまで心配はしていなかった．

本番1ヶ月前から毎週チーム練を行った．流石にICPC4年目だと，国内の過去問は一通り走ってしまっているので，Codeforcesのgymにある海外regionalを適当に選んでバチャをやった．

6/24の模擬国内では 6完，ゲスト除いて3位 (!) という好成績を収めた．遅い愚直を回している間に他の問題の実装をするといったような，国内予選特有の立ち回りがうまくできた．3位なんてまぐれでも取れると思っていなかったので，やばい！

本番1週間前に，模擬国内2018のバチャをやった．本番2位相当 (!) の結果だった．このチーム，強いぞ．

本番2日前に，模擬国内2020のバチャをやった．信じられない冷え方をした (通過できないレベル)．ちょっと不穏な空気が漂う．

本番前日．いくつかAOJ-ICPCを解いたり，ライブラリを追加したりした．早めに就寝．ICPCが気になりすぎてあまり寝付けなかった．

当日

10時頃起きる．研究室に行って院試の研究計画書を書いていた．あとは研の同期に順位表のスクショ撮影をお願いしておいた．

14時頃，参加場所である別の研究室に移動してチームメイトやサークルメンバーと合流．場所を決めたり印刷についての取り決めをしたりした．あとはリハーサルの問題を解く．JKLが終わったのが終了10分前．Mの鎖中経路10分実装チャレンジが始まった．毎年これやってるから，もう問題文見なくてもコードがだいたい書けるくらいなんだけど，10分は，無理．幾何ライブラリの写経でほとんど終わり．

本番まで1時間半ほど微妙な時間がある．エナドリとお菓子の買い出しに行ったり，同じ部屋にいたチームや，見に来てくださったこたつがめさんとホスフィンさんと雑談したりしていた．

↓ これ見て爆笑してた．

適当にAOJの簡単な問題を解こうと思い，250点の Leaky Cryptography を開いた．問題文の読解にかなり時間がかかり，理解して実装したあともサンプルが全然合わず，チームメイトに助けて〜って言っていたらそもそも10進数から16進数への変換のところがバグっていることに気づいた．脳が死んでいる．なんとかAC．

開始10分前くらいになると流石に緊張が高まってくる．もうICPC4年目だけど，いつまで経っても緊張するんだね．

本番開始

A (AC 3:26)

僕がAをやる間に，問題文が届き次第チームメイトが前から適当に考察を始めるというのが初動．Aは問題文も短いしやることも簡単なのでいいね．かなりスムーズに実装できてすぐにAC． FA行けたんじゃね？と思っていたら 3rd ACだった．FAは同じ部屋にいたAobayama_doctors．FA取る！って宣言してまじで取っていてすげ〜．

ラボの同期くんが撮ってくれた

B (AC 18:51)

Aをやっている間に kari くんが考察できていたらしいので任せる．通る．

kari くんがBをやっている間，milk さんがC，僕が D を読む．何もわからん．

C (AC 32:12)

Bが終わった時点で，milkさんが一緒に考察したいと言っていたので，Dを kari くんに渡して僕はCに合流．

もういかにも天才構築って感じの設定で，こんなのがCに出るの怖すぎ〜と言っていた．方針が立たなくて唸っていたら，milkさんが「偶数行を n/2, 偶数列を n/2 ずらせばいける？」とつぶやく．これはいかにも正しそうで，すぐに頭の中で証明ができたので，パソコン席に座っていた僕が実装に飛びつく．念のため丁寧にassertを書く．O(n^2) でassertするのだるくね？思って制約を見に行ったら n <= 50 だったので甘えて O(n^4) でassertした．assertのほうが実装が面倒で，そっちを主にバグらせていた．assertのバグが直ったら，構築部分のバグが発覚し，assert書いてよかった〜と思った．テストケースも全部assert通ったのを確認して提出，AC．

これきれいだよなあ．これをすぐ思いついたmilkさんめちゃくちゃすごいんだよな．

Cがかなり速かったおかげで，この時点でかなり上位だったみたい．

毎年，Cまでは爆速なんだ．問題はここから．

D, E, F

Dをやっていたkariくんの方は，解の上界がかなり小さいので全探索できるという方針が立ったらしく，実装を任せる．その間，僕がE，milkさんがFを読む．

Eは，DPをデータ構造で高速化するような見た目をしているが，制約的に変だなと思っていたのでもっといい感じの方針を探る．てか各ケース n <= 6000 で，データセット全体でのnの総和が 1e5 ってなに？2乗で大丈夫なんですかね．logつけたらやばそう． (←国内だと余裕なんだよな〜なぜその発想が模擬国でできて本番でできない）

まず数字が1種類しかなかったら最長減少部分列を取ってくれば良いから，それをいい感じに2次元に拡張できないかな〜と考えていた．単にペアの最長減少部分列を求めると，午前午後両方変える場合が扱えなくて厳しい．午後をDPで固定して午前でLDSをやるとかも考えたけどあまりいい感じにならない．

その間にFのいい感じの考察がmilkさんから降ってきたので．そこから2人で考察を発展させる．「凹んでいるところの両側の辺が一直線上にあり，かつ図形の反対側に平行な辺がある」が条件になると考えて，正しそうということになった．しかし，良い感じの実装方針がぱっと思いつかず，かなり沼る予感がしたので，DEを解いて時間が余ったら戻ってくることにした．

（この考察，嘘だったな．反対側に平行な辺がある必要はない．）

Dが結構バグっているらしく kari くんが格闘している．やばそうなので見に行き，ラバーダックになっていると，どうも話が噛み合わない．すると kari くんの誤読が発覚した．使う数字の総和が n にならなければいけないという条件を見落としていたらしい．これ見落とすのは仕方ない感じがあるな......．でも直せるらしいので再び任せてEの考察に戻る．

Eは2次元DPの方針が立つ．午前，午後の値をキーに持ち，最後の値をキーに一致させるのに必要な最小の操作回数を持たせる．3乗に見えるが，午前午後両方変える場合は午前をできるだけ大きくして損しないので，結局更新すべき状態は O(n) 個しかないことがわかる．これで全体で O(n^2) になる．でもこれ実装したくねえな〜場合分け書きたくねえな〜と思う．

その間，Dのサンプルがあったらしいので投げる．落ちる．かなりやばい雰囲気が漂う．Eを離れてDの鎮火に向かう．

D (AC 2:06:17+3ペナ)

再びラバーダックになる．途中まで説明を受けた段階でかなりやばそうなところが見つかる．コードを口で他人に説明するの，まじで大事．直したら diff が出たので投げるとまた落ちる．

全体の説明を受けてから提出すればよかった．焦りが出ている．コードの続きを説明してもらう．すると怪しそうな枝刈りが見つかる．それを消して再び実行．かなり遅いが，各ケース10秒も待てば出力が得られることを確認し，最後まで走らせる．するとdiffが出ますね〜．コード全体がいい感じになっていることを再確認し，提出．Correctが出たときは本当にホッとした．2ケース目も通り，Congratulations!

Dの全探索がすぐに見えたkariくんかなり天才なんだよね．僕は何も分からなかったので．ただ丸投げしたのが良くなかった．チーム戦をするべきだった．


E (解けず．2WA)

残り1時間．流石にEをやるかな．例の2乗DPを実装する．丁寧に場合分けしながら実装．O(n^2) のDPテーブルを持って，O(n) 個の状態だけ更新する．遷移元も O(n) 個しかないので計算量はいい感じだが，僕の取った方針だとかなり場合分けが大変になっちゃう．実装してしばらくデバッグすると，サンプルが合う！テストケースを実行．2乗だと結構遅いんじゃないかと思ったけどほぼ一瞬だった．投げると落ちる．これが終了15分前くらいだっけ？みんなでデバッグするためにコードを印刷しようとしたが，印刷されない．リハーサルのときも印刷されたりされなかったりでよくわかんなかったんだよな．仕方なくパソコンの画面を全員で覗き込む．コードを見返すと，考慮し忘れていた遷移を見つけたので実装．もう残り2分くらいなので，急いで提出．また落ちる．もう一度コードを眺めていると，見落としている遷移がもう一つあることに気づく．さっき直したところと同じようなところだったので，最初からこれも気づくべきだった．でももう残り10秒とか．無理だね......．

終わり．


本番後

恐る恐る順位表を開く．29位．Tohoku の文字列を検索する．suzukazeの上に2個あるね......でもギリギリ3チーム通過圏内だったりしない？僕らより上の東大をみると，どこも落ちてないじゃないか！東工大が2つ落ちている (1つはホスト枠で通るけど) ので，それを除くと27番目か．3チーム通過のためには25番に入る必要があるんだよね．

え？

かなり信じられなくて，現実感がないふわふわした時間がしばらくあった．

どうしようもないので別チームと一緒に感想戦をする．1年生チームのrnnの，Eに対する考察を聞いて大声が出た．操作回数をキーに持って，達成できる最大のペアを持てばいいんだね．これも結局 O(n^2) で計算量は変わらないんだけど，見通しの良さが格段に違う．かなり衝撃的だった．

Aobayama_doctorsはDをかなり速く通していてすごい．その後Fをやっていたらしい．かなり正しい考察をしていたっぽいが落ちたらしい．あれを実装しきれるのすごいな．

東北大通過2チーム目の Aobayama_primes は，正直完全にノーマークだった．最近黄色になった suo くんのチーム．Dが速くて，強い．

その後軽く打ち上げに行った．帰宅に失敗．逆方向の終電に乗っていた......．結局ネカフェに転がり込んで夜を明かし，始発で帰った．

振り返り

チーム戦をしなかったのが良くなかったんじゃあないかなあ．Dとか考察をまともに聞くことすらせず何もかも丸投げしてしまった．バグって苦しいのを1人で長い間戦わせてしまったのは本当に申し訳ない．

あとE，1時間あれば通さなきゃいけないだろう．はずれ方針とはいえ，1時間あれば実装しきれるはずのものだった．

未練しかない．どうすればいい？

本番終了後は現実を受け入れられずヘラヘラしていたけど，一晩経ってこれ書いてたらもう終わったことが理解された．

とにかく，国内通過した Aobayama_doctors, Aobayama_primes，おめでとう．アジア頑張ってください．全力で応援します．

チームメイト，お疲れ様でした．ICPCはこんな形で終わってしまったけど，2年間一緒にICPCできて本当に楽しかった．チームとしてはこれで終わりじゃなくて，また有志コンとか出たいね．

今まで4年間のICPCを通じてありとあらゆる感情を経験した．今年は未練しかない．

TUPC2022 感想

東北大学プログラミングコンテスト (TUPC) 2022 を 3/4 (土) に AtCoder で開催した．僕は writer，運営としてコンテストに関わった．

atcoder.jp

この記事では，TUPC2022 の各問題について，僕視点の感想や裏話を書いたり，当日のオンサイト会場の感想などを書く．準備の記録などもあとで別の記事を書くかも知れない．

問題について

多くの問題が好評を頂いたようで，とても喜んでいる．また，全部の問題にACが出たのも嬉しかった．

ただ，時間に対して難易度が高すぎるという意見もたくさん頂いた．また，序盤から難しく，初心者にはかなり厳しいセットになってしまったことは否めない．これは，運営陣の難易度評価が完全にバグっていたからであり，申し訳ないと思っている*1．この辺の課題は次回には直したい．

問題順序は，writer 4人 + 全体 tester 2人 の6人で，各問題について difficulty を予想し，その平均を取って昇順に並べた．分散がかなり大きかったが，平均は正しい値になるだろうと思っていた．しかし，全然そんなことはなかった．

A - Sum Sort

いい感じの簡単枠だと思ったが，それでも結構難しかったらしい？

B - Snowy Aobayama

東北大ネタが1問くらい欲しかったので，ちょうどよい．

C - Flip Grid

解く前に解法を知ってしまい後悔した問題の一つ．AGC-Aとかにありそうな感じ？

D - Zeta Sum

tester をした．式の見た目がやばすぎる．展開してシグマを5重にするのはためらわれたが，勇気を出してやってみたら見掛け倒しで面白かった．この見た目を D に置くのはちょっと渋ったが，解法の難易度的には妥当だと思いここに置かれた．結局 D にしては厳しすぎたかも？

E - 00-11 Rotate

解く前に解法を知ってしまい後悔した問題の一つ2．解説の証明を考えた．AGC-B とかにありそうな感じ？難しいとは思っていたけど，ここまで解かれないとは思わなかった．

F - Block Rotation

writer をした．題材は「万華鏡」．2回の操作で形が揃うことと，サイクルに分解できることに気づくのがちょっと難しい？実装は，やることが多く，想定解も 100 行近く行ってしまった．とはいえ，添字を合わせたり場合分けを頑張ったりみたいな辛さはないので，実装難易度自体は高くないと踏んでいた．ところが思ったよりも解かれず，G, Hと逆転してしまった．

G - All Pairs

tester をした．考えていてかなり楽しかった．どこに辺を追加するかが本質．

H - Next Permutation

tester をした．階乗進数で足し引きが簡単にできることに気づいて，かなり感動した．階乗進数を見たことがなかったので，とても面白いと思った．僕は結構難しいと感じたが，思ったよりも解かれた．

I - Count Setwise Coprime

tester をした．僕は解法2の Mertens 関数を用いる方法で解いた．数論関数の累積和を知らなかったが，いろいろ調べたら 3/4 乗や 2/3 乗で解けることを知って勉強になった．解法1はかなりきれいだが，これは思いつかないよ......．

J - AMidA

最初，writer から「サイクルを分裂させるクエリと，2頂点が同じサイクルに属するか判定するクエリを処理する方法で，削除可能 union find よりも良い方法はあるか？」と相談をされた．調べると，グラフが森なら decremental connectivity が逆マージテクで解けるということが Wikipedia に書いてあった．これ自体かなり面白く，勉強になった．そしてこの方法がサイクルにも応用できることに気づき，この問題の構築部分の解法となった．

その後，問題自体も解いてみた．予め，サイクルを分裂させればいいということを知っていたので，割とすんなりと解けてしまった．実際は，そこに帰着すれば解けることに気づくまでが一番難しいので，自力で解けたとは言えないかも知れない．

サイクルを分裂させれば解けることも，それが逆マージテクで処理できることも面白く，かなりの良問だと思った (問題名も面白い！)．思ったよりも解かれなかった．

K - Lebesgue Integral

writer をした．実は去年の TUPC2021 B - Minimum Upper Sum は， Riemann 積分を離散化したつもりの問題だった．そこで， Lebesgue 積分版でも作ってみようと思ってこの問題ができた．

高度典型やるだけ枠を出すのはちょっと申し訳ない気持ちもあったが，1問くらいあってもいいかと思って出した．最近 Universal Cup かなんかで Monge が出たらしく，Twitter で話題になることが多かったみたい．

橙中位くらいの難易度だと推定していて，実際そうなった．今回のセットで，難易度推定が正しかった数少ない (唯一の？) 問題だったかも知れない．

ところで，Minimum Upper Sum はめちゃくちゃ難しいのに Lebesgue Integral は (計算量が良いという意味で) 簡単なのだが，これは Lebesgue 積分が Riemann 積分よりも良い性質をいくつか持っていることと関係があったりするのだろうか？

L - Inversion High and Low

tester をした．最初，N=500で質問回数4000回だったのだが，マージソートの比較回数をちゃんと評価したら3990回くらいでギリギリ間に合ったので，N=100で質問回数500回になった．N=100のときの比較ソートの比較回数の情報理論的下界が 525 回なので，マージソートだとどうやっても無理になる．=の情報を必ず使わなければいけないというのが，理論的にも結構面白いポイントだと感じている．

実は自力で解けていない．最初，想定解よりも比較回数が少ない解法 (マージソートベース) を得意になって喋っていたが，あとになってすべて真っ赤な嘘だったことが発覚した．その後も，=の情報をうまく使うように工夫して，クイックソートを使わない別解をずっと考えていたのだが，全然思いつかなかった．比較回数自体が減らせても，比較の基点を取るためのクエリが増えてしまい，結局全クエリ回数が500回を超えてしまう．全体 tester や，本番中に解いた人は非想定解法で解いたようだが，彼らも結局クイックソートをしていた．マージソートを頑張る方針だとどうやっても無理なのだろうか．

この問題の準備中に，ARC にインタラクティブなソート問題 (ARC154 - D) が出て，ちょっと冷や冷やした．

この問題は本番中，最後の方まで解かれなかった問題だった．終了10分前までACどころか提出すらもほとんど無く，このまま終わってしまうのかと思っていたが，ぎりぎりで1チームだけ通してくれた．writer 陣が集まってジャッジを見守っていたが，ACの緑文字が見えたときには一同が湧いた．

M - Fractal Tree Isomorphism

writer をした．「木 (植物) はフラクタル」という話がある．木以外にも，フラクタルは自然界にあふれている．このことをなにかの本で読んでとても面白いと思い，木 (グラフ理論) でもフラクタルを作ってみることにした．木の有名問題を fractal tree に置き換えるだけなので設定はいくらでも考えられるんだが，同型性判定の解法が面白くなったのでこれにした．

自分は，まず同型になるようなサンプルを作ろうと思ったら問題が解けた．fractal tree が同型になるような木のペアは，同じ繰り返し単位を持つような2つの木を持ってくれば作れる．すると，これが必要条件になっているとエスパーできる．

直感的には正しそうだが，証明はかなり難しい．僕は，fractal tree に葉がないことが難しさの原因であると感じた．木の同型性判定アルゴリズムは，hash も AHU algorithm も葉からボトムアップに見ていっているわけだが，fractal tree は根から始めるトップダウンな議論をしなければいけない．証明を考えるのに数日かかった．また，無限集合に関する証明を厳密に記述することも難しい．集合論を思い出して頑張って書いたが，不安だったので数学に強い tester に確認してもらった．

正当性の保証が難しいとはいえ，通すだけなら黄 diff くらいだと思っていたが，あまり解かれなかった．

実は，オートマトン最小化による解法があり，想定解よりも良い計算量になるようである．これは全体 tester にも指摘された解法だが，理解が間に合わずコンテスト当日を迎えてしまった．ちゃんと理解したい．

N - Matrix Game

writer をした．かなりシンプルな条件で判定できる．実験だけでは見えにくい条件なので，考察を然るべきところでする必要がある．一方で，証明が難しいパートがあるので，考察だけでは解けそうにない問題でもある．実験と考察をうまく組み合わせる必要がある．

当初この問題は Matrix Nim という名前にするつもりだったが，一応既出チェックのために調べたら論文が見つかってしまった．問題名を Matrix Game に変えることでお茶を濁したが，結局論文の存在がバレてしまい (検索が上手すぎる！)，しかも既出だったことがコンテスト中の提出から発覚した (Topcoder SRM 793)．SRM 本番中に tourist が 15 分で解いていたんだがどういうこと......．これも論文を見つけたのかな？それにしても速すぎる．

コンテスト中ACのほとんどが論文または既出に気づいたものだったようだが，正面から取り組んで解いてくれたチームもあったようで嬉しかった．

O - Equidistant Binary String

tester をした．超絶難しい．ヒントを貰いつつ解いた．

実装もそこそこ難しいのだが，それ以上に考察のボリュームが凄かった．どうやったらこんな問題がつくれるんだ．そもそも，設定を思いつけたとしても自分で解法を思いつける気がしないので，この問題を自力で解けるのがとんでもなくすごい．

本番で2つACが出てびっくりした．

オンサイト会場について

特に大きなトラブルもなく，時間通りにコンテストを開始できて安心した．

コンテスト中は内職をするつもりだったが，順位表が気になりすぎて結局4時間張り付いて観戦していた．中盤や終盤の問題にも，かなり早い段階でACが出ているのがあってびっくりした．一方で，序盤のACはなかなか増えず，やばいセットにしてしまったかも知れないという雰囲気があった．

個人参加の人が上位に多かったことに驚いた．1人でやるにはかなり重いセットだと思っていたので，個人でどんどん解き進めている人を見て，すごいなあと思っていた．

順位表観戦が楽しすぎて時間を忘れ，気づいたら4時間経っていた．解説スライドを作るに当たり， difficulty を順位表から計算してくれるスクリプトを使って，各問題の difficulty を調べた．予想 diff と実際の diff の差が2色くらいあって笑ってしまった．ごめんなさい......．

解説，講評，観光案内の後，懇親をした．問題が面白いと言ってもらえていい気分になった．ARC書けるんじゃない？とも言われてさらにいい気分になった．書いちゃおっかな〜．

いろいろな人と喋れてとても楽しかった．他大学の競プロ事情とか，社会人の方の競プロ事情とか，直接聞かないと知れないようないろいろな裏話とかを聞けた．

話し込んでいて気づいたら会場を閉める時間になってしまった．懇親の時間を長く取れたので，4時間にして結局良かった気がする (オンライン参加者には申し訳ないけど)．それでも時間が足りなくて話せなかった人が多かったのは残念．

最後に

あおばさんをおばあさんと言っている人は表に出てください．

オンライン参加者含め，参加してくださった方々，ありがとうございました．問題が面白いと思っていただけたら writer として望外の喜びです．

問題準備からコンテスト当日まで本当に楽しかったです．来年もやります．

*1:どれくらいバグっていたかについては，オンサイト会場で使った解説スライドを参照してください．AtCoderの解説タブから見れます

AtCoder 橙になりました

2023/2/12 の AGC061 で念願の AtCoder 橙になりました．

(ABC を除く) コンテスト中 AC の difficulty の自己ベストを大幅更新して色変出来たので，最高です．


各種記録


やったこと

問題を解く

  • 黄を全部埋める
    • いつ達成したか忘れたが，B1 の頃に達成した気がする．(今は B3)
  • 橙を 9 割埋める
    • B1 終わりの春休みに狂ったように埋めていて，このときに半分以上解いた記憶がある．
  • AOJ-ICPC を解く
    • これは ICPC 対策のためにやっていることだが，AtCoder で見る機会が少ないフロー，幾何，構文解析に強くなれる．ABC でこれらが出ると比較的スムーズに解けることが多いが，A[RG]C にはあまり出なくて悲しい

解説 AC については，

  • ABC とコドフォ: しばらく考えてわからなかったら見る
  • ARC と AGC: 基本的に見ない．解けなかったら寝かせてしばらくしたら再チャレンジ

というスタンスでいる．

考察メモをつくる

なにか学びがあるたびに，個人の考察メモに書き溜めている．コンテスト中に参照して役に立ったことはあまりないが，知識を整理したり，定期的に見返して忘れていたテクを思い出したりするのに役に立っている．

アルゴリズム・データ構造を勉強する

たまに気が向いたら Library Checker で解いてない問題を選んでそれを勉強する．結構役に立つものもあるが，マニアック過ぎてコンテストで見たことがないものがほとんど．

また，競プロサークルで最近まで組合せ最適化の輪読会をやっていた (切りのいいところまで読んだので終了)．LP，マトロイド，マッチングなどの話題を知れた．LP もマトロイドも汎用性のある話題で役に立ちそうだし，なにより理論がかなり美しくてとてもおもしろかった．ただ，これもコンテスト本番で役に立ったことはない (過去問埋めでたまに使うことはある)．

また，ABCやエデュフォのボス問はだいたい高度な知識を要する問題なので，たまに解説ACして知識を得ようとしている．

作問する

僕はあまりたくさん作る方ではないが，主に TUPC (東北大学プログラミングコンテスト) のために作問をすることがある．去年の TUPC でも 4, 5 問出した．今年の TUPC でも writer をやっている．

Writer や tester として，ある問題に深く関わると，その問題に使うアルゴリズムとか考え方の理解が深まるというのはあると思う．コンテストでも役に立ったりする．

(ここで宣伝)
3/4 (土) に AtCoder で TUPC2022 を開催します！今年はオンサイトも同時開催です！たくさんの参加をお待ちしています！

サークルに参加する

バチャとか，ICPC 参加とか，TUPC 準備とか，前述した組合せ最適化ゼミとか，いろいろ活動している．

活動内容そのものが競プロに役に立っているという感じはあまりないのだが，サークルを通して同じ大学の競プロ er たちと知り合えて切磋琢磨できるのが，とてもモチベーション維持に貢献していると思う．

かなり幸運だと思っているのは，近い学年に近いレートの人が数人いて，みんな結構アクティブにサークルに参加していること．ライバルがいてとても刺激になっているし，楽しい．

(最近研究室のミーティングとかぶって定例会に全然参加できていなくて悲しい)

感想

2200 周辺で停滞していた1年半，かなり苦しかった......．

ICPC が終わるたびに「来年の予選までには橙になるぞ！」と言い続けて2年，やっと届いた．

コンテスト直後は強烈な達成感，幸福感，解放感，充実感，自己肯定感，第六感，恋の予感，その他任意のポジティブな感情を感じ，全然眠れなかった．

同時に，「本当に自分に橙が務まるのか？」という気持ちもあるので，気を抜かずに行きたい．

これから

今年の目標

  • Codeforces 赤
  • AHC 黄
  • ICPC 国内 + アジアで一桁順位

AtCoder は，どこまで行けるんだろうなあ．とりあえずは来週からの2連ARCで橙を維持するところからですね．