キャディプログラミングコンテスト2021 (ABC 193) F - Zebraness

• 問題
• AC

マスを二つに分類する最適化問題なので、最小カットで解けないかと思ってyosupoさんの記事で解ける条件を確認する。

「Xが赤で、Yが青ならZ円の報酬」
「Xが赤で、Yが赤ならZ円の罰金」
は最大カットになって解けないと思います。

この問題は異なる色に塗ると得になる制約なので、解けそうにない……と思ったが、市松模様の一方の色を反転すると、同じ色なら得になる制約に変換できる。

$10^4$頂点なので一般のフローアルゴリズムで解けるのかわからなかったが、とりあえず書くと通った。

Dinicの計算量について
https://misawa.github.io/others/flow/dinic_time_complexity.html

Toph - Subset of Master Shifu

• 問題
• AC

更新がなければwavelet matrixで解ける。更新がある場合、更新が起こる位置が高々6種類しかないことを利用できそう。列$B$を$A_1, ..., A_6$をそれぞれ含む/含まないという分類によって、$2^6 = 64$個の列に分解すると、更新は個々の部分列に対する定数加算として記録できる。質問クエリに対しては、各部分列の$[L, R]$に対応する区間について「$X$以下の要素は何個あるか？」という問いに答えられれば、その総和が$K$以上となるような最小の$X$が答えになるので二分探索できる。これはやはりwavelet matrixでできる。

計算量は、$A= \max(\max_i A_i, \max_i C_i), P=\max_i P_i$として、クエリあたり${O}((\log (AN))^2 2^P)$となる。（二分探索とwavelet matrixの処理が共に${O}(\log (AN))$。）かなり重いが$Q=10^4$で3秒なのでぎりぎり通る。

editorialを読んだ。ほぼ同じことをやっているようだが、wavelet matrixを64個用意する必要はなくて、1個用意すればほかはその列全体に定数を足したものになっている。確かに。オーダーは変わらないがだいぶ速くなった。

CodeChef - Little Elephant and Movies

• 問題

制約を見て三乗想定かと思ったら二乗想定だった。

${O}(N^2K)$解

$P_1 \le P_2 \le ... \le P_N$と仮定してよい。また、$f(i) :=$ 映画$i$と同じpriorityを持つ映画の中でもっとも右にあるものの位置、とする。$P_0 = 0$としておくと都合がよい。

$\operatorname{dp}[x][y][z] = x$本映画を見た時点で、今までに見た映画で最もpriorityの高い映画の位置（タイは最初に見たものを優先）が$y$で、現在のexcitingnessがzであるような場合の数

でDPできる。

遷移について。$x < f(y)$ならexcitingでない映画が$f(y)-x$個あって

$$\operatorname{dp}[x+1][y][z] \mathrel{{+}{=}} (f(y)-x)\operatorname{dp}[x][y][z]$$

excitingな映画$y' = f(y)+1, f(y)+2, ..., N$については

