前回のコンテスト で重くし過ぎたことを反省してやや軽めにしようと思っていたんですが、結局後ろが大変になってしまいました。
言い訳をさせて頂くと、テスター作業を依頼する前に設定していた難易度は☆1.5 - 2.0 - 2.5 - 3.0 - 3.0 - 3.5 - 3.5 - 4.0でした。
A - Zero-Sum Submatrices
ギャグその①。
2022年に作っていた問題です。前回のF はこの問題からの派生です。
想定解の構築を直接思いつけなくても、解説の後半で説明している再帰的な構築はよく見る気がします。
B - Prime Sum
ギャグその②。
一番最初に考えた設定では構築ありで $X _ i \geq 1$ でした。 この場合は全ての $i$ に対して $X _ i = 1$ とすれば条件を満たすんですが、流石に度が過ぎるかと思い $X _ i \geq 2$ にしました。
この問題のように、与えられたペアを表す辺を張ってできるグラフで考えると上手くいく問題というのはよく見ますが、私は初見で結構感動した覚えがあります。cp-unspoiler とかは結構お気に入りの問題で、競プロの説明に使ったこともあります。
C - Minimize Inversions of Deque
前回の B に引き続いて転倒数に関する問題。
操作を後ろから考えると良い性質が見える問題というのもよくあって、例えば 前回の C もそうでした。
ABCのE, F辺りに置かれそうという印象です。
D - Decreasing Modulo Nim
結論がかなり面白くてお気に入りです。
一番最初に考えた設定は $m \to \infty$ としたものでした。 ただ、これだと通常の Nim の勝敗判定と全く同じになってしまったので、もう一捻り加えました。
明らかに $x$ に関する制約が厄介なので、初手で先手が $x$ を $0$ にしてしまうことを考えようというのが解説の 1 行目の気持ちです。そこから先の考察は比較的素直だと思います。
$x$ という global な (?) 値が存在するので、山毎の Grundy 数を求めて～、という解法は棄却する必要があります。
E - Constrained Permutation
区間スケジューリングを題材に作りました。この問題も性質が綺麗でお気に入りです。
以下のコードに示した貪欲法で $k$ が条件を満たすかを判定できます。
# ranges: 閉区間のリスト def check(k, ranges): n = len(ranges) # 左端の昇順にソート ranges.sort_by_left_bound() # 右端の最小値を管理する優先度付きキュー pq = MinPriorityQueue() j = 0 for v = k+1, k+2, ..., k+n: while j < n and ranges[j].left <= v: pq.push(ranges[j].right) j += 1 # 条件1 if pq.empty(): return False # 条件2 if pq.pop().right < v: return False return True
上記のコードにおける条件1は左端の(多重)集合にのみ依存しており、この部分で False が返らないような条件を考えているのが解説の初手に対応します。
条件2に関しては、直感的には $k$ が小さい方が有利そうであり、実際にその通りであることを解説で証明しています。
証明がやや難しいので、未証明で通した人が多そうです。
F - Trees on Graph Paper
出題方法にかなり悩んだ問題です。
初めは次数 1 の頂点がちょうど $K$ 個の良い全域木を数えたかったのですが、私が解けなかったので次数 1 の頂点の $x$ 座標の積の和という奇妙な設定になりました。DPの遷移が $x$ 座標に依存するようにしたのは Berlekamp–Massey 防止策です。
ナイーブな DP を考えると考えるべき情報が多く遷移を詰めるのが大変ですが、考察を進めると僅か 3 状態のシンプルなDPになります。
解説に余談として書いた良い全域木の個数とフィボナッチ数の関係が面白いです。OEISで解けるので出題は出来ませんが...
G - Generalized Hitting Set
解説に気合が入っているのでぜひ最後まで読んでほしい。
包除のような謎の係数 (この係数の正体は解説②で説明されます) が現れるのが面白いと思っています。 「上位集合系のゼータ変換 → 各点積 → 下位集合系のゼータ変換」というアルゴリズムも個人的には違和感があって面白いと思っています。解説の最後に変種として紹介している問題の解法は更に不思議な感じになっています。
$n = 24$ という過激な制約は、各 $i\in\lbrace 0,1,\ldots,n\rbrace,\ T\subseteq\lbrace 1,2,\ldots,n\rbrace$ に対して $\lvert S _ j \cap T\rvert = i$ を満たす $j$ の個数を数える DP 解 (空間 $\Theta(n 2 ^ n)$ / 時間 $\Theta(n ^ 2 2 ^ n)$) を TL,ML の両方で落とそうとしたためです。
ところで、問題準備中に PyPy に関して謎の現象に遭遇しました。
以下の2つのコードの違いは 40 行目あたりの del b の有無のみなんですが、実行時間が 800 ms 程度も変わっています。
原因が分かる人がいたら教えてください。
H - Sum of Products of Interval Length
唯一解法から作った問題です。
いわゆる(?)同じものの連続に関する包除ですが、その勉強がてら作りました。
積の和典型で上手くDPすれば分割統治FFTで $\Theta(n (\log n) ^ 2)$ 時間で解けるようです。
