TUPC2022 感想 - sotanishy.shojin();

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

この記事では，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時間にして結局良かった気がする (オンライン参加者には申し訳ないけど)．それでも時間が足りなくて話せなかった人が多かったのは残念．