yukicoder No.1191 数え上げを愛したい（数列編）

• 問題
• AC

条件を満たす数列のすべての要素は互いに異なるので、昇順のものだけ数えて後で$N!$を掛ければよい。

$S_1$が与えられたとき、残りの項は

$f(k) :=$ $1$回の操作で$A$マス以上進むとして、$N-1$回操作してちょうど$k$マス進む場合の数

と考えると形としては$f(A)+f(A+1)+...+f(B)$通りのように求まる。（実際には$S_1+k \le M$であるような$f(k)$までしか足せない）したがって、$f$かあるいはその累積和$F(k) = \sum_{i=1}^kf(i)$が求めれば$S_1 = 1, 2, ..., N$について足せばよいことになる。形式的べき級数で考えると

$$\begin{aligned} f(k) & = [x^k](x^A+x^{A+1}...)^{N-1} \\ & =[x^k]\Bigl(\frac{x^A}{1-x}\Bigr)^{N-1} \\ & =[x^{k-A(N-1)}](1-x)^{-(N-1)} \\ & = [x^{k-A(N-1)}] \sum_{i=0}^\infty \binom{i+N-2}{N-2}x^i\\ & = \binom{k-A(N-1)+N-2}{N-2} \end{aligned}$$

$F(k)$を求めるなら、$(1-x)^{-1}$をもう一つ掛けることになるので$\binom{k-A(N-1)+N-1}{N-1}$となる。

CodeChef August Challenge 2020 - Smallest KMP

• 問題
• AC

最適な文字列がどういう形になっているか考えると、パターンの前後は$a...ab...b \ ...$と$... \ y...yz...z$のようになっているはずなので、$S$から$P$を除いた上でソートしたものを$S'$とし、$P$を$S'$のどこに挿入するのが最善か調べる。$P$を$S'$の$i$文字目に挿入したものと$S'$の$i+1$文字目に挿入したものを比較するとき、この比較は辞書順に関して下に凸になっているので、最小となる場所を二分探索で探せばよい。

CodeChef August Challenge 2020 - Insanely Hard School Exam

• 問題
• AC

1つの色についてだけ考える。平行な2直線がないとすると、直線が$x$本ある時のtruly-geometric triangle（以下TGT）の総数は$\binom{x}{3}$である。これを元に、$\operatorname{dp}[x][y] =$色$x$まで見て消しゴムの残量が$y$である場合のTGTの総数、として全体で${O}(NK)$のDPが可能なのでsubtask2, 3が解ける。

平行線がある場合について考える。平行関係は同値関係なので、異なる同値類の総数を$p$とし、$i$番目の同値類に属する直線が$L_i$個あるとする。$L_1 \ge L_2 \ge ... \ge L_p$と仮定してよい。これらの直線を消していくとき、同値類の総数をできるだけ減らすように消すのが最善なので、後ろから消していくのがよい。そこで$f(c, z) =$色$c$の直線が$z$本残っている場合のTGTの総数、として$f$を事前に求めておけば、上と同じDPで解ける。順序が固定されているので$f$自体もDPで求まる。

CodeChef August Challenge 2020 - Subsequence Frequency Counting

• 問題
• AC

数列$(A_i)$が整数$x$を$c_x$個含むとする。また、整数$x$が代表になるような部分列でちょうど$k$個の$x$を含むものの総数を$f(x, k)$とする。$f(x, k)$を二項係数で表すと、以下のようになる:

$$f(x, k) := \biggl( \sum_{i=0}^{k-1} \binom{c_1}{i}...\sum_{i=0}^{k-1}\binom{c_{x-1}}{i} \biggr) \binom{c_x}{k} \biggl(\sum_{i=0}^{k}\binom{c_{x+1}}{i} ... \sum_{i=0}^{k}\binom{c_N}{i} \biggr)$$

