65:09 で完走しました。
解説は公式解説があるので、感想を書きます。
C - 偏ったサイコロ
$$\mathsf{dp}(i, j) \coloneqq 1 \text{ 個目から } i \text{ 個目までの出目の和がちょうど } j \text{ である確率}$$
として dp を書いたけど、想定解は出目の全探索だったらしい。
D - 採点
$u \leq v$ となるように swap してから set に入れるのはやや面倒なので、std::minmax(u, v) を insert すると楽。
E - 棒倒しゲーム
題意の理解に時間が掛かった。$s$ を $R$ 個の連続部分列に分ける方法であって、各連続部分列が $1$ ラウンドに対応するようにできるかという問題。
左端を固定すると、右端の候補は
- 連続部分列の和が $N$ 以上になる最初の位置
- $\text{左端}+ M - 1$
- $L$
のうち最小を調べれば十分。この方針に従って前から連続部分列を取り除いていき、以下を調べれば十分。
- 取り除いた連続部分列の個数がちょうど $R$ か
- 取り除いた連続部分列たちが全て $1$ ラウンドの要件を満たすか
サンプルは 1 つめの条件を調べなくても合うので忘れないよう注意 (これで WA を出しかけた)。
F - 薬剤師
目に入る制約がいかつくて構えたけど、よく見るとクエリ毎に全探索しても十分間に合うようになっている。
ただ、「$y$ が $X _ i$ に含まれるか？」という問いには十分高速に答えられるよう前処理しておく必要がある。
H - ３種の硬貨
これは個人的な癖かもしれないけど最初に考えたのは
- 貰う金貨の最大化
- 払う銀貨の最小化
- 払う銅貨の最小化
で、これだと最大と最小が入り混じって比較が面倒。最大化に統一して次のようにすると、operator< で比較できる (std::tuple<int, int, int> で表現した場合)。
- 貰う金貨の最大化
- 残りの銀貨の最大化
- 残りの銅貨の最大化
この方針に従って dp テーブルを定義すると公式解説と同じものになる。
I - 毎日のリンゴ
迷わず ACL の floor_sum を貼ったけど、想定解 1 を見て確かにになった...
J - スプリンクラー
手計算した式を書くだけなんだけど、計算に時間が掛かってしまった。
K - 連結チェック
Dynamic Connectivity を借りて貼ろうかとも思ったけど、自重。
L - 展覧会
最終的な状態を全探索するテクを久しぶりに見た気がする。
M - シリーズ
C - 蛍光灯 という全く同じ問題がある。初見で感動して記憶に残っていたのですぐ反応できた。
N - 上からと横から
$2$ 数の積の上限が決まっていると小さい方は上限の sqrt 以下になるという典型。AOJ の問題で初めてこの典型を知った気がするけど、どれだったか思い出せない。
O - ２個のボール
多次元畳み込み。
$$\begin{aligned} f(x, y) &= \sum _ {i = 0} ^ {2 ^ N - 1} A _ i x ^ {i} y ^ {\mathsf{popcount}(i)}, \\ g(x, y) &= \sum _ {i = 0} ^ {2 ^ N - 1} B _ i x ^ {i} y ^ {\mathsf{popcount}(i)}. \end{aligned}$$
とする。$x$ に関する積は $x ^ i \bullet x ^ j = x ^ {i \mathop{|} j}$ で、$y$ に関する積は $\ y ^ i \circ y ^ j = y ^ {i + j}$ として $f$ と $g$ の積を計算すればよい。
この積は subset zeta 変換 (x 方向) -> DFT (y 方向) -> 各点積 -> inv DFT (y 方向) -> subset mobius 変換 (x 方向) で計算できる。(or convolution 自体も $\mathrm{mod}\ (x _ 1 ^ 2 - x _ 1, x _ 2 ^ 2 - x _ 2, \ldots, x _ N ^ 2 - x _ N)$ の多次元畳み込みではある)
