https://csacademy.com/contest/round-11/summary/
整数$A, B$が与えられる。区間$[A, B]$に含まれる整数のなかで、1種類の数字のみで構成されるものの数を出力せよ。
$A, B\leq 10^6$なので、$[A, B]$に含まれるすべての整数について条件を満たすかどうか調べればよい。
自力AC。簡単。
ある少女がキーボードを用いて自分の名前を入力しようとしているが、少女はキーを押す際に誤って同じキーを何度も入力してしまうことがある。文字列$A, B$が与えられるので、少女が$A$を入力した結果誤って$B$が入力されることがありうるかどうかを判定し、判定結果を出力せよ。
$A, B$を前から同じ文字を{(a), (bb), (ccc)}のようにまとめて、条件を満たしているかどうか愚直に判定すればよい。
自力AC。難しくはない(2WA)。
$N$頂点$M$辺のグラフが与えられる。このグラフに以下の操作を繰り返し行う。
グラフを連結にするために必要な操作回数の最小値を出力せよ。
グラフの辺を1つずつ見ながら、Union-Find Treeを用いて頂点の連結成分を管理することができる。ここで、すでに連結であるような点対を結ぶ辺は別の場所に移動させてもよいので、このような辺をメモしておく。与えられたグラフの連結成分が$C$個あるとすると、移動可能な辺が$C-1$本以上存在すればグラフを連結にすることができる。実際にこれを行うには、それぞれの連結成分から代表として頂点を1つずつ取り出して、これらの$C$頂点を辺で結べばよい。
自力AC。素直な発想で解ける問題。同じことをDFSを用いて行うのが想定解らしい。
$N$要素の数列がある。この数列の$S$番目の要素は1であり、その他はすべて0である。この数列に以下の操作を繰り返し行うことを考える。
ここで、一連の操作の途中で1が存在してはいけない場所が$M$個指定されている。すべての$i$について、$i$番目の要素を1にするために必要な操作回数の最小値を求めよ。
(0-indexedで)$i$番目の要素が1であるとき、1を区間$[i-K+1, i+K-1]$の範囲内に移すことができる。ただし、$K$が奇数のときは$i$からの距離が偶数のindexに、$K$が偶数のときは$i$からの距離が奇数のindexにしか移せない。ここで、$i$が数列の左端から$K$個以内の場合は区間の左端が$K-i-1$に、右から$K$個以内の場合は区間の右端が$2N-i-K-1$になる。
$S$からBFSを行うとこの問題が解けるが、普通にやると$O(NK)$となり間に合わない。ここで、std::setを使って未到達のindexを管理することを考える。$i$から到達できるindexは区間になっているので、二分探索を使えば未到達かつ$i$から到達できるindexに高速にアクセスできる。それぞれのindexはsetから一度ずつeraseされるので、時間計算量は$O(N\log N)$となる。
解説AC。これは解けないと駄目だった。
$N$頂点の木が与えられ、この木の各頂点に1から$N$までの番号を振ることを考える。以下の性質を満たすような番号の振り方の数を$10^9+7$で割ったあまりを出力せよ。
問題文の条件を満たす番号の振り方は、1を根とした有向木についてトポロジカル順序となるような番号の振り方であると言いかえることができる。ここで、頂点1を根とした場合に有効な番号の振り方を数える方法を考える。
これは木DPで求めることができて、DPテーブルを
$DP[idx]=(val, size)=$頂点$idx$を根とする部分木の(有効なトポロジカル順序の数, 部分木のサイズ)
として
$$DP[idx]=\left(\frac{(DP[idx].size-1)!}{\prod DP[son].size !}\times DP[son].val, \sum DP[son].size \right)$$
で更新できる。これをすべての根について行えば答えを求められるが、計算量が$O(N^2)$となるので間に合わない。ここで、このDPを全方位木DPにすることを考える。つまり、DPテーブルを
$DP[a][b]=(val, size)=$頂点$a$から頂点$b$に向かう向きの、$b$を根とする部分木の(有効なトポロジカル順序の数, 部分木のサイズ)
として、最初に頂点1を根としたDPテーブルを普通に計算する。このとき、頂点1から出ていく向きの辺についてはDPテーブルの値が求められているが、頂点1に向かう向きには計算できていないという状況になる。ここで、ある頂点$idx$に入る向きのDPテーブルを更新するためには$idx$から出ていく向きのDPテーブルがすべて計算されていればよいので、頂点1に入る向きのDPテーブルは既に更新できる。すると頂点1の子に入る向きのDPテーブルが更新できるようになる。このようにして、頂点1からDFSしながらすべての頂点についてDPテーブルを更新していけばDPテーブルが完成する。最後にすべての頂点について、その頂点を根としたときのトポロジカル順序の数を計算して足し合わせればよい。
解説AC。この問題の解説を読んだ後に実装せず放置していたらABC160Fに全く同じ問題が出て、しかも参加してない回だった。悲しい。
すべての要素が$[0, K]$であるような$N$要素の数列のなかで、すべての要素のxorが0ではないようなものの数を出力せよ。
DPテーブルを
$DP[i][x]=$長さ$i$の整数列で、総xorが$x$となるようなものの数
とする。ただし、$x$の最大値は$x=2^k-1$となるような整数のなかで$K\leq x$となる最小のものである。更新は
$DP[i+1][x]=\sum_{x\oplus y \leq K} DP[i][y]$
と表せて、愚直に計算すると$O(NK^2)$となる。これを行列で表したとき、たとえば$K=5$であれば
$$\left( \begin{array}{rr} DP[i+1][0] \\ DP[i+1][1] \\ DP[i+1][2] \\ DP[i+1][3] \\ DP[i+1][4] \\ DP[i+1][5] \\ DP[i+1][6] \\ DP[i+1][7] \\ \end{array}\right) = \left( \begin{array}{rr} 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array}\right) \left( \begin{array}{rr} DP[i][0] \\ DP[i][1] \\ DP[i][2] \\ DP[i][3] \\ DP[i][4] \\ DP[i][5] \\ DP[i][6] \\ DP[i][7] \\ \end{array}\right) $$
となる。ここで、$K\leq 50000$なので、単純な行列累乗では間に合わない。ただし、この遷移行列$A$には行列$X, Y$を用いて
$$A= \left( \begin{array}{rr} X & Y\\ Y & X\\ \end{array}\right)$$
と表せるという性質があり、さらに$X, Y$も同様の性質をもつので、これを用いて高速に行列の累乗が計算できる。遷移行列$A$が$2^k\times 2^k$正方行列であることを利用して、$2^k\times 2^k$のアダマール行列
$$H_{2^k}=\frac{1}{\sqrt{2}} \left( \begin{array}{rr} H_{2^{k-1}} & H_{2^{k-1}} \\ H_{2^{k-1}} & -H_{2^{k-1}} \\ \end{array}\right) $$
を両側から掛けると
\begin{align*} H_{2^k}AH_{2^k} &= \frac12\left( \begin{array}{rr} H_{2^{k-1}} & H_{2^{k-1}} \\ H_{2^{k-1}} & -H_{2^{k-1}} \\ \end{array}\right) \left( \begin{array}{rr} X & Y \\ Y & X \\ \end{array}\right) \left( \begin{array}{rr} H_{2^{k-1}} & H_{2^{k-1}} \\ H_{2^{k-1}} & -H_{2^{k-1}} \\ \end{array}\right) \\ &= \left( \begin{array}{cc} H_{2^{k-1}}(X+Y)H_{2^{k-1}} & O \\ O & H_{2^{k-1}}(X-Y)H_{2^{k-1}} \\ \end{array}\right) \\ &= \left( \begin{array}{cc} H_{2^{k-1}}XH_{2^{k-1}} + H_{2^{k-1}}YH_{2^{k-1}} & O \\ O & H_{2^{k-1}}XH_{2^{k-1}} - H_{2^{k-1}}YH_{2^{k-1}} \\ \end{array}\right) \end{align*}
となる。対角成分のブロックも再帰的に計算すると、これは対角行列であることがわかる。これを累乗して、最後にアダマール行列を両側から掛けることで、$A$の累乗を得る（アダマール行列は、それ自身がアダマール行列の逆行列である。）
ここで、遷移行列$A$に両側からアダマール行列を掛ける操作を考える。$K\times K$行列にアダマール行列を掛ける操作は、通常の方法ではすべての列に対して高速ウォルシュ-アダマール変換を用いることで$O(K^2\log K)$である。この問題では、$H_{2^k}AH_{2^k}$が対角行列になることがわかっているので非対角成分を計算する必要がなく、さらに対角成分を構成する2つのブロックは$X, Y$に両側からアダマール行列を掛けたものの線型結合で表せる。さらに$X, Y$にも同様の性質があるので、これを用いて対角成分だけを再帰的に計算することで$O(K\log K)$となり、対角行列の$N$乗は対角成分のみ計算すればよいので$O(K\log N)$で計算できる。
可能な数列は$(K+1)^N$通り存在し、その中から総xorが0になるものを除いたものが答えである。さらに、初期状態として$DP[0][0]$のみ1であり、それ以外はすべて0であることから、$A^N$を完全に復元する必要はなく、$\left( A^N \right)_{0, 0}$のみが分かればよい。これは簡単に計算できる。
解説AC。知識として高速ウォルシュ-アダマール変換を覚えたが、この問題では使わなくても解くことができた。この問題はなぜか公式Editorialがないので、pekempeyさんのブログ記事を参考にしながら解いた。一応CSA内にも解説っぽいものがあるが、よく読んでいない。
整数の区間が$N$個与えられ、これを最大で$K$個のグループに分けることを考える。各グループのスコアは、そのグループに含まれる区間の共通部分の長さである。合計スコアの最大値を出力せよ。
前提として、すでに区間が入っているグループにさらに区間を追加してスコアが増えることはない。このことから、最適なグループ分けではスコアが0のグループ（共通区間がないグループ）が高々1つしかないことが言える。スコア0のグループが2つ以上あるなら、一方が正のスコアとなるまで区間をもう一方に移し替えることで必ずスコアを上げられるからである。
よって、最適なグループ分けは以下の2種類のうちのどちらかである
スコアが0のグループが1つの場合のなかで最適なグループ分けを構築するのは簡単で、区間を長い順にソートして、上から$K-1$個を1つずつグループに分けたあと、最後の1つを全部同じグループにすればよい(この方法で最後のグループがスコア0にならない場合には、スコア0のグループがある状態が最適になることはない)
以下、スコアが0のグループがない場合について考える。このとき、以下のようなことがいえる
これは、区間$[L_i, R_i]$が別の区間$[L_j, R_j]$を含むとき、両者を同じグループに入れることで常に区間$[L_i, R_i]$の存在を無視できるという意味である。一方で、区間$[L_i, R_i]$を単独のグループとすることもできる。よって、別の区間を含まないような区間をうまくグループ分けできれば、全体の最適なグループ分けは貪欲に求めることができる。
別の区間を含まないような区間だけを集めたとき、これらの区間を左端と右端の座標どちらでソートしても同じ順番になる。ここで、最適なグループ分けのなかに、あるグループに属する区間がこの順序において必ず隣り合っているような分け方が存在することがいえる。そうなっていない場合、たとえばグループ$j$に属する区間がグループ$i$に属する区間に挟まれている場合には、挟まれている区間をグループ$i$に変えても損しないからである。
ここで、別の区間を含まないような区間の集合に対して、以下のようなDPを考える
$DP[i][j] = i-1$番目までの区間(以下、区間$[0, i)$と表記する)を$j$個のグループに分けたときの最大スコア
遷移は $$DP[i][j] = \max_k\{ DP[k][j-1] + (R_k - L_i) \}$$ が考えられ、これは全体でO($N^2K$)であるが、制約より$K\leq N\leq 6000$なので間に合わない。
このDPを高速化することを考える。まず、以下のようなことがいえる。
これは当たり前のことに見えるが、つまり$DP[a][j-1] + R_a \leq DP[b][j-1] + R_b$が成り立っているなら、それ以降$DP[i][j-1]$の計算をするときに$DP[b][j-1] + (R_b - L_i)$は最大値になりえないので、最初から考える必要がないということを意味する。
考えなくてよいindexを管理するために、dequeを用いることができる。$DP[i][j]$を計算するとき、dequeの中には$i$以下のいくつかのindexが入っていて、これらのindexを$k_1, k_2, ..., k_r$とすると、$DP[k_1][j-1] + R_{k_1} \gt DP[k_2][j-1] + R_{k_2} \gt ... \gt DP[k_r][j-1] + R_{k_r}$を満たす。
ここで、$L_i \geq R_{k_1}$ならば$k_1$を考える必要がないので、これをpopしてよい。なぜなら、現在考えているのがスコア0のグループを含まない場合の最大スコアであり、$L_i \geq R_{k_1}$のとき区間$[k_1, i)$のスコアが0になってしまうからである。このようにして、$L_i \lt R_{k_1}$となるまでpop_frontする。
さらに$DP[k_r][j-1] + R_{k_r} \leq DP[i][j-1] + R_i$であれば、前述の理由から$k_r$を考える必要がないのでpop_backする。これを$DP[k_r][j-1] + R_{k_r} \gt DP[i][j-1] + R_i$となるまで繰り返したあと、dequeに$i$をpush_backする。
今、$DP[k_1][j-1] + R_{k_1} \gt DP[k_2][j-1] + R_{k_2} \gt ... \gt DP[k_r][j-1] + R_{k_r}$を崩すことなくdequeに$i$を追加することができた。ここで、$DP[i][j] = DP[k_1][j-1] + R_{k_1} - L_i$であることがわかる。
このようにして、全体でO($NK$)でDPテーブルを埋めることができる。最後に、$DP[$他の区間を含まない区間の数$][j]$について、他の区間を含む区間から長いものを貪欲に単独のグループにして$K$グループになるまで補填したものの最大値をスコア0のグループを含む場合の最大スコアと比較して、大きい方が答えである。
解説AC。AGC040Bの、グループの数が一般の場合である。解説を理解するのにめちゃくちゃ時間がかかってしまった。editorialではIOI2002の問題を類題として紹介している(というより解説を丸投げしている)が、すでにリンクが切れており、現在のURLは問題、解説である。実際のところ、不等式の性質からdequeでindexを管理する方法は
$DP[i][j]=i$番目までを$j$個のグループに分ける場合の最大値/最小値
というDPをする場合に使える解法のうちの1つということだろうか。このような場合に汎用的に使えるなら、かなり用途は広そうな感じがする。