HackerEarth - Connected Permutations

• 問題
• AC

求める数を$a_n$とする。長さ$n$の順列を先頭$k$要素が$1, 2, ..., k$の順列であるような最小の$k$で分類して数えると、それぞれ$a_k(n-k)!$通りある。長さ$n$の順列から長さ$n+1$の順列を作ることを考えると、$n+1$は$k$箇所に挿入可能なので$a_{n+1} =\sum_{k=1}^{n}ka_k(n-k)! = \sum_{k=0}^nka_k(n-k)!$。$a_0=0, a_1=1$としてオンラインFFTすると${O}(N \log^2 N)$で解ける。

CodeChef SnackDown 2021 Online Qualifiers - Minimise Difference

• 問題
• AC

問題: 無向グラフが与えられる。出次数の最大値が最小であるようなacyclic orientationを求めよ。

出次数が$D$以下であるacyclic orientationが存在するかどうかの判定問題が解ければよい。判定問題は次のように解ける:

まだ選んでいない頂点の中でトポロジカル順序で先頭にする頂点$v$を自由に選ぶ。この$v$の次数は$D$以下でなければならず、そのような頂点が存在しなければ判定はNOである。存在する場合、$v$から伸びているすべての辺を削除する。以上を頂点の数だけ繰り返す。実装はキューで${O}(N)$でできる。

エクサウィザーズプログラミングコンテスト2021 (ABC 222) G - 222

• 問題
• 提出

与えられた数列を$(a_i)_{i = 0}^\infty \ (a_0=0, a_1 = 2, a_2 = 22, ...)$とする。$M = \begin{bmatrix} 10 & 2 \\ 0 & 1\end{bmatrix}, v= \begin{bmatrix} 0 \\ 1\end{bmatrix}$とするとき、$a_k$は$M^k v$の第一成分に等しい。従って、問題は$v = M^kv$であるような最小の正整数$k$を求めることと言い換えられる。

この問題はbaby-step giant-stepで解ける。$B= \lceil \sqrt K \rceil$とする。$a_0, a_1, a_2, ..., a_{B-1}$について$\mod K$での値をmapのキー、添字をmapの値として保持しておく。（キーが重複する場合、そこでサイクルに入るので、それまでに$0$が見つかっていなければ打ち切ってよい。） $k= iB-j$, $j \in \{0, 1, ..., B-1\}$とする時、$v = M^kv$が成り立つためには$M^j v = M^{iH}v$が成り立つ必要がある。したがって、$i=1, 2, ..., B$について$M^{iB}v$を計算して$a_{iB}$を求め。この値が先に作ったマップに入っていれば対応する添字$j$を取り出すと$k=iB-j$が答えの候補になる。ただし、$M$は正則とは限らないので、$M^j v = M^{iB}v$は必要条件でしかない。つまり、$a_{iB-j} \mod K$が必ず$0$になるわけではない。実際に$M^{iB-j}v$を計算して確認する必要がある。

ハッシュテーブルを使った場合の期待計算量は${O}(\sqrt K)$。

ABC 221 H - Count Multiset

• 問題
• AC

分割数っぽい数え上げなので分割数っぽいDPを考える。

まずは分割数のDPを思い出す。自然数$n$を$k$個の正整数の和に分割する場合の数を$P(n, k)$とする。分割の中に1を含まないものは$n-k$の$k$分割のすべての項を$1$増加させて得られ、分割の中に1を含むものは$n-1$の$k-1$分割に1を付加すれば得られるのだった。漸化式で表すと

$$ P(n, k) = P(n-k, k) + P(n-1, k-1) $$

このDPを、同じ数を$M$個より多くは含まないという制約（以下、単に制約と呼ぶ）に合うように修正することを考える。制約付きの分割の総数を$P'(n, k)$とする。

上の遷移の一つ目の項、つまり分割の中に1を含まないものを$n-k$の$k$分割のすべての項を$1$増加させて得る場合については、制約はそのまま守られるのでこのままでよさそう。一方、二つ目の項、つまり、分割の中に1を含むものを数えたい場合、このままだと1を$M+1$個含むものも数えてしまうことになるので、これを除きたい。

$n$の$k$分割で$1$をちょうど$M+1$個含み、他は制約を満たしているようなものの総数 = $n-(M+1)$の$k-(M+1)$分割で1を含まず、かつ制約を満たしているようなものの総数 = $n-(M+1)- (k-(M+1))$、つまり$n-k$の$k-(M+1)$分割で、制約を満たしているようなものの総数

と言い換えると、最後の量は$P'(n-k, k-(M+1))$に等しいので、漸化式は

$$ P'(n, k) = P'(n-k, k) + P'(n-1, k-1) - P'(n-k, k-(M+1)) $$

となる。

---

スターリング数っぽい数え上げがスターリング数っぽいDPでできる、はけっこう見るけど、分割数っぽい数え上げではうまくいく問題を見た記憶がなくて、遷移を考え始めるまでに時間がかかった……が、例えばJOI 2009 予選 F - ビンゴ がそうだったのを思い出した。

第八回 アルゴリズム実技検定

満点だった。

L - K番目の絶対値

総和の絶対値が$D$以下であるような連続部分列を数える問題が解ければよさそう。累積和$S_i = A_1 + ... + A_i$上で言い換えると各$i$について$|S_i-S_j| \le D$であるような$j < i$を数えればよく、これは$S_0, S_1, ..., S_{i-1}$の中で$[S_i-D, S_i+D]$に含まれるようなものを数えることに等しい。数え上げを${O}(N \log N)$で解くと、全体で${O}(N \log N \log \sum_i |A_i|)$。

順序対を数えることにすれば尺取りでできる。確かに。

M - バランス

SoundHound Inc. Programming Contest 2018 Masters Tournament E - + Graph

O - 色分けトーナメント

• トーナメントは$2 \cdot 2^N-1$頂点の完全二分木とすると、制約$(W_i, L_i)$は$W_i$と$L_i$のLCAまで$W_i$と$L_i$が勝ち上がって$W_i$が勝つこととみなせる。
• ある選手を青に塗ると決めても赤に塗ると決めても有効な塗り方は同数ある。（どの有効な塗り方についても、すべての色を反転したものが有効な塗り方であるため。）

$\operatorname{dp}_v[x] =$頂点$v$を根とする部分木に属する左から$x$番目の選手の色を決め打った時に、部分木$v$に属する選手の塗り方で（部分木$v$に含まれる制約を満たし、かつ）$v$が勝ち上がるようなものの総数、とする。$\operatorname{dp}_v$は$v$の子を$c_1, c_2$として$\operatorname{dp}_{c_1}, \operatorname{dp}_{c_2}$から線形で作れるので、下から処理していけばよい。根に関する$\operatorname{dp}$の総和を2倍したものが答えになる。

各深さの$\operatorname{dp}$の長さの総和はちょうど$2^N$になるので、全体の計算量は${O}(N 2^N + M)$。