UTPC2023 開催記 - chineristACの日記

UTPC2023 を開催しました

atcoder.jp

めっちゃ遅いし今更かな～と思ったら誰も開催記書いてなくないか？？？

各問題の感想+運営面でのザックリとした反省点を書きます。難しめの問題は大体解いてて簡単目はあまり通してなかったりするので短めになるかも。大いにネタバレを含むので注意。

問題の感想

A- Again Make UTPC

U > T > P > C なの気づいてましたか？僕は知らなかったので提案されたときビックリしました。

元ネタの Make UTPC と同じくなんとなく解けそうなことはわかるが場合分けが地獄になる問題。前回以上にヤバかったみたいで開始後しばらくWAしかでてなかった。 Contestant じゃなくてよかった～～～～～～～～～～～～～～～～

B- Black or White 2

構築問題。損失最小 $0$ じゃないと解けない気がするけど構築できね～～～～ってなってました。しばらく考えて階段状に黒にするのが強いことに気づきなんとか AC 難しめの問題が並ぶ今回のセットの中で、これ考えてもらえば暇しないかな～という枠でした。

C- Contour Multiplication

典型枠だと思ったら思ったより解かれなかった。 $2^{N-1}$ の位が $0,1$ のケースでクエリを言い換えればあとは問題が $2$ 分割されるだけで解けるいつものやつです。

最初は足し算だったけど畳み込みで解けるらしく、一般 mod で逆元をなくすことで対応。

D- DRD String

面白かった。最初 D の長さについて包除原理つかって答え計算してみるか～とやってみると二乗でも解けず崩壊。最初から考え直して解説通りの解法でACできました。

はじめてみる結論でおもしろいな～と思ったら準備中にARC-Fやらゆるふわコンボス問などで急に出題されだした。

E- Equally Dividing

構築問題 2 。両方奇数のケースにしばらく悩んだので黄diff評価出してたんだけどかなり解かれて最初びっくりした。

あとから atcoder.jp

とかで解けることを知った。

F- Flip or Not

ヤバ問題 1 。とりあえずぱっと見だと全然解けなくて $\mathbb{F}_{2} [x$ ] での話になるんだろうな～と思って言いかえを考えるがわからない。結局解説みてあ～となった。最初の言いかえも難しいし後の処理も自分の方針だとかなり大変。

AtCoderとかほかのコンテストでもこの手の問題あまり見なくて

atcoder.jp

ぐらいだったので評価難しかったが、最終的に HoMaMaの 1AC のみとなってしまった…

G- Graph Weighting

最初全域木の重みを共通にできるか？という問題で、これは自分でも考えたことあったので典型かな～と思っていたらいつの間にか魔改造されていた。二重頂点連結成分の頂点数で分けると凸になって、あまりごとに考えると片方凸のmin-plus convolutionになるのすごい。

pypyでだれも通してなかったので二重頂点連結成分分解やmonotone minima・SMAWKを非再帰でかいてチャレンジしたがギリギリ通らず。結局頂点数の昇順に畳み込んでいたのを降順にすると倍ぐらい速くなってACした（ちなみにSMAWKの定数倍がおもすぎてmonotone minimaに余裕で負けてて泣いた）。

H- Huge Segment Tree

最初非再帰セグ木でクエリが分割される過程に基づいて数えようとしたが全然解けない。考え直して木を上からみて左、右に行くパターンと分かれるパターンで分けて考えたら解けました。計算もそこまで複雑じゃなくて比較的簡単目な印象。

I - I Love Marathon Contest

大体集まったから問題セット決めるぞ～！となった1日前にnoimiが投げてきた問題。評価できないからもっと早めに投げてくれ…

かなり面白め+難しめの数え上げだと思うのでぜひ挑戦してください。

最初noimiはラストランナーが累積和最小で一番右のやつとして考察して「最初と累積和最小で一番右の走者を抜かして考えればいい」ととしてましたが、ラストランナーについては嘘で、tokusakuraiと一緒に証明を考え直してました。たまたま結論があっているおかげで「」内の考察がすんなりでてきてますが、実はこれ天才言いかえじゃないか？と思ってます。

J- Japanese Gift Money

エスパー問題？ちょっと悩んだ後に試しに $A_i$ 進数にすると実は単純になる？とエスパーして成功しました。必要十分であることを示すのも簡単ではないと思う（自分はすぐできる思ったけど後で考えると間違ってた）。ただコンテストならエスパーでいいので…

K- Kth Sum

SSRSが2600diffぐらいといって投げてきた問題。全然解けなくて泣きました。解説みてこんなことできるのか～と感心。

コンテスト2日前ぐらいにtorisasamiが賢いけど単純な $O(NK^{\frac{1}{3}})$ 回を出してきて、落とそうかなやんだけど結局無理でした。

