うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

ICPC模擬地区予選 2022　準備記

ICPC

ICPC模擬地区予選 2022 参加者の皆さま、お疲れ様でした。ご参加いただきありがとうございました。

以下、各問題に対する貢献（あれば）と個人的な感想などです。

以下、問題のネタバレを含みます

A: Stop & Go

準備されたものを見たら赤になった瞬間に信号に突っ込むケースがなかったので追加しました。
ついでに青になった瞬間に信号に突っ込むケースも追加しました。こっちはいらないかも。

B: 1-Player Concentration

ほとんど何も関わってないです。
難読なのかなと思っていましたがわりとサクサク通されていたのでよかったです。

D: 2-LIS

原案時には {O(N^3)} だったのを {O(N^2)} に落としました。
あとは少しだけテストケース生成をしました。
解説には違う DP が書かれていましたが、自分の解法は

dp[x][y] := (b_{k-2} < x) and (b_{k-1} = y) を満たすような k の最大値

というちょっと変な DP テーブルがうまく更新できることを使っています。これちょっと面白くない？
AtCoder で言うとこの問題が少し近いかもしれません：https://atcoder.jp/contests/abc176/tasks/abc176_f

H: Sloppy city planning

ほとんど何も関わってないです。2
けっこう難しいんじゃないかと思ってましたがかなり通されていました。まぁこのセットの中だとこの位置になるのはそれはそう。
入力サイズが大きすぎて domjudge にアップロードしようとすると 500 が返ってきて困っていたんですが、システム担当者の方がなんとかしてくださいました。本当にありがとうございます。

C: Track Train Trail

データセットを担当しました。
ただ、急遽入った形だったので自分は解いていません。

内部コンテストでの一幕
区間が交わらないマッチングが区間 DP になるのは典型 90 問にもあったはずなのでわりと一直線かなと思ってたんですが、そもそも中国人郵便配達問題の考え方が「次数が奇数の頂点の最小重み完全マッチングを考える」なのを知っているかどうかがかなり大きかったかもしれません。

I: N-1 Truths and a Lie

ほとんど何もしていないですが、一応 {\bmod 2^{32}} で見ると（32 bit 整数型を使っていると）嘘つきが一人もいなくて困る、というケースだけ追加しました。引っかかった人いるんでしょうか。
あとは制約を満たす（嘘つきがちょうど 1 人いる）入力のランダムな生成方法を提案したりしました。
これは、K 頂点 N-1 辺の矛盾ないグラフ（これは各頂点に適当な値を割り振ればできる）に 1 本間違った辺を足すとき、2 頂点の間に直接の辺がないかつ辺素パスが 2 つ以上あること（＝連結かつ間に橋がないこと）が辺を足せる必要十分になるので、二重辺連結成分分解をしたあと成分内で繋げばよいです。
前日の 27 時までテストケースに橋のあるケースが入っておらず、慌てて追加したりしました。翌日の起床時間 8 時。
実は原案時にはこの問題設定の前にもう一つステップがあったんですが、本番 5 日ほど前に改題されて今の問題になったりしています。

L: Tree Automorphism

データセットを担当しました。
木のハッシュについては前回の模擬地区でも出題されていたのでボーナス枠かなと思っていたのですが、思ったより解かれませんでした。
でも確かに子に同じ部分木があったときに具体的に何倍になるのかパッとはよくわからない気もするので難しいかも。
もし根つき木のハッシュはわかるけど根なし木のハッシュはわからない、という方がいたらあとで調べていただけると……。

F: Seimei Handan 999.0

ほとんど何も関わってないです。3
そんな状態で言うことではないですが、もっと解かれると思っていました。
実際に何の文字であるかはかなりどうでもよくて、どの文字とどの文字が同じかという情報だけ欲しいので、「何文字前と同じか」という情報にしてしまいたいのはかなり自然で、そういう情報が一致することと元のパターンが一致することが同値なのもわりと自然なので、あとはウィンドウをずらしながらロリハを更新していけば良い、とかなり一直線だと思っていました（考察だけして実装してないですが……）。

E: Sharp 2-SAT

ほとんど何も関わってないです。4
本当に考察もしていないので何もわからないですが、とりあえず TLE 解を出す、というチームがもっと出てくると思っていました（まぁ FFT の写経が必要になるのでその方針が正しいかは微妙ですが……）。

K: Sort Compressed Strings

データセットを担当しました。
原案時点ではまぁそこまで難しくないでしょ、というような雰囲気だったんですが、実際に実装してみたらかなり面倒でびっくりしました。
その上で、うまく実装すると log が落ちたりかなり高速になったりするのでそれに合わせた制約、実行時間制限にしたら大変なことに……。
これでも展開後の文字列長の最大値が {10^{18}} から {10^{10}} に変更になっていたり（これは実行時間の問題ではなくハッシュの衝突確率が十分に低い証明ができないことが原因ではありますが）、本番 2 日前に TL を 2 sec から 4 sec に変更していたんですがまだ足りなかったようです。
適当なメモ化で現実的にかなり高速になるのでそういうことをした結果通る、というチームが多いだろうという予想をしていたのですが、コンテスタントから見るとどれくらい惜しい TLE なのかはわからないので難しいですね……。
コンテスト中に、1 ケースだけ 4.2 sec かかって TLE、という惜しいチームがありました。
結果的に 0 AC になってしまったのは調整ミスだと思うのでかなり悔しさがあります。

