NPCAPC 2024 開催記
NPCAPC 2024 の開催記を適当に書き殴ります。開催経緯は文化祭コンがなくなってしまったけど何かしら有志コンをやりたいな～と思っていたら前向きな後輩が割といたので実際にやることにしました。
文化祭コン程の規模では出来ないものの、灘校生として作る最後のコンテストなので面白いものを作れたらいいなと思っていました。
以下それぞれの問題について適当に思ったことを書きます。
A - Welcome to NPCAPC(writer：kohenyan)
始めは NPCA と npca を含む文字列の個数で N <= 2e5 のみだったが、行列累乗で解けるのでとりあえず N <=1e9 にすることに。
ちゃんと考えると割と次数の低い母関数を持ちそうだったので行列累乗と区別するために NPCA を NPCAPC にしてマルチテストケースにしました。行列の累乗なので母関数を持つのはそうだが、考察をすると次数が落ちるのが嬉しいポイント
B - Some Sum of Subset(writer：number_cat)
普通の中難易度枠だな～と思った。N,M,sum A <= 2e5 でも解けるが writer 本人にどちらで出すかは任せた。
C - Solve with Friends(writer：number_cat)
簡単枠が欲しいな～と思ったら出してくれたので助かった。このセットで一番簡単な問題想定です。
D - Two Box(writer：PCTprobability)
始めは 2 次元グリッドでいくつかマス目を選ぶ設定だったが解けなくて色々弄ってたらこの設定になってとりあえず Q = 1 は解けていた。クエリにしても解けるのが面白かったので出題してみた。このセットの中の最高難易度枠です。
E - Aim High(writer：PCTprobability)
友人からコンウェイの兵隊という問題を聞いて面白かったので競プロで出題したいなと思って少しだけ設定を変えて出題しました。知識枠みたいなところもありますが、有志コンなのでこういう問題もいいかな。
F - Train Seats(writer：fact493)
N <= 2000 の状態で原案が飛んできた。少し考えてると端から取るのが最適そうだったのでそれで 2000 diff くらいかな？等考えていたが、なんとか N <= 2e5 で解けないかな～と 1 週間くらい悩んでいるとなんとか解けた。
結構変わったタイプの解法 + かなり高難易度ということで気に入っている。このコンテストで D と同じ最高難易度枠です。
G - Many Common Segment Problems(writer：PCTprobability)
いつもの Many なんちゃら Problems です。この言い換えは昔どこかで見たような気がするが忘れてしまった。log を 3 個から 2 個に落とすパートは面白いと思います。
H - Music Game(writer：akinyan)
いい感じにソートを出来るたまに見かけるやつ。今回も隣接する 2 個についてぐっと睨むと比較が出来るようになります。
I - Left Equal Right(writer：number_cat)
いい感じの簡単枠 2 個目です。条件を満たす i が高々 1 個なのに気付くといい感じに dp が回ります。
J - Again Inversion Problem(writer：PCTprobability)
O - Simple Inversion Problem
この問題のオマージュです。こどふぉに置換群のサイズを計算するブログがあって気になって読んでみたらかなり面白かったので少しだけ捻って出題しました。
K - Peace with Magic(writer：number_cat)
始めは H_i = ... = H_j という条件がなく変わりに H_i の高さが与えられていたが改題された。改題後の方が面白いと思った。
L - Construction of Town(writer：PCTprobability)
考えていたら出来たギャグ枠。ARC には投げられないのでせっかくなら有志コンに投げてみました。有志コンなのでこういうのもいいんじゃないでしょうか。
M - Admired Person(writer：number_cat)
いい感じの簡単枠 3 個目です。ここらへんの難易度を沢山生やしてくれるのはかなり助かった。
N - Product Matrix(writer：PCTprobability)
等比数列で補間する場合 log が 1 個でいいというアルゴリズムを出したかったがかなり出し方が難しかった。Nyaan さんと話していたらこの形に落ち着いたが、行列積を O(n^2 d log d + n^3 d) でやる等の高速化が早く厳しい TL になってしまった。
ただアルゴリズム自体は面白いと思うので是非解説を読んでもらいたい。
O - New School Term(writer：number_cat)
始めこの制約で提案されるも writer 解の嘘が発覚した。だがよく考えるとその制約でも解けたので元の制約のままになった。
枝刈りで (a,b) + (c,d) -> (a+c,b+d) が失敗したか？を持つものが O(N^(7/3)) で正当なのが面白かった。
P - Make Testcase(writer：PCTprobability)
かなり天才問だと思う。だが内部の問題が ABC 既出で微妙だったので AR/GC で没になって有志コンに流れてきた形になった。(そのため UC にも出せず)
全体の感想
これで私が灘校生として作成するコンテストは最後だが、有終の美を飾れるコンテスト出来たと思っている。文化祭コンテストのときからも始め、灘でのコンテストにはかなり思い出があるので感慨深い。
割と崖の厳しいセットになってしまった気はするが部分点を割と入れたのでいい感じになっていると思いたい。
tester 作業が終わらず地獄を見ている人がいたが、それはまた別のお話...