こんな感じで想定解の通りにやるのは難しいと思うけど、3人いればたぶんいろんな嘘や謎ヒューリスティックを組み合わせて通してきそうだなと想像してました。大体想定通りの通り方だったと思います。

L- Large Triangle

簡単枠をつくろうとなってできた問題。一番長い棒に着目すれば結論がそうなるのはその通りなんだけど、最初ヘロンの公式で1辺固定したときの最大化は～とか考えて単純な結論にならず解けなくて泣いた。

M- Majority and Permutation

writerしました。最初は

chineristac.hatenablog.com

のC問題のとこに載せた問題が「 $P$ を逆順にしてもいい」という風にすると天才構築で $N=200000$ でも解けそう、と思ってARCに出そうとしたが、adminから「自分のブログで言及しちゃってるとちょっと…」と言われ断念。UTPCで出してもいいか聞いてみるか～と思って出したところ、tokusakuraiから「貪欲で普通に解けない？」と指摘されて愕然としていました。

その後「（のちのP問題）を部分問題として経由すれば $O(N^{4})$ で解ける！」となって数え上げの形で出したのですが、またしてもtokusakuraiから「実はこれが必要十分条件で $O(N^{2})$ で解けない？」と指摘されてめちゃくちゃビックリしました。集団作問の醍醐味って感じでいいですね。

ゴミサンプルにしたけどどれくらいエスパーされるのかな～と思ったら4h経っても全然解かれなくて焦りました。

N- Number of Abbreviation

（比較的）簡単枠。たとえば ARC-B,C にあると想定解にたどり着けるかもしれないが、5hで難易度シャッフルでだされると suffix array とか使いそうに見えっちゃって面白い問題だなと思いました。最終的には順位表でわかるし解かれるだろ～と思ってたので AC 数が E > N になったのは想定外でした。

O- Optimal Train Operation

こういうのはまずオンラインオフライン変換！（脳死）をしたらうまくいった。ARC-Fで何回か出ているし高度典型としてみんな（とくにJOI勢）解いてくるかな～とおもってた。実際にforestedさんがFAで予想どおりだ～となったけどAC数は思ったほどは伸びなかった。これまだ典型じゃないのか？

P- Priority Queue 3

writerしました。Mで考えた部分問題がいらなくなって16問セットの予定だったから捨てようかと思ったけどもったいなくね？となって17問に増やして出題。この予定調和dpそこまで天才！って感じじゃないしE8さんとか解いてくるかな～と思ったけど最終的にHoMaMaだけで悲しい… Priority Queue の別verって感じでワンチャンmaroonさんのストック爆破できるか？と思ったけど見た感じそもそもストックになかったっぽい。

Q- Quotient Sum

#UTPC2023 本当はもう 1 問原案を出していたんですが… pic.twitter.com/DeUpaKoR1N
— SSRS (@SSRS_cp) 2024年3月18日

もともと用意していた問題が一週間前にまさかの爆破。想定解は全然違ったけどX上に別解として流れているのを観測したため出題を断念。

そのあとにtokusakuraiが「簡単枠」として提案した問題。言いかえも遷移の絞り込みもむずくね？となったけどdiscordで誰もつっこんでないから俺がアホなだけか…となったが当日みんなQヤバいでしょと話してた。不安になるからdiscordですぐにつっこんでくれ！！！

運営面での反省点

挙げるときりがないが

コンテストの告知が遅い

コンテストページが全然公開されなかったしオンサイトの募集が始まったのが締め切り1週間前とかだった気がする。ヤバすぎ

会場がわかりにくい

今回MCDさんの会場を貸していただけたのですが（ありがとうございます！！！）、地上から入れないというのがあまり伝わってなかったみたい？で迷子が多発した。次回以降は地上から地下へのルート案内も流しておこうと思います。

重要な連絡がうまく伝わっていない

上記の会場の件だったり、名札につかうconpassのアイコンの画質が低いのを変えてほしいといった連絡があまり伝わってない気がした。

これはたぶん連絡をXでの公式アウのpostに頼ったのが原因で、そもそも公式アカの存在を周知していないのもヤバいのですが、postしたタイミングでTLにいなかったらそれっきりなんですよね。次回以降はオンサイト参加者専用のdiscordサーバーを立てることなどを検討しています。

懇親の時間が取れなかった

これの原因なんですが、撤収時間を把握したのが2,3日前とかでした。MCD側との相談はもっと前からやっていましたが撤収時間を交渉役が全体に共有していなかった+交渉役に聞いておくのを全員忘れてた Ω＼ζ°)ﾁｰﾝ

来年以降はもしかしたらコンテスト時間をずらして対応するかもしれないです。