UTPC 2023 に運営として参加したので、運営プロセスや各問題についての感想をまとめます。
スケジュール
| 10/15 - 1/20 | 原案作成・難易度評価 |
| 1/20 | 問題選定・作業者割当 |
| 1/20 - 2/18 | writer 作業 |
| 2/18 - | tester 作業 |
| 3/12 - 3/13 | 問題文校正 |
| 3/13 - | 名札作成 |
| 3/17 | コンテスト本番 |
運営陣
昨年の運営陣から今年は運営やれという要望を多数受けたので参加することにしました。この他にも での募集から新規参加したメンバーが多くいて、今年からの新規は 9 人と、昨年からの継続 7 人よりも多くなりました。他の大学コンテストを見ても運営 16 人というのは異様な多さだと思います。
作問体制
GitHub の issue に原案と想定解を書き、他のメンバーが解いての感想や難易度評価をスプレッドシートに書き込むという形式です。issue を作ったりリプライがあった場合に discord の通知が行くようになっていました。1 月までに 25 個程度の原案があったので、問題数不足に困ることはありませんでした。選定会では原案作成者の出題したい度合を元に 16 問を選定し、その後さらに 1 問を追加する形で 17 問になりました。
オンサイト
今年も MC Digital 様に会場をお借りさせていただきました。今回のオンサイト開催における反省点を以下に挙げます。
- 開催数日前まで会場の撤収時間を正しく把握できていなかった。
- マイクの電池状況を把握すべきだった。
- 懇親時間が取れなかったのでコンテスト時間を前倒しにするなど調整すべきだった。
- 解説会をできる場所が狭かった。可能ならポスター発表形式にしても面白いかも。
- コンセントの使用状況を把握できていなかった。
- 会場の集合場所が B1 であることを強調した周知ができていなかった。
- AtCoder のコンテストページや connpass を公開できるのに誰もやらないという状態が続いてしまったため、公開できる状態になったら即座にするべきだった。
名札作成
AngrySadEight さん主導でアイコン入りの名札を作りました。デザインは AngrySadEight さんに作ってもらい、私含め数人で connpass のアイコン画像をはめ込む作業をしました。AngrySadEight さんに印刷とカットをしてもらい、当日私が購入した名札ケースに入れる作業をしました。
作問準備
各問題について writer・tester 1・tester 2 が割当てられます。writer の主な作業は問題文、テストケース、想定解の作成で、tester の主な作業は AC 解、想定嘘解法のチェックと入力が制約を満たしているのかの確認となります。
writer は基本的に原案作成者が行うことにしたため、原案を 1 個も出していない人と原案を複数出している人の間で負担がかなり偏重してしまったのは改善点です。しかし、仕事を多く振られた人も期限内にできそうになければ他の人に投げていればよりスムーズに準備ができていたと思います。仕事をやっていないことを指摘されてそれに逆ギレするというシチュエーションは最悪です。個人主義な人が多い弊学の悪い所だと思いました。
問題名
miscalc さん主導で、問題名の頭文字を問題番号に一致させるようにしました。原案の時点では問題名はバラバラだったのでかなり大変だったと思いますが、最終的にはかなり上手くまとまっていると思います。個人的には J: Japanese Gift Money が好きです。
問題文校正
開催週の火・水曜日の夜に、合計 8 時間のミーティングで全 17 問の問題文校正を行いました。セット全体での表記の統一、誤読する余地がないか、サンプルの説明など、各々が気になる点を列挙していってそれを 1 つずつ直していくという形で進めました。I, O 問題など原案時点の問題文が見る影もなく変わった問題もありましたが、元と比べると見違えるほど良くなったので時間をかけてやった意味は十分あったと思います。本番は clar 0 でした。表記ゆれの統一など今回で得られた知見は多くあるので、来年以降はよりスムーズに進められると思います。
当日
当日は運営 16 人のうち 15 人が現地に行きました。たくさん人がいたので、名札のケースへの収納や参加者の案内をスムーズに行うことができました。コンテスト中はオンサイト参加者の様子を見に行ったり、運営で FA 予想をしたり、順位表を眺めたり、食事に行ったりと楽しかったです。
各問題について
準備段階で全問題の AC を取ったので、それぞれについて簡単に感想をまとめます。括弧内は個人的な難易度評価 (AtCoder での配点) です。
A: Again Make UTPC (600)
AngrySadEight さん原案。UTPC 枠。UTPC が部分列として出てくる場合は 4 回以下ででき、答えが 4 になるケースも実際にあるという部分がかなり非自明。キャッチーな見た目とは裏腹に正しく詰めるのが難しく、ペナ祭りと化していた。
B: Black or White 2 (600)
Mitsubachi さん原案。構築その 1。実は自明な最適値を達成できる。やりようは色々あって誰にでも解けうる問題で、個人的には A 問題よりも取り組みやすいと思っていた。しかし結果的にはそれほど AC されなかった。
C: Contour Multiplication (700)
SSRS さん原案。SSRS その 1。原案当初は乗算ではなく加算だったため、私が XOR convolution 回で解けることを指摘したらそれを阻止するために任意 mod での乗算になった。SSRS さん曰く典型とのことだが、私は全然わからなかった。ためになる一問。
D: DRD String (600)
confeito さん原案。中難易度数え上げその 1。DRD 文字列を DRD として表す方法として何があるかを考えると自然に考察が進む。個人的には C 問題より幾分か取り組みやすいと思っていたが、実際の結果を見てもそのようだった。ちなみに元ネタはダンスロボットダンスというボカロ曲らしい。
E: Equally Dividing (500)
Mitsubachi さん原案。構築その 2。B 問題と同じく、自明な必要条件を満たしているものは全て作ることができる。実際に手を動かして考えやすいので、B 問題と比べて取り組みやすいと感じていたが、実際は予想より大きな差が出た。
F: Flip or Not (1100)
Mitarushi さん原案。自力では初手の多項式で剰余を取るパートから気づかなかった。その後も正しく立式して 多項式の諸演算を実装する必要があるので、解説を見た後に通すのですらかなり苦労した。個人的には 0 AC 筆頭だと思っていたが、本番では hos_lyric さんに解かれていて感嘆した。
G: Graph Weighting (800)
tokusakurai 原案。グラフと最適化。原案当初は 固定かつ最適化パートはなしの構築問題だったが、運営陣から簡単という意見を多数受けたので強化をすることとなった。数え上げにする案もあったが、のいみの案をさらに強化をする形で現在の問題となった。ステップが 3 つ程あって、どれも突飛なものではないため難易度推定は難しかったが、本番は 6 AC と想定より多くの人に解いてもらえた。
H: Huge Segment Tree (700)
SSRS さん原案。SSRS その 2。中難易度数え上げその 2。問題設定が面白い。想定解は多項式で立式して式変形を重ねているが、分割された区間の一番長い部分がどの段にあるかで場合分けして立式しても畳み込みの形になって解ける。当日運営の控室で SSRS さんに H は fps 経由しなくても解けるという話をしたら、fps ではなく多項式だと説教された。
I: I Love Marathon Contest (1200+)
noimi さん原案。全完阻止枠。高難易度数え上げその 1。AGC-E,F レベルくらいあると思っている。周回数が累積和の がその
になることに気づくのは難くないが、
される必要十分条件がかなり難しい。そこから高速に計算できる形にするのもかなり難しい。そして、解説を書くのも難しい。間違った OEIS エスパーができるようにサンプルは
までにしてもらったが、結局提出すら 1 回もされなかったのは残念。
J: Japanese Gift Money (500)
miscalc さん原案。簡単枠その 1。日本のお祝儀が題材ということで、命名がとても上手い。問題自体は、最初に考えそうな予想が正しいでセットの中で 2,3 番目くらいに簡単だと思ったが、実際には想定よりは解かれていなかった。
K: Kth Sum (800)
SSRS さん原案。SSRS その 3。想定解のブロック分けは自然な着想で、これで計算量が落ちているのが面白い。その他にも色々な解法がありそうなため、セットの高難易度帯の中では比較的正解しやすい問題だと思っていた。実際、本番でも 10 チーム以上が正当していて、中には の高速化で通したチームもあるようだった。制約強化や TL 調整をする余裕がなかったのが残念。
L: Largest Triangle (400)
confeito さん原案。簡単枠その 2。このような問題では何かを固定して考えてみたくなるが、今回は最大辺を固定することで上手くいく。出力形式に関しては小数にするか平方根の中身にするかといった議論があった。
M: Majority and Permutation (800)
chinerist さん原案。高難易度数え上げその 2。原案時は、順列 が与えられたときに正しい括弧列であって
に従って並び替えても正しい括弧列となるようなものの構築問題だった。これに対して私が優先度付きキューを用いた貪欲法を指摘したところ、それでは面白くないということで数え上げ問題に転生した。当初は制約は
だったが、私が
についての必要十分条件を指摘した結果、制約が
まで上がった。upsolve おすすめの問題。
N: Number of Abbreviations (500)
SSRS さん原案。SSRS その 4。簡単枠その 3。問題設定、解法共にとてもシンプルで面白い問題。それと同時に、詰まる人はとことん詰まってしまいそうという印象がある。私も筋のいい着想に至るまで 10 分程要した。部分文字列数え上げをする嘘が多く出ていたのは意外だった。
O: Optimal Train Operation (800)
confeito さん原案。5h 枠。解法としては挿入・削除する CHT を考えたくなるが、実は履歴を管理するシミュレーションだと最悪ケースで になってしまうため、挿入・削除の履歴を木構造として持って HLD を使うというのが原案の想定解。こちらでも通すことはできるが、実装のみならず TL や ML も厳しい。chinerist さんのテスター解である分割統治を使うと、計算量も実装もかなり楽になる。方針が重要な問題。
P: Priority Queue 3 (1000)
chinerist さん原案。高難易度数え上げその 3。M 問題の制約強化前の想定解の部分問題として作られた問題で、ad-hoc 要素で面白い問題だったので追加で採用してもらった。chinerist さんの最初の想定解はいわゆる箱根駅伝 dp を使うものだったが、それとは独立に私が公式解説の解法を思いつき、こちらの方がやや計算量が良かったためメインの解法になった。こちらも upsolve おすすめの問題。
Q: Quotiet Sum (600)
tokusakurai 原案。この位置には元々 SSRS さん原案の幾何の問題があったが、前週の ABC-G 問題で似たような問題が出題され、解法の本質パートが で投稿されてしまったため出題を見送りとなった。Quotient Sum は補填の簡単枠として私が即興で作った問題だったが、ちょうど良さそうということで採用となった。codeforces Div.1-A くらいの難易度のつもりだったが、実際は意外と捉え所が難しいようだった。
おまけ
I 問題のタイトル
— のいみ (@noimi_kyopro) 2024年3月17日
I hate Marathon Contest but I like MCD! が面白い。
Q 問題の爆破
#UTPC2023 本当はもう 1 問原案を出していたんですが… pic.twitter.com/DeUpaKoR1N
— SSRS (@SSRS_cp) 2024年3月18日
G: 助けてくれ（クエリがランダムなことを利用して怪しい平方分割に......）
— 和解 (@rsat__m) 2024年3月9日
Q がそのままだったらだいぶ難易度やばかったかもしれない。
セット全体の難易度調整
最終的な結果を見てもだいぶ難しいセットだったと思いますが、簡単枠が嘘解法を誘発するような問題ばかりだったのが全体としての AC の低さに大きく寄与しているのだと思います。Universal Cup でもトップのチームにもギリギリ全完されないくらいの難易度だったのは良いですが、多くのチームにとって高難易度の面白い問題に割ける時間が短くなってしまったのは調整ミス感があります。全体的にも WA が発生しやすい問題が多かったので、その辺りをふまえた難易度調整は今後の課題になると思います。5h という枠に囚われず、より長いコンテスト時間や Day1 Day2 という方式にするのもありですね。
感想
個人としては作問活動をするのは初めてで、その中で 2 問出題できたのは非常に良い経験となったので、今後も作問活動を行っていきたいです。コンテストとしては問題名や問題文など細部までこだわり、clar も 0 と非常に質の高いものができたと思っています。会場をお貸しいただいた MC Digital 様、コンテストサイトを提供いただいた AtCoder 様、ご参加いただいたコンテスタントの皆様にこの場を借りて感謝申し上げます。