$$\operatorname{dp}[x+1][y'][z+1] \mathrel{{+}{=}} \operatorname{dp}[x][y][z]$$

素朴にやると${O}(N^3K)$だが、累積和を取りながら遷移して${O}(N^2K)$。$(P_i)$のsuffixがタイになっている場合に、最後にそれらを全部足す必要があることに注意。

${O}(NK)$解

Editorialを見たら${O}(NK)$想定だった。同じpriorityの映画をまとめて、降順に挿入していけばよい。（リンク先参照）

Myers, Wilf. Left-to-right maxima in words and multiset permutations

discussionに載っていた論文。この問題とわずかに違って同じpriorityの映画は区別できない設定だが、考え方は同じで、区別できるようにするには各priorityの頻度の階乗を掛けるだけ。

よく考えるとこれはDEGwerさんの数え上げPDF（3.探索順の変更）に載っている典型とほぼ同じだった。

CodeChef - Expected Greatest Common Divisor

• 問題
• AC

答える数が特殊。$y=P \cdot Q^ {-1}$が$\mod 10^9 + 7$で求まっているとき、$N \equiv -y$である。

$\gcd$の期待値を求める問題だが、総和が求まればよい。

GCDごとに求める典型を思い出す。$f(X, r) := |\{(x_0, ..., x_{N-1}) \in X : \gcd(x_0, ..., x_{N-1}) = r\}|$とする時、求める総和は$\sum_r rf(X, r)$と表せる。最大公約数の代わりに公約数を考える: $F(X, r) := |\{(x_0, ..., x_{N-1}) \in X : r が x_0, ..., x_{N-1}の公約数\}|$。$r$ が $x_0, ..., x_{N-1}$の公約数であることは$x_0, ..., x_{N-1}$がすべて$r$の倍数であることと同値で、これは成分毎にわけて数えられる。つまり、$[A_i, B_i]$中の$r$の倍数の数が$\lfloor B_i / r \rfloor - \lfloor (A_i-1) / r \rfloor$で、$F(\prod_i [A_i, B_i], r) = \prod_i \bigl( \lfloor B_i / r \rfloor - \lfloor (A_i-1) / r \rfloor \bigr)$と計算できる。$F(X, r) = \sum_{r|m} f(X, m)$なので、$f$は$F$のメビウス変換で得られる。

全体の計算量は、$B= \max B_i$として${O}(BK + B\log\log B)$。$\lfloor A / r \rfloor$が高々${O}(\sqrt A)$種類の値しか取らないから、頑張れば${O}(K \sqrt B)$でできる？

ABC162 Eがこれの簡単バージョンだったことを思い出した。

CodeChef - MST queries

• 問題

最初のMSTに使われなかったいくつかの辺の重みが0になったとする。path optimality conditionを考えると、それらの辺を全域木に加えてできたサイクルから最大重みの辺を除く、を繰り返せば最適になるので、最初の全域木に使われている辺+重み0になった辺だけでMSTを求めても正しい結果が得られる。重みを元に戻した時も、「最初のMSTに使われなかった辺がいくつか0になった状態」であることには変わりないので同じである。したがって、重みが$0$になっている辺と最初の全域木に使われた辺だけを見て毎回Kruskalなどをするという方針は正しい。

ただ、更新クエリによって重み0の辺が増えていくと、質問クエリで走査する辺の数は結局${O}(Q+N)$になってしまうので厳しそうに見える。各時点での重み$0$の辺によるconnectivityをundo可能Union-Findに保持しておいて(offline dynamic connectivity)、毎回そこからKruskalをする方針だと辺の数は${O}(N)$のままなので、全体の計算量は${O}(Q (\log Q + N)\log N + M \log M)$にはなりそう。これでもぎりぎりに見えるが…… → 解説を見た。掛かる定数が小さいので${O}(Q + N)$でよいということらしい。

• 愚直Union-Find 1.46 sec.
• offline dynamic connectivity 1.01 sec.

undo付きにするとUnion-Findが遅くなるのでどうかと思ったけれど、一応速くはなるらしい。

CodeChef - Chef and Array

• 問題

区間の半数を超える同一要素(dominator)があるかどうか判定するクエリ問題。一点更新もある。

方針 1

Editorialの方針。

2つの区間を合併するとき、ある要素が合併後の区間で半数を超えるためには、2つの区間のうちの少なくともいっぽうで半数を超えていなくてはならない、ということを利用できる。

セグメント木の各ノードに、区間内の各要素の出現頻度を保持するマップと（存在すれば）区間のdominatorを保持しておく。質問クエリに対しては、質問の区間がセグ木上の${O}(\log N)$個の区間に分割できるので、${O}(\log N)$個のdominatorの候補を、${O}(\log N)$個のマップに関して調べる。${O}(N \log N + Q \log^2 N)$だが、ハッシュテーブルを使う${O}(\log^2 N)$なのでかなり重い。

https://www.codechef.com/viewsolution/42694801 1.63 sec.

方針2

$n, k$を決めておいて、質問クエリの度に区間から$n$回無作為に要素を抽出して$k$回以上出現した要素についてrange frequency queryを適用してdominatorかどうか調べる。

正答率を評価するには二項分布のCDFを調べればよい。たとえば100回抽出して17回以上出現した要素について調べることにすると、確率1/2で成功する試行を100回繰り返して成功回数が16回以下になる確率が$10^{-11}$以下で、$10^5$個の質問に対して少なくとも1回間違える確率は$10^{-6}$以下と求まる。

https://www.codechef.com/viewsolution/43903194 0.68 sec.

方針 3

rajat1603さんの書き込みより。

区間内でトーナメントのようなことをする。セグメント木の各ノードに$(x, 残っているxの数)$を保持することにして、葉$(a_i, 1)$から

$$(x_1, c_1) \oplus (x_2, c_2) = \begin{cases} (x_1, c_1 + c_2) \qquad \text {if} \ x_1 = x_2 \\ (x_1, c_1 - c_2) \qquad \text {else if}\ c_1 \ge c_2 \\ (x_2, c_2 - c_1) \qquad \text{otherwise} \\ \end{cases}$$

という演算でマージしていくと（結合法則は成り立たないが）マージの順番や区間の大きさによらず、dominatorは必ず残る。実際に残った要素がその区間でdominatorかどうか判定するためにはrange frequency queryに答えらればよい。${O}((N+Q) \log N)$。

https://www.codechef.com/viewsolution/42748384 0.22 sec.

方針4

anudeep2011さんの書き込みより。

区間の長さの閾値$B$を適当に決めて、長さ$B$未満の区間は愚直に判定する。

長さ$B$以上の区間については、その区間のdominatorは与えられた列中に$B/2$個より多く含まれることを利用できる。具体的には、列中に$B/2$個より多く存在する数については個別にBIT等を作っておいて、range frequency queryに答えられるようにする。このような数は高々$2N/B$種類しかないので、質問に対しては$2N/B$個のBITをすべて調べれば答えられることになる。

前処理: ${O}(N \log N \cdot (N/B))$ 質問クエリ（長さ$B$未満）: ${O}(B)$ 質問クエリ（長さ$B$以上）: ${O}((N/B) \log N)$ 更新クエリ: ${O}(\log N)$

$B = \sqrt { N \log N}$とすると${O}((N+Q) \sqrt {N \log N})$。

yukicoder No. 1392 - Don't be together

• 問題
• AC

スターリング数のような設定（ボールは区別できる、箱は区別できない、各箱に1つ以上のボールが入る）の数え上げはスターリング数のようなDPができる、という典型を思い出す。

とりあえずスターリング数と同じように$f(x, y) := 1, 2, ..., x$を$y$個のグループにわける場合の数、と定める。$P_x < x$の場合はスターリング数と同じような遷移^[1] $f(x, y) = f(x-1, y-1) + (y-1)f(x-1, y)$が成立しそうだが、$x < P_x$だと$P_x$の所属するグループに関する未来の情報が必要でうまくいかない。DPするにはもう少し変数を増やす必要がある。

与えられるのは順列なので巡回置換に分解してみる。整数の順序は関係ないので、$(1 2 3 4)(5 6)(7 8 9)$のように各巡回置換が連続区間に対応しているものだけ考えればよい。このとき、$f$を次のように定義すればDPできる:

$f(x, y, z) := 1, 2, ..., x$を$y$個のグループにわけるとして、$x$が$x$の属する巡回置換の先頭の整数と同じグループに属する$(z=1)$か異なるグループに属する$(z=0)$場合の数。

---

1. 遷移の意味付けはdrkenさんの記事を参照。 ↩︎

CODE FESTIVAL 2014 決勝 H - 部屋割り

• 問題
• AC

$i$人目が入る部屋の人数は決まっていて、シミュレーションで求まる。$i$人目が$f[i]$人の部屋に入ったとする。また、

• $\operatorname{dp}[i][x] := i$人が部屋に入った時点で$x$人部屋であるような部屋の、最終的な人数の期待値
• $\operatorname{num}[i][x] := i$人が部屋に入った時点で$x$人部屋であるような部屋の数

とすると、後ろからDPできる:

$$\operatorname{dp}[i][f[i+1]] = \frac{\operatorname{dp}[i+1][f[i+1]+1] + \operatorname{dp}[i+1][f[i+1]]\operatorname{num}[i+1][f[i+1]]}{\operatorname{num}[i+1][f[i+1]] + 1}$$

$\operatorname{num}[i][f[i+1]] = \operatorname{num}[i+1][f[i+1]] + 1$
$\operatorname{num}[i][f[i+1]+1] = \operatorname{num}[i+1][f[i+1]+1] - 1$

更新箇所が定数個しかないので、in-placeにDPすれば${O}(N)$になる。$i$人目に関する期待値は$\operatorname{dp}[i][f[i]+1]$に等しい。