仮のブログ

仮です

TUPC2022 開催記

はじめに

　東北大学プログラミング2022を開催しました. この記事はその開催記と感想的なものです.

atcoder.jp

各問題の感想

　自分がWをした問題についてのみ言及. ネタバレや解法を大いに含みます.

B: Snowy Aobayama

　Writerをした. 簡単枠かつ大学ネタの入った問題を作りたかった. 少し捻りを入れたかったので O(N) の素朴な解法から座圧的な事を要求する制約にした. 2問目に置くにしては難しかったかもしれないので O(N) のままの方が良かったのかもしれない.
　実際にコンテストで自分が解きたいかと言われるとそうでないかもしれないが, 私はこのような問題が有志コンテストにあるとちょっと嬉しくなる. そんな問題にすることができたと思っている.

D: Zeta Sum

　Writerをした. 式の見た目が厳ついし難易度評価がムズすぎる. 出来てしまえば簡単だけど時間を掛ければできるかと言えばそうでもないし......
　この問題は賛否が大きく分かれそうだなと思っていたので感想ツイートで面白かったと言ってもらえたのを見つけて安心した. (もちろんそうでない感想もあったので次回以降もちゃんとバランスも考えないとなとは思いました.)

J: AMidA

　とても好きな問題なのでこの問題の制作過程も含めて少し長めに話す.
まず最初に対称群から問題を作ろうとした. (このころ体論, ガロア理論を学んでいたので.) 対称群で競プロ問題っぽくするならアミダクジとかが良さそうと思っているとamidaの中に数学で恒等的を表すのに用いられている "id" が潜んでいることに気が付く. ここで恒等的なアミダクジを題材に問題を考えようとなった. 色々問題設定を考えては自分で解いてを繰り返して取りあえず今回の問題で言うところの最小回数を求めるパートまでで良さげな問題となった.
最小回数を与える操作についても, どうすれば良いかまでは分かったが, 実際に実装する方法が分からなかった. 削除可能UnionFindで一応可能ではあったのでこれを実装してここまでの考えがあっていることを確認.
しばらくたっても解けなかったのでSota君に相談したところ, 色々なconectivityについてが書かれた記事を教えてもらい解決. 無事に今回の問題の形になった.

　これで問題が完成で万歳となるかと思いきやここからはテストケースづくりに苦労する.
逆マージテクをサボる解法は落としたかったが, これを落とすのが中々難しい.
というのも, マージテクサボりが落ちるのは, デカいサイクルからサイクルをちょっとずつ切り落とすケースであるが, 超意図的に作らないと中々これができない.
そこから, 少々の横線を追加したりシャッフルしたりは耐える(テストケースのstairarbがこれに相当)が, それ以上変化させると, 逆マージテクをしなくても結構通る.(stairに相当).
　その後色々試してはコードを走らせて実行時間を計測する中で, 作ることになるサイクルを先に作ってそれになるように横線を設定するという方法を思いつく.
しかし, これにも問題点はあり, 適当にサイクルを決め打ってしまうと, 横線の本数が O(N^2) のオーダーになってしまう.
そこで, 横線の本数を O(N) 程度に収められるようなサイクルを用意する必要があり, これは \sum|i-p_i| を小さくすることを目指せば大体良い.
最終的には, N を X 個のブロックに分け, 各ブロック内でサイクルを作り, それをつなぎ合わせるという方法をとった. (permケースの前半)
ここまで作って満足していたが, どうやらこれだと削除可能UFや変更する頂点のすぐ近くだけ調べるといった方法で通ってしまうらしい.(全体testerのお二人に教えていただいた).
正直それらの解法は通ってしまっても仕方ないと思っていたが, permケースの X の値を変えてみたり, 適当にシャッフルを加えたりしてみたらこれらの解法に対して強いケースとなった(permケースの後半).
こうしてこの問題は完成を迎えた.

　この問題は最小回数を求めるまでと, TLに間に合うように実装するところに2つ考察の山場がある. しかし実装は丁寧にやればかなり軽く, データ構造としてはvectorがあれば事足りる. testerのこたつがめさんの提出を参考に書き直したところ, C++で43行に収まった. これもお気に入りポイントである.
https://atcoder.jp/contests/tupc2022/submissions/39489976

準備について

　ここからは運営としての準備について書く.
次回以降の開催のためのメモとしての役割も持たせている.
各内容を思い出したら随時更新をする.

2022年8月頃

　TUPC2022というdiscordサーバーが生える.
メンバーが集まったところで役割分担をする.
役割は,

  • 進捗管理: 全体のスケジュールや進捗をまとめる係
  • 連絡係: 各所と連絡をとる係
  • 技術係: rimeやgitの使い方の管理をする係

である.
この時点でメインwriterが4人, 有志コン経験が豊富なアドバイザーが2人といった運営パーティーとなった.

　その後2022年末くらいまではひたすら問題を生やす.
問題は, writerが問題設定や簡単なテストケースを作った段階で他のwriterにtesterをしてもらいながら問題をブラッシュアップといった流れ.
問題の作成はrimeで, 問題の管理はgithubで, 進捗の管理はスプレッドシートで, 問題の議論はdiscordの個別チャンネルで行った.

2022年末頃

　コンテスト開催形態について会議をする. 希望としてはオンサイトあり&AtCoder上開催であったのでその方向で調整をしていく. また, ICPCAsiaの折にhenoさんに全体テスターをお願いし, 承諾をいただいた.

2023年1月

　問題セットを一通り組んでみる. オンサイト会場も大学で話が付きそうとなったので, 実際にAtCoder側と連絡をとり, 日程が3月4日に決定.
　問題作成としても, 草稿状態だったものも含め全て一旦の完成状態とする.

2023年2月

　全体テスターからのフィードバッグをもとに問題を磨く. その他告知を出したり, 全体の会の流れを考えたり細かい準備を進める.

2023年3月

　問題の最終チェックをしたり, 同一のWifiから大人数がAtCoderのサイトに繋ぐのヤバイ!!ってなって慌てて連絡をしたり, 他コンテストによる問題爆破にひやひやしたりしているうちに本番を迎える.
　本番は開場から解散まで大きなトラブルもなく楽しんでもらえたようで良かった.

おわりに

快くサイトを利用させていただいたAtCoderの皆様, 全体テスターを引き受けていただいたhenoさん, ご参加頂きコンテストを盛り上げて頂いた皆様, ありがとうございました.
現在開催を目指しているTUPC2023もよろしくお願いします.