2023 年 3 月 4 日に東北大学プログラミングコンテストをオンサイトで開催しました．その記録です．
コンテストまでのできごと
TUPC2022 始動
去年サークルで TUPC2021 を開催して結構うまくいってたので，今年もやろうという話がずっと前から出ていました．去年の 8 月頃にサークルの slack で TUPC2022 の writer の募集がかかったので名乗り出ました．僕のほかに sota 君と kari 君と milk さんが writer に名乗り出ました．writer のほかに tester としてこたつがめさんが，運営面の手伝いとしてホスフィンさんが加わり，計 6 人で TUPC2022 を運営することになりました．
問題準備
始動してしばらくは問題をひたすらみんなで産みました（9~12 月）．誰かが問題を産んだら，それ以外の 3 人の writer のだれかがまずは問題をチェックするという形式を（基本的に）とりました．各問題ごとの議論とかは discord のチャンネルを生やして行いました．
問題文や解説，コードを共有/保存するのは github で行い，テストケースを作って実際にジャッジするのは rime という機能を使いました．rime を使うのは sota 君が提案してくれたもので，彼が rime の使い方を非常にわかりやすく説明した資料を作ってくれたので作業がスムーズにできてとても助かりました．
合わせて，今年はオンサイトでやりたいねということ，AtCoder を借りてやりたいねという話をすこしずつしてました．
オンサイトの準備
オンサイト開催について，とりあえず Twitter でアンケートを取って聞いてみようということになりました．35 人が「行きたい」に入れてくれており，ある程度人が集まることが見込めたためオンサイトをやる方向で決定しました．
TUPC2022の運営の参考にするため，アンケートのご協力をお願いします．
— TUPC2022 (@tupc_tohoku) 2022年11月23日
3月上旬にTUPC2022をオンサイトでやるとしたら仙台に
オンサイトでやることが決まったら，会場探しをしました．まずは仙台市にある貸会議室を探してみましたがあんまりいいところが見つからず，お金がかかるくらいだったら東北大学の適当な場所を借りてやろうということで，サークルの顧問の先生にお願いして大学で借りれる場所を探していただきました．結果としてこの判断が良く，広い会場を無料で借りられることができました．WiFi も貸していただきました．
AtCoder のサイトの準備
AtCoder のサイトを借りることについて，chokudai さんの過去のツイートをさかのぼってみると，AtCoder で有志コンを開くための条件として ①橙以上が問題をチェックする ②writer/tester が黄色以上 という 2 つを課しているツイートがありました．幸いにも東北大には赤コーダーのこたつがめさんがいてくださるためこれらの条件を満たしており，とりあえず chokudai さんに DM してできるかどうか聞いてみようということになりました．AtCoder 側から，こたつがめさんがいるなら問題ないだろうということでコンテストページをいただけることになりました．
AtCoderで開催可能な最低水準（橙以上が原案についてチェック。黄色以上がWriter/Tester（テスターの場合はデータセットの中身についてもチェック））が満たされてるかちょっと良く分からないので、有志コンが開催可能なのかどうかがあんまり解ってない
— chokudai(高橋 直大)🐙🔥@AtCoder社長 (@chokudai) 2019年4月18日
ただ Atcoder で開催するにあたって，運営陣がだれも Atcoder でバイトをしていないので，問題文を上げたりテストケースを登録したりする方法を誰も知らないという問題点がありました．そこで，昨年 TTPC を開催していて，かつ AtCoder での writer 経験もある tatyam さんにお願いして，テストケースの登録方法とかを 1 時間くらい zoom をつなげて教えていただきました（後で知ったことだったんですが，教えてもらった日が tatyam さんの誕生日だったらしく，人の記念日の貴重な時間を奪ってしまって申し訳ない気持ちに...）．このとき，オンサイトの運営のことについても少し話をしてくれました．tatyam さんのおかげでかなりのことが助かっていて，ありがたい限りでした．
コンテスト 2 ヵ月前～
今年の 1 月中旬くらいにはすでに問題のセットが完成し，この頃あたりから全体 tester のこたつがめさんにも作業をお願いしていました．その時期にコンテスト時間とチーム制限を議論しており，当初私はこのセットは簡単だと思っていたので(え？) 4 時間かつレート制限ありでよいと主張してしました．
1 月 30 日にオンサイトでやることを告知し，conpass での募集を開始しました．私は当初 20 人も集まらないんじゃないかと思っていましたが，これも見積もりが下手で実際のところは 43 名もの方にオンサイト参加していただきました．
コンテスト開催のちょうど一か月の 2 月 4 日にコンテストページを公開し，2 月 5 日から heno さんに作業を開始していただきました．heno さんの解く様子を見ていると，私が見積もっていた問題の難易度がバグっていることに気づき，正気を取り戻しました．今更コンテスト時間を変えるということは難しいので，せめてもということでチーム制限は撤廃されることになりました．
2 月の中旬には，私が名札を作る担当になったので作っていました．TTPC の名札がすごいおしゃれで，そんな美術センス私にはないよ～～とかいいながら，恥ずかしくないような最低限のシンプルな名札を作りました．作った当初はあんまりピンときてませんでしたが，実物を見てみるとまあまあよかったのかなと思っています．
うおおー pic.twitter.com/1cpnvr6yeo
— とりゐ (@toriidao) 2023年3月4日
残りの 2 週間は問題文や解説のチェックをずっとしてました．コンテスト前日にはこたつがめさんが細かいところまで隅々チェックしてくださり，そのおかげもあって（誤読によるものを除いて）コンテスト中は clar が一つも来ませんでした．
コンテスト当日
当日，コンテスト開始までは会場でこれといってやることもなく，適当に人々を案内してたりしてました．コンテスト中は人々の提出や順位表をひたすら眺めてたらあっという間に 4 時間たってました．解説会をやって，渾身の懇親をして，そのあと牛タンを食べました．いろんな人とおしゃべり出来て楽しかったです．
問題について
全体的な話
問題案を投げられた段階でどの問題も面白くて，tester をしていてとても楽しかったです．クオリティも高く，ARC に出しても遜色ない問題が多かったんじゃないかなと思っています．コンテスト後にはいろんな方から面白いセットだったと言っていただき，うれしかったです．分野も偏りなく出せていたんじゃないかと思っています．atcoder-standings-difficulty-analyzer による diff 推定によれば，4 人全員とも銅以上の難易度の問題を生やしていて，これもすごい．あとは，実装がつらい！みたな問題が少なかったのもよかったと思います．
それぞれの問題の感想とかを書いていきます．
!!!ネタバレをかなり含むので，まだ解いてない問題がある方はお気を付けください!!!
A. Sum Sort
tester しました1．2 分くらいで解けてたかな？シンプルだし 1 問目にちょうどいいね～～と言っていたけど，実力者でも WA を出してる人がちらほらいたみたいで，1 問目に置くには難しめだったっぽい．来年はもっと簡単なのを置きたいね．
B. Snowy Aobayama
tester しました2．10 分くらいで解けたと思ったらそのときのサンプルが弱くて 1WA しました（サンプルが優しくないねと言ったら，自分がその罠にはまっていた．アホ）．大学有志コンでよくありがちな，その大学にまつわる問題を簡単枠として出したいねという話があって作ってくれました．やることはそんなに難しく無くて，ABC-C/D くらいだと思ってたけど，この問題も 2 問目にしてはあまり解かれなかったですね．簡単枠の調整難しい...
C. Flip Grid
tester しました3．最初に問題を渡されたときは，グリッドは '#' と '.' で与えられるものだと思い込んでいて，O(HW) で解きました（これも 10 分くらい）．そのあと milk さんに O(黒のマス) で解けるといわれたので H,W,N<=2*10^5 にする今の形式を提案しました（こういう，制約の調整とかを提案とかするのが，共同作問っぽくていいですね）．問題の見た目がいかにも milk さんの問題って感じがして，解法がシンプルで面白かったです．
ここまでが Welcome 枠でした．この時点ですでに難易度を見誤っており，やばい！
D. Zeta Sum
横で見てました1．実は自力で解けませんでした．数式を見ていかつすぎ～とか言ってたら全然解けなくて，答えを見ました．こういうのは展開しないとダメですよねぇ．この問題は D に置かれちゃダメだろとはずっと思ってたけど，そうなると後ろの問題をを削って前に簡単枠を追加しなきゃいけないことになり，いろいろ面倒なことになるのでこのまま出すことになりました(当然正解者数が大変なことに...)．
E. 00-11 Rotation
tester しました4．30 分くらいで解きました．milk さんは転倒数を出しがちという偏見があった（多分ゆきこで出してた転倒数が印象に残っているせい）ので，転倒数とかかな～ってエスパーしたら解けました．この問題は，答えが転倒数になることの証明が結構大変で，writer 4 人でみんなで考えてました．
この問題は 10 月に提案されていました．1 月に diff 予想をしたときには，解いたときから時間がたっていたのもあってこの問題はすぐ解けたものだと思い込んでいたらしく，diff は 1200 だと主張していました．30 分もかかっていたことに気づいたのはコンテストが終わってからで，自分でも 1200 と主張していたことに驚いています．作問作業に長い間携わっているとバイアスがかかってしまって正常な判断をするのが難しいですね...．D>E とも主張していました（D：解けない，E：解けた だったので...）．
F. Block Rotation
tester しました5．考察・実装共にそこそこ時間がかかった気がします．高々 2 回の回転で元の形に戻るというのになかなか気づけず，サンプル 4 をお絵描きして気づけました．実装はちょっと大変だけど，やること自体は難しくないと思って diff 1600 を主張していましたがこれもはずれ．この問題の元ネタが万華鏡ってのを聞いて確かに～～となってました．
G. All Pairs
writer しました1．完全グラフで遊んでたら思いついた問題です．もともとの想定解は場合分けをして実際に構築していくもので，これが結構面白いと思っていました．オイラー路を再帰的に構築するアルゴリズムを後から知って，このアルゴリズムを知ってるとどこに辺を追加するかさえわかれば貼るだけの問題になってしまってちょっと悲しい気持ちになってました．でもまあ辺を追加する場所はそんなに自明じゃないと思ってそのままだしました．
答えは偶奇によって変わるので，提出デバッグがされないようにするために AGC061B の形式をパクってマルチテストケースにしてみました．一応 O(N^2) でも解けますが，O(N^3) でも pypy で N=1000 が 3000ms になって区別が難しかったので O(N^3) を許容しました．実装が短くできるのがお気に入りポイントです．
解説スライド用に gif を頑張って作ったのでここにも貼っておきます（N=5, 6 のときの構築方法です）．
H. Next Permutaion
writer しました2．階乗進数の問題を作りたくて作りました．特に言うことはないです．個人的にはあんまりおもしろくないと思っていたのですが，tester の sota 君がおもしろいと言ってくれたので出しました．
I. Count Setwise Coprime
writer しました3．約数・倍数系の問題かつ数え上げの問題を作りたいなーって言ってたら生えました．見た目がシンプルで気に入っています．解法については，多くの人は数論関数の累積和で通してくるんだろうなあと予想していて，実際にそうでした．想定解 1 の方は ABC-Ex で一回出ていて，実装も軽いしコンテスト時間も 4 時間あるので，ABC の問題が橙中位であることを踏まえると黄色上位とかになると思ってましたが，思った以上に難しかったみたいです．この問題も実装が短くて気に入っています(こたつがめさんの提出を参考にしたら python で 24 行になりました)．
ちなみに，今回の問題は Setwise Coprime の数え上げでしたが，Pairwise Coprime の数え上げは ABC で出てます．こっちは R-L がどれくらい大きくしても解けるんだろう？（全然考えてない）
J. AMidA
tester しました6．これ今回のセットで個人的に一番好きです．最初に問題見てから数日たって解けました．かかった時間は合わせて 2 時間 30 分とかかな？問題を渡された段階のサンプルがすごい親切で，最小回数!=転倒数 のケースが含まれていたので助けられました（このサンプルが無かったら倍近くかかってもおかしくない気がする）．この問題はまず最小回数が (N-サイクルの個数) になるのに気づくのが難しくて，渡された優しいサンプルをいじったりしていろいろ実験してたらそれに気付きました（この時点で 100 分位かかってたと思う）．あとはサイクルを管理するのも難しくて，O(N^2) でいったん書いてみた後に，マージテクが適用できることに気が付いて解けたという流れでした．高度なライブラリが一切いらず，使うアルゴリズムがマージテクだけというのが競プロの問題としてかなり面白いと思っています．
優しいサンプルにとても助けられたので，サンプルは弱くした方が良いという提案を当然しました．テストケースの作り方も少し助言したりしました．
私が自力で解けたのもあって diff は 2400 と提案してましたが，2 時間 30 分もかかってるならもっと高くつけるべきでした．本当に diff 予想が下手ですみませんという...
K. Lebesgue Integral
tester しました7．私は少し考えて何もわからなかったんですが，誰もやる気配がなかったので引き受けました．CHT をつかって O(NK) にするところは比較的すぐできて，そこからが何もわからず困っていました．O(NK) はできたがその先が分からないと writer に言ったら Aline DP というものがあるよといわれ，noshi さんの記事を教えてもらい，そこに書かれた事実を認めたら解けました．monge 性の何がうれしいかとかなんで三分探索でうまくいくのかとかは何もわかってないです．
今年に入ってぐらいから，TL で monge の話題がたびたび出ていたので，そのたびに「あまり話題にならないでくれ！」と言ってました．universal cup に monge が出たらしく，それの影響もあって正解者数が後半の問題の中では一番多くなりました．
L. Inversion High and Low
横で見てました2．なんか最初 milk さんがすごい解法をもっていて（でももともとは 500 回は想定していなかったっぽい？），tester の sota くんは最初マージソートで頑張ろうとしていて，それで 2 人のやり方をいい感じに混ぜると 487 回が達成できることがわかって，すげ～～～ってなってました．共同作問のいいところを見られて感動してました．自分はというと，ARC154D にあるようなマージソートっぽいことは一応考えていたんですが，どうやっても 500 回を下回らず無理でした．ローテートして前・中・後ろに分けるっていう発想は賢すぎるよ～～～～～．インタラクティブのジャッジを作るのが結構苦労してたみたいでした．
この問題だけ 3 時間経過しても正解者が出ず，終了 10 分前に QCFium さんが通したときは writer みんなで盛り上がってました（QCFium さんの直前の提出が 1 ケースだけ WA だったのもあり，祈るように見守ってました）．
M. Fractal Tree Isomorphism
tester しました8．これはどれくらい時間かけたかよくわからないです．問題を渡されてから 1 ヵ月以上かけて解きました．最初は，SSRS さんがツイートしていたような解法を考えていました．具体的には，有限の木に対して，その木の各頂点の深さとか次数をもとに有理数を割り当てて，それを無限級数っぽくやることで fractaltree に対しても有理数を割り当てるみたいな方針でした．この方針を writer に伝えたら hack されたので，木の同型判定を使うというヒントをもらって考えなおしたら，最小単位を考えるのに行き着きました．この問題もかなり面白くて好きです．
M
— SSRS (@SSRS_cp) 2023年3月4日
変数 x_1, x_2, ... を用意し、形式的冪級数 Σ[v∈V] Π[w: 根から v へのパス、ただし v は除く] x_{w の子の個数} が等しければよい → 適当な値を突っ込み mod で計算、をした
この問題も diff を 2400 と主張していて，終わっています．
無限周りの定義とか厳密性が全然わからなかったので，数学科の 2 人に見てもらったりしてました．私は解説に書いてある証明がなかなか理解できず苦労しました．
もともとは 2 つの木が与えられて，それらから誘導される fractaltree が同型か判定する問題だったのですが，テストケース作りが大変そうだなーって思って複数個にすることを提案しました．この提案が結果的に良かったみたいで良かったです．
N. Matrix Game
横で見てました3．この問題だけセットの中で唯一考えてないです．なんか大変そうな見た目してるな～って言ってたら，writer の sota 君が「大変だから無理して考えなくていいよ」と言ってたので，そのまま何も考えないままになってしまっています．tester の 3 人は実験してエスパーしたらしく，すごい...
O. Equidistant Binary String
writer しました4．もともと，順列 P,Q に対して dist(P,Q) を転倒数で定義して，2 つの順列 P1,P2 が与えられたときに dist(P1,Q)=dist(P2,Q) を見たす順列 Q についての問題をいろいろ考えてました．Q の数え上げとか Q の辞書順最小とか．それでうまくいかなかったので，なんとなく順列じゃなくて 01 列に置き替えてみて，さらに辞書順最小と数え上げを融合した問題を考えてたら，考察がどんどん進んで解ける問題を生やせました．
考察中は，ARC132 の解説のように，01 列を 2 次元グリッド上の経路としてとらえて考えていました．経路として考えることで，2 つの文字から等距離にあるという条件を経路の下側の面積として表現でき，これがうまく使えました．辞書順最小という条件もうまい具合に表現できて，びっくり．
コンテスト中に 2 名の方に解いていただいてとてもうれしいです（だれにも解かれたくないという思いも多少はあったんですが，それだと悲しいので）．ありがとうございました！
全体の感想・振り返り
まず反省しなければならないのが，難易度の設定ミスでしょう．過小評価しまくっていたのは良くなかったです．どうすれば過小評価を防げるんでしょうか？来年の課題ですね．
そのことを除けばかなりうまくいったんじゃないかなと思っています．コンテスト準備・運営で反省すべき点もいくつかありましたが，初めてのオンサイトコンテストの運営にしてはよくやれたのではないでしょうか．
懇親のときに，セット内容についていろんな人に褒められてうれしかったです．ARC 書ける実力ある世ともいわれて，ARC writer をやるモチベがわいたので，さっさと橙になりたいね！（O みたいな問題をまた生やせる気は全然しないけど）
ほんとにめちゃくちゃ楽しかったです！来年もやるつもりでいます！
ざっくりこんな感じです．
ご参加いただいた方々，仙台まで来てくださった方々，本当にありがとうございました！また来年もよろしくお願いします！
TUPC2022 おしまい
