東北大学プログラミングコンテスト 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にどうにかして関わりたいので，運営陣にまぜてください．
