ICPC模擬地区予選2022 準備記

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

スタッフとして現地にいたほか、問題準備にも携わっていました。問題セットや解説などはそのうちアップロードされると思います。以下、担当の問題に対する感想です。

E: Sharp 2-SAT

データセットを担当しました。

当初、入力をランダムに生成したら、充足不能なものばかりできてしまい困りました。最終的には、変数の割り当てをいくつかランダムに決めて、それに矛盾しない節をランダム生成、という方法を取りました。

時間制限は 8 秒になっています。分割統治のたびに (I)FFT が 48 回必要なので、定数倍が軽いとは言えないものの、一応 Java でも 4 秒くらいあれば通ったので、ちゃんと実装すれば時間制限はそこまでキツキツではないはずです。

F: Seimei Handan 999.0

原案・データセット・解説を担当しました。

Parameterized matching に帰着させてロリハ・(K)MP・Z などで解けます。どのみち重複除去のためにロリハ (か、さもなくば接尾辞配列等) を実装する必要があることもあり、まあロリハで解かれるだろうなと思っていました。実際そうだったんですが、1 チームだけ Morris-Pratt で解いたチームがあってびっくりしました。正当性は自明というわけではないので、知っていたのではないかと思います。

Parameterized matching の部分は論文そのままで解けるので、もうちょっとひねりを加えられないかと考えてはみたのですが、思いつけなかったのでそのままになりました。とはいえこの概念を知っている人が参加者の中に 1 人くらいしかいなかったような気がするので、杞憂だったかもしれません。検索ありのルールだったらもっと解かれていたんでしょうか。

G: Avoid bombings

問題文・テスターを担当しました。

実装したくないなぁとずっと思いつつ、一週間くらい前につらみを感じながら実装始めました。こんなもの誰も解かないだろと思っていたら、案の定提出は 0 件だったので、我々の苦労が報われることはありませんでした。

円弧がなければライブラリゲーなので、円弧の代わりに微小線分の折れ線で近似する、という解法も実装してみました。ジャッジ解の正当性の検証には役立ったものの、精度を妥協してもなお実行時間が分単位になったので、本番これで解けることはないと思います。

ジャッジ解自体の精度にも不安があったので、実は許容誤差が問題文記載のものの 1.1 倍に緩和されていたりします。この配慮が生きることはありませんでした。

H: Sloppy city planning

原案・問題文を担当しました。Insane Connection Plan City (ICPC) という、命名の時点で常軌を逸した、一方通行だらけな上に強連結とは限らない都市が舞台です。強連結にしたところで根本的に住心地が改善するとはあまり思えません。絶対住みたくないですね。

本家の ICPC で完全グラフ関連の問題が出ていたこと、制約次第では (特に国内予選形式では) Warshall-Floyd 回すだけで解けるということもあり、模擬国内 D-E にちょうどいいかなと思い、2019 年に提案していました。長らく使われなかったので日の目を見ることはないと思っていました。

3 乗時間解法を落とすために頂点数が最大 3000 と大きくなっていますが、そのせいでファイルサイズが大きすぎて、ジャッジシステムへのアップロードに失敗するというトラブルもありました。制約を落とすという案もありましたが、最終的にはシステム担当者が頑張ってくれたので、そのまま出題できました。感謝です。

I: N-1 Truths and a Lie

線形時間解法の方針の一つ (ちょっと間違っていた) を提案しましたが、未実装です。あと、N=1 が問題文の記述に反せずコーナーケースになっていることを指摘し、最終的には制約で弾くことになりました。お誕生日系のコンテストだったらそのまま出ていただろうなぁと思います。

J: Most distant point from the stations

特にかかわってはいないんですが、幾何 2 問もいる？と内心思っていました。いらなかったと思います。ボロノイ図の実装ってどれくらい大変なんでしょう。

K: Sort Compressed Strings

原案を担当しました。

構文解析パートは本家で 2 回 (国内2006、国内2019) と模擬で 1 回 (模擬国内2019) 出ているということもあり、典型と言っていいでしょう。とはいえ最初のを除き構文解析パート以外が本質です。AtCoder などで構文解析が出題されることは少ないので、練習機会の提供という意味で言うと、ほぼ純粋な構文解析問題みたいなのもあった方が良かったりするんでしょうか。

展開後の文字列長の上限について、原案時点では 10^18 文字になっていたんですが、ハッシュの衝突確率の評価がやばくなるという指摘を hos さんより受け、今の形になりました。それはさておき、1e9+7 など有名 mod を落とすケースは入っているようなので、注意しましょう。mod (2^61)-1 の方法などがおすすめです。

…と書いてみたはいいものの、実は原案出しておきながらまだ実装していないので、どのあたりが難しいのかわかっていません。実装してみたらかなりハチャメチャになるという噂ですが、果たして。

それと、個人的にローリングハッシュはあんまり好きではなくて、deterministic な解法が無いかと模索してはみたのですが、見つけられませんでした。誰か思いついたら教えてください。

L: Tree Automorphism

原案を担当しました。

部分木のハッシュの衝突に注意しましょう。map<子のソート済みハッシュ列, 新たなハッシュ値> を管理するようにすると、多少遅くなるかもしれませんが、衝突の可能性を考慮せずに済みます。ただし全方位木 DP には使えません。

実装上の工夫として、辺を倍化すると答えが変わらない上に場合分けが減るんですが、これをしたチームはほとんど見ませんでした。そもそも全方位木 DP (?) っぽい方法で解いてるように見えたチームもありましたが、楽なんでしょうか。よくわかりません。

おわりに

JAG の問題セットは、数少ないまともな問題案の中からなんとか絞り出しているような感じで、バランス等も安定しているとは到底言えない状況です。そもそも問題案が枯渇しかけていて、来年以降問題セットを作れるかどうかすらわかりません。ICPC 引退した人が JAG に加入して問題をドシドシ提案してくれると、とても助かります。ご検討のほど、よろしくお願いいたします。
jag-icpc.org