J: Most distant point from the stations

最初は {N \le 100} くらいで準備されていたと思うのですが、いつの間にか {O(N^2 \log N)} の解法が実装されて {N \le 2{,}000} になっており、泣きながら自分も {O(N^2 \log N)} を実装しました。complex<double>.arg() でソートしたら遅かったので泣きながら整数で比較したりもしました。
どうやらまともなボロノイ図のライブラリを持ち込んでいたチームはいなかったようで、0 AC でした。これ {N \le 100} でもよかったんじゃない？ だめ？

G: Avoid bombings

原案、データセットを担当しました。
問題案がなかなか集まらず、ボス問もない（これはいくつかの問題に対する難易度の過小評価もあった）という状態で、問題選定会議の司会をしながら無理矢理捻り出した問題でした。
一週間くらいかけて泣きながら想定解を実装したはいいが他に誰も実装してくれなかったのでこれは出せなさそうかな……、と思っていたのですが、climpet さんが実装してくださり出せる形になりました。
結局提出数 0 だったので我々の努力が報われることはありませんでした。
ちなみに解説スライドにあたかも元ネタかのように置かれている画像は実は元ネタではなく、原案を出したあとにそういえばこんなミニゲームあったな……、となっただけでした。

その他

前回の模擬地区予選（模擬地区予選 2021）から、自分がコンテスト運営責任者を not さんから引き継いでいました（JAG のページ更新してない気がする……）。自分がまとめ役をするようになってからこれで 3 回目のコンテストでした。まだ not さんなどベテランの方々に頼っている部分もかなり大きいですが。
主な仕事としては、コンテストを企画したり、会議を開いたり、スケジュールを管理したり、セット全体の品質を管理したりなどです。その上で他の人と同じように各問題の担当者に入ったりもしています（手を加えた方が良さそうな部分のヘルプに入るのを中心にしたいため、可能な限り入らないようにしてはいますが）。模擬地区特有のことを言うと、icpcsec に連絡してジャッジを貸してもらったり、貸してもらったジャッジにデータをアップロードする、あたりもしていました。そういえば参加者への連絡も（アカウント通達以外は）自分がやっていましたが、それくらいは他の人にお願いすべきだった気もします。
また、今回は久々のオンサイト開催ということもあり、その辺の調整も自分がやっていました。調整、と言っても会場やスポンサーとちょっと連絡取るだけだろ、と思えるんですが、実際には今回はここに書けないような大変なことがたくさん起こり、心が 5 回くらい折れました。
特にオンサイト周りなどで慣れないところが多かったり JAG の人々の時間的余裕ややる気の度合いがわからなかったりで、他の人に責任やタスクを分散できなかったのがかなりよくなくて、特に問題セットのバランスや品質に影響したような気もしていてそこが反省点ですね……。
特に実装量がちょっと多いとかハッシュを取る問題がちょっと多いとかは準備時に気づいていたので何らかのアクションは取られるべきだったかもしれません。
あとどうでも良い寄りのところだと、思ったよりおにぎりの消費が早かったのでおにぎりとサンドイッチが同じくらいの量でもよかったなとなりました。あとお茶多めにする必要もなかったかも。みんな学生なのでジュース飲むっぽい。

おわりに

改めて、模擬地区予選にご参加いただき本当にありがとうございました。
JAG の問題セットは、数少ないまともな問題案の中からなんとか絞り出しているような感じで、バランス等も安定しているとは到底言えない状況です。そもそも問題案が枯渇しかけていて、来年以降問題セットを作れるかどうかすらわかりません。ICPC 引退した人が JAG に加入して問題をドシドシ提案してくれると、とても助かります。ご検討のほど、よろしくお願いいたします。（コピペ）*1

jag-icpc.org

また、JAG のコンテスト運営責任者に興味のある方も募集しています。一応まだ投げ出す気はないですが、興味のある方がいたらお手伝いいただく（もしくは自分がお手伝いする）のもいいかなと思っています。

最近は特に、作問能力の高い人、モチベーションの高い人が他のコンテストサイトなどに吸われてしまっていてどうしても JAG の作問能力が落ちていてこまっています。まぁうちが完全無償のボランティアなのに対しちゃんと正当な対価が支払われるような場所もあるのでしかたないね。

*1:https://climpet.hatenablog.com/entry/2022/11/27/230943#%E3%81%8A%E3%82%8F%E3%82%8A%E3%81%AB