$f(x, k)$を$N$通りの引数について足せばよいが、毎回すべての二項係数を掛け算していては間に合わない。そこで、$\operatorname{dp}[x] := \sum_i \binom{c_x}{i}$という形の列をセグメント木で持っておくことを考える。$\operatorname{dp}$のそれぞれの値が適切な$k$に対応していれば、$f(x, k)$は$\operatorname{dp}[1...x-1]$の積と $\binom{c_x}{k}$と$\operatorname{dp}[x+1 ... N]$の積を掛けて求まることになる。$k=0$から$f$を求めていくとして、$\operatorname{dp}$の末尾から$k$が増えていくので、$k$の昇順、タイブレークは$x$の降順に$f(x, k)$を求めつつ$\operatorname{dp}$を更新していくと、一回の更新が${O}(\log N)$でできる。

CodeChef August Challenge 2020 - Chefina and Strange Tree

• 問題
• AC

与えられたグラフを根付き森とみなすと、ある頂点$v$を消す操作は、$v$のそれぞれの子の部分木と$v$の親側の木とをすべて切り離す操作と考えられる。オイラーツアー(pre-order)上で考えると、部分木は連続した区間に対応しているので、区間を切り貼りすることができればよい（下図）。そこでオイラーツアーを平衡二分木で保持することにする。

平衡二分木に$\min$を載せて、さらに遅延更新で加算ができるようにする。町$P_i$についての処理の流れは次のようになる:

1. $P_i$を含む木$T$（=1つの平衡二分木で表されたオイラーツアー）のすべての頂点の値から$A_{P_i}$を引く。
2. $T$の$\min$を求めて、$0$以下なら$T$上の二分探索で最小値を取る頂点$v$を探す。$v$が$i$日目に$0$になったと記録し、$v$の値を$+\infty$にセットする（再び$0$にならないようにするため。） $\min$が$0$より大きくなるまでこれを繰り返す。
3. 上図のように$P_i$の隣接頂点に関する部分木をすべて切り離す。

1を行う際に、$P_i$を含む平衡二分木を得る必要があるが、永続UnionFindを使った。事前に列$(P_i)$を逆順に走査しながら頂点をつないでおく。$P_i$を（正順に）処理する際には、その時点での$P_i$に対応する（UnionFind上の）根に平衡二分木を持たせるようにした。（でも、ちゃんと前処理すれば普通のUnionFindでできるか。）

計算量は全体で${O}(N\log N)$。

---

明らかに過剰なデータ構造をごちゃごちゃと貼ってしまった。physics0523さんの解説によると、操作の構造自体が木になっていることを利用できるらしい。なるほど……

AGC 037 B - First Second

• 問題
• AC

文字列を反転して条件を言い換えると、文字列$s, t, (|s| \le |t|)$に関する問題の条件は次のようになる。(添え字はPython風に表している)

1. $t$のprefixに$s$の最後の1文字を除いたもの$s[:-1]$が含まれ、
2. さらに$s$の最後の1文字$s[-1]$が$t$のそれ以降に存在する

1つ目の条件だけ考える場合、事前にTrieを作っておけば$s[:-1]$をprefixとして含むような文字列の総数は高速に数えられる。この時、$s[:-1]$をTrieで辿った際の終端ノードに2つ目の条件に関する情報があれば、うまく数えられそうに見える。具体的には、そのノードの部分木に含まれる文字列で$s[-1]$を含んでいるものの数が記録されていれば、2つ目の条件も満たすものが数えられる。

そこで、配列$\operatorname{dp_v}$を$\operatorname{dp_v}[c] :=v$の子に属する文字列で以降に文字$c$を含むものの総数、と定めて、Trieの各ノードに持たせればよい。

アルファベットのサイズを$\alpha$とするとき、この$\operatorname{dp}$配列は各ノードについてならし${O}(\alpha)$で作れるので、全体の計算量は${O}(\alpha\sum_i S_i)$。（一つの子ノードについて、親への遷移はちょうど1回で、遷移の計算量が${O}(\alpha)$。）