---
tags: メモ
---
# yukicoder contest #343 メモ

https://yukicoder.me/contests/380

## A

ありがちな条件だし何か場合分けのいらない式があるだろと考えると、XOR が該当
素直に場合分けした方が早かった

## B

水の量の総和が $100$ で、$4$ つに分けるので、状態数が $\binom{103}3 \times 4 \approx 7 \times 10^5$ 以下
メモ化再帰でループ検出をすると解ける

ところで実行時間からして状態数はもっと少ないように見える

容器 $M$ 個で考える。

カーソルのある容器は満タンであるか、他の容器の容積と同じ量
最も小さい容器は必ず満タンになる

$V_i < V_{i + 1}$ だと $V_{i + 1}$ はスルーされてしまうので $V_{i + 1} ← \min(V_i, V_{i + 1})$ として良い ← $2$ 周目以降影響してくるので嘘

$\min\{V\}$ 分の水量は常に回り続けるので、全部から $\min\{V\}$ を引いて $\min\{V\} = 0$ として良い


$1$ 周目と $2$ 周目でそれぞれ埋まる場所の図

$100, 2, 100, 1$ のときが最悪ケースで、状態数が $400$ くらい

$N = 10^5$ 、容積いっぱいでも解ける雰囲気を感じる

## C

[limit_denominator](https://docs.python.org/ja/3/library/fractions.html#fractions.Fraction.limit_denominator) が強力そう

float で二分探索をすると、めちゃくちゃ WA が出る
Fraction のまま二分探索をすると、AC

え、$P + Q$ なのか、天才？

## D

$N ≤ 16$ なので、bit でどうにか

$2^i$ 人使ってトーナメントを作り、勝者が $j$ である

$8^2\binom{16}8\binom88=8.2 \times 10^5$
$4^2\binom{16}4\binom{12}4=1.4 \times 10^7$

## E

ラグランジュ補間を考えると、$2$ 点を除いて $0$ で、$1$ 点で $1$ みたいな関数を列挙して線型結合をすれば良い

$X=x_0$ で $1$ 、$X = x_i$ で $0$ になる関数

$$
f(X) = \prod_{i=1}^n\frac{X - x_i}{x_0 - x_i}
$$

$F_i$ (抜ける点それぞれ) ごとにこれを計算するのは難しいが、$x_0$ ( $1$ になる点) ごとにこれを計算するのは差分更新が効く
分子が $0$ になるのがめんどい
分数のまま計算することで log mod を掛けないテク
これ通分しておかないと

## F

間を詰めるのか…
色の他に番号も付いているので、間に何か挟まっているやつと、単に連結したやつを区別できる

$f$ : 答え (空列を含む)
$g$ : 分離できないひとかたまり

として、

$$
g = x\sum_{l}(xf)^{l-1}\\
f = \frac{1}{1 - g}\\
f = 1 + fg\\
f = 1 + \sum_l (xf)^l\\
$$

どうするのこれ

ラグランジュの反転公式らしい　どうやって？

$F = xf$ とすると、
$$
F = x(1 + \sum_lF^l)\\
\frac{F}{1 + \sum_lF^l} = x\\
G = \frac{x}{1 + \sum_lx^l}\\
[x^N]F = \frac{1}{N}[x^{N-1}](1 + \sum_lx^l)^N\\
[x^N]f = \frac{1}{N + 1}[x^N](1 + \sum_lx^l)^{N+1}\\
$$

は〜〜
pow of FPS (sparse) で $O(NM)$　そうだね〜　いやすごいな

勉強になった

$F = 1 + \sum_lx^l, G = F^{K + 1}$ とすると、

$$
\log G = (K + 1) \log F\\
G' / G = (K + 1) F' / F\\
FG' = (K + 1) F' G\\
(1 + \sum_lx^l)G' = (K + 1)(\sum_l l\cdot x^{l-1}) G\\
N G_N + \sum_l(N - l)G_{N-l} = (K + 1)\sum_l l \cdot G_{N-l}\\
N G_N = \sum_l(Kl + 2l - N)G_{N-l}\\
$$