うにゅーん、って感じだ

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

もぎちく2021非公式コメンタリ

ICPC

（この記事に書かれた内容は全て個人の見解であり、所属する組織の公式見解ではありません）

問題文、順位、解説等は以下のページで公開されています。 jag-icpc.org

注意：以下には問題のネタバレが含まれます

自分の想定していた難易度順に問題を見ていきます

A: Harvest（AC チーム数：35）

データセットを担当していました。最も簡単な問題ということもあり境界値データとか用意するの忘れていたんですが、ちゃんと WA や TLE が出ていて（かつ全チーム AC していて）良かったです。

B: Parse the Syntax Tree（AC チーム数：34）

びっくり簡単枠です。最近の ICPC 横浜では A とか B とかに見た目やばいけど実は簡単な問題が出る印象があった（個人の見解です）ので B に置きました。
問題文中に書いてある構文に沿って再帰関数で計算してもいいですが、実は . を全て無視して左下から Queue とかを使って適当に計算してもできます（詳しくは解説 pdf を）。

H: include（AC チーム数：34）

SCC 貼るだけ枠です。意図的に（？）入次数 0 の頂点のみを選択してもサンプルが合うようにしていたらしく、そんな感じの提出が何件か来ていた気がします。

G: Pizza delivery（AC チーム数：29）

隣接した 2 つを swap した方が嬉しい条件を見つけるいつものです。データセットを担当していました。もしかしたら {t_i, a_i \le 1{,}000} という制約に戸惑わされた人がいるかもしれないですが、答えを 64bit 整数に収めるための処置でした。データセット作成係としては何も考えずにランダムに作ってもいい感じの入力が作れて嬉しい。

I: (N+1)-legged race（AC チーム数：32）

すでに AC 数と想定難易度順に逆転が起きていますね…。当初 DP 解が発見されておらず、そこそこの考察をしたのち set を使う解法が想定だったんですが、実はもっと単純な DP 解が存在していました。本番で解いたチームもほとんどが DP だったのではないでしょうか。

K: Zombie Land 2（AC チーム数：20）

ん……？ ちょっと幾何の要素が入った普通枠のつもりでした。ある二人が距離 D 以下になる区間さえ求まれば、あとは {O(V^2)} ダイクストラみたいな要領で各人がいつゾンビになるかわかります。誤差の評価にそこまで自信がないので、もし誤差のみが原因で落ちている人がいたらかなり申し訳ないです。
ところで問題文を担当していました。読み比べればわかるんですが、ほぼ過去の JAG 夏合宿の問題 Zombie Land の丸パクリです。まぁ解法全然違うしセーフということで…。 onlinejudge.u-aizu.ac.jp

あと、コンテスト中に既出？が発覚しました。 onlinejudge.u-aizu.ac.jp

C: Permutation Magic（AC チーム数：24）

最小費用流を流す問題でした。おそらく辞書順最小を求めるところが問題になる気はしますが、そこで {O(M^2)} 回最小費用流を流すのが通ってしまったようです。まぁおそらく遅いフローの {O(M^4 \log M)} と速いフローの {O(M^5 \log M)} を区別するのは困難なため……。

J: Isomorphic?（AC チーム数：25）

データセットを担当していました。輪っかにくっついてる木の hash を求めて、そうしてできた 2 つの hash 列が反転、rotate によって一致するか調べる問題でした。前半部分は「根付き木　ハッシュ」とか調べるといくらでも出てきて、後半部分は Z-Algorithm や Rolling-Hash でできます。
YesNo だと簡単に嘘解法が通りそうだったので実は対応関係を復元する問題にするつもりだったのですが、自分の対応が遅れてしまい結局 YesNo のまま出しました。終わってみれば復元を要求しなくて正解だったかもしれません。
代わりにテストケース生成はちょっと頑張って、最低限適当すぎるコードは通らないようにしたつもりです。本番でも結構な提出を落とせていて良かった（ただ一つ問題があって、問題の性質上木のハッシュが衝突しまくり、みたいな嘘は基本的に落とせない）。

D: MFP: Most Fluctuated Player（AC チーム数：22）

最初に出うる得点を座圧しておいて、自分以外のせいで起こった変動を上手く遅延するといい感じになるやつです（最初に出うる得点を座圧しておいて、自分以外のせいで起こった変動を上手く遅延するといい感じになるやつとは？）。

F: qarentheziz zepuence（AC チーム数：4）

原案と問題文を担当しました。どうやらセグ木とか平方分割に変なものを乗せるのが人よりちょっと得意らしい。
当初想定解が {O(N \log N + Q \sqrt N \log N)} で {N, Q \le 10^5} だったのですが、{\Theta(NQ)} を確実に落とすのが難しく、かつ {O(N + Q \sqrt N)} になったので少し制約が大きくなりました（すまん！）。それでも 3 並列だし 10 チームくらい通すと思っていたので、ちょっと意外ではありました。

準備をしながら、この辺の問題に似てるな思いを馳せていました。 atcoder.jp onlinejudge.u-aizu.ac.jp

自分のジャッジ解を置いておきます（もしどこかバグっていても責任を負いません） jag_regional_2021_F_riantkb.cpp · GitHub

E: Underground's SUNDAY（AC チーム数：4）

問題文を担当しました。原案では日食みたいな問題設定だったんですが、空に浮いたあの多角形はなんだ……？ となって今回の問題文になりました。ちょっとだけ Undertale をイメージしています。
ところで、原案では凸多角形だったり円の中心が通る直線と平行な辺が存在しなかったりしました。どうしてこんなことに。準備段階でも y 軸に平行な辺とかではちゃめちゃバグらせたので、5 時間の間で冷静にデバッグができるかゲーかなと思っています。

自分のジャッジ解を置いておきます（もしどこかバグっていても責任を負いません） jag_regional_2021_E_riantkb.cpp · GitHub

ところで

JAG ではメンバーを募集しています。 やる気がある人やボス問を作れる人や問題準備を手伝ってくれる人やテスターをしてくれる人ややる気以外何もない人などの加入を心よりお待ちしています。 jag-icpc.org