nononの落書き帳

不定期に、でもずっと更新したい

TUPC2023開催記

3月9日に東北大学プログラミングコンテスト（以下TUPC）を開催した。私もwriter・運営としてコンテストに関わったのでその記録を書こうと思う。

atcoder.jp

準備について

運営が組織として動き始めたのはICPCの国内予選が終わった直後だった。その時点でいくつか原案があったのでwriterとして参加することにした。また、自分以外のwriter陣が全員B4以上だったので今後の開催も考えてAtCoderとの連絡係も引き受けることにした。そこから11月ごろまでは原案出しやtester作業をしていた。

11月の終わりごろには原案がある程度出ていたのでコンテストの開催に向けて本格的に動き出した。一度writer陣で集まり、問題の選定なや今後のスケジュールなどを議論した。実は最初の候補日としては3月2日を考えていたが、これを決めた直後にマスターズの予選が生えたため変更を余儀なくされた。運営陣の都合を考えると3月9日しか候補日がなかったが、この日は東北大で入試があり学内の教室を借りることが難しそうだった。顧問の先生との協議を重ね、何とか年内に教室使用の目途が立った。また、それと同時並行でAtCoderとの連絡やhenoさんへのtester依頼を行っていた。

年が明けてすぐに大学から教室の使用許可書をいただき、オンサイトを開催できることが決定したので告知を行った。オフィシャルなアカウントからツイートをするのはかなりドキドキする。

ツイートしてから1時間ほどはずっとTLを眺めていたような気がする。多くの方から楽しみという声があり、とてもやる気が出た。後日気付いたことだが、このツイートにハッシュタグを付け忘れてしまった。反省。

その数日後に再びwriter陣で集まり、問題順や開催までのスケージュールを話し合った。その時にオンサイトの募集開催とコンテストサイトの公開も同時に行った。

コンテストサイト

とりゐさんから文字サイズの変更のアイディアがあがり、クリックすることで文字サイズが変わるようになった。

2月に入り全体testerのkotatsugameさんとhenoさんに問題を渡した。また、オンサイトに来た人が暇にならないように学内の青黄の3人チームに実際に5時間走ってもらい、難易度感などを確認した。特に「簡単枠を解いた後に不可能枠しか残っておらず何もできなかった」ということにならないようにしたいという気持ちがあったので、この確認が出来たのはよかった。これは来年以降も続けていきたい。

3月に入ってからは問題文のチェックや解説に嘘がないかなどを繰り返し確認した。また、直前には名札を作ったりお菓子の買い出しなどを行った。

当日について

当日は11時ごろに集合し、会場準備などを行った。名札やお菓子を並べていたら受付開始時間になってしまったので慌てて受付に座り受付の仕事を行った。そしてついにコンテスト開始。

開始してすぐにA問題のFAが出て開始を実感。その後すぐにG問題、I問題のFAも出ており順調な滑り出しだった。数分後にはC問題。F問題にもFAが出ており、難易度を見極めるのがうまいなぁと思っていた。
次にFAが出たのはN問題だったがこれはかなり想定外。その後1時間以上たってから2nd ACが出たのでNyaanさんがやばかったらしい。続いてJ問題、E問題と解かれていてかなりいい感じだった。開始1時間で半分の問題にACが出ていた。続いてL問題、P問題と解かれ、開始2時間を迎えた。
その次にFAが出たのがO問題だったがこれもびっくり。コンテスト後にHemimorさんに話を聞くと20分くらいで解いたらしい、すごい。O問題は結局このFAがユニークACなので難易度推定が間違っていたわけではないのだろう。その後、開始3時間までにB問題、D問題とFAが出ていた。 次の1時間はFAが出なかった。しかし、上位陣は解いてる問題がチームによって異なっており、順位表は賑やかだった。残り1時間となりまだ3問が0AC。だが、最後の1時間の間にM問題、H問題とFAが出た。運営の面々でもジャッジを見守っており、ACの文字が見えたときにはかなり盛り上がった。 そしてコンテスト終了。あっという間の5時間だった。

結果としては以下のようになった（画像は解説スライドから）。

各問題の予想diffと実際のdiff

diff予想を大きく外したのがD問題、J問題、K問題、M問題、O問題だけで、それ以外はかなり予想通りで嬉しい。特に（難易度順で）前半の問題での大きなミスがなかったのはよかった。

その後は解説会と懇親会。解説会については割愛。来年はもう少しうまく話せるようにしたいね。懇親会では多くの人と話すことができて良かった。特に自分の問題についての感想をいただけるのは本当に嬉しかった。これからもオンサイトコンで作問したいと強く思った。

問題について

各問題の細かい裏話は他の方に任せて自分がwriterをした問題についてのみ書こうと思う。

L - Random Mex

最初にこの問題を考えたときは以下のような設定だった。

N 個のサイコロがあり、i 番目のサイコロは 0 以上 A_i 未満の目が一様ランダムに出る。 これらをすべて振るという操作を M 回行う。i 回目の操作の出目の \text{mex} を B_i とするとき B の \text{mex} の期待値を求めよ。

これでは全然解けなかったので今の形式に落ち着いた。また、原案を投げたときは M,N \leq 5000 とかで O(NM) のdpが想定だった（解説スライドの部分点解法）。遷移部分がかなり面白いので個人的にはかなり好きな解法。

また、その後も制約や解答形式の変更が何度かあった。具体的に以下のものを考えた（どれも解ける）。

  • N,M \leq 3 \times 10 ^5
  • N,M \leq 3 \times 10 ^5、M に関する列挙
  • N,M \leq 3 \times 10 ^5、N に関する列挙

ただ、最終的な閉じた式を出してほしいということで現在の制約になった。 O(N^2\log N) や O(TM) を落としたかったので普段のコンテストでは見ないような厳しい制約になってしまった。実際1ケースだけTLEの提出もあったのでかなりギリギリなことをしていたのだろう。

N - Do Not Turn Back

解説スライドにも書いたが元ネタは桃鉄の「いけるかな」である。友達の家で桃鉄をしているときにふと思いついた問題。問題を考えたときはTUPCに出そうと思ってなかったのだが思いのほか好評で採用となった。この問題もL問題同様TLが厳しめになっている。また、既出が見つかったり非想定のBMBMで殴られたりと悲しいことに。もし来年もwriterをやるなら気を付けたいと思った。

最後に

はじめて競プロのwriterをしたが本当に楽しかった。語彙力がないのでうまく書けないがとにかく楽しかった。また、オンサイトの準備・運営も楽しかった。普段はTwitterでしか見ない人々が実際に目の前で話しているというのは何となく不思議な感覚になる。この楽しさをまた味わいたいので来年もTUPCを開催したい！幸いなことに今年のwriterのうち5/6は来年も残っているのでとても楽しみである。

最後に、はるばると仙台まで足を運んでくださった方々、順位表をに賑やかにしてくださったコンテスタントの方々、本当にありがとうございました！！また来年もよろしくお願いします！！！