コンテストでの時間切れや解けなかった過去問を振り返って供養していく

6/22: AtCoder Grand Contest 046 C - Shift

供養

問題

Difficulty: 2084 (記事作成時点)

$S$ 中の 0 の数を $z$ とすると、問題は $|S| - x$ 個の 1 を $z + 1$ 個の区間に配置した初期状態から、1つ選んでそれが置かれていた区間より左にあるいずれかの区間に再配置するという操作を最大 $K$ 回実施したときの配置のパターン数となる
$\mathit{DP}_{i, j, k}$ を $i$ 番目の区間以降で $j$ 個選び、そのうち $k$ 個を再配置した状態のパターン数とする
区間で行う操作は
- 何もしない
  - $\mathit{DP}_{i, j, k} = \mathit{DP}_{i + 1, j, k}$
- 1個以上の 1 を再配置する
  - $\mathit{DP}_{i, j, k} = \sum_{l = 0}^{j - 1} \mathit{DP}_{i + 1, j, l}$
- 1個以上の 1 を選ぶ
  - - $C_{i}$ は区間 $i$ に最初に配置された 1 の数
- 再配置と選ぶ動作は同時には行わない
$\sum \mathit{DP}_{1}$ が答となる

実装は

配列 $C$ を用意し、 $c = 0$ とする
について、下記の操作を実施する
- $S_{i} =$ 0 ならば $c$ を $C$ の末尾に追加し $c = 0$ とする
- $S_{i} =$ 1 ならば $c = c + 1$ とする
$c$ を $C$ の末尾に追加する
$C$ の先頭要素を削除する
$M = |C|, K = \mathrm{min}(\sum C, K)$ とする
$(M + 1) \times (K + 1) \times (K + 1)$ のDP表 $\mathit{DP}$ を用意し、 $\mathit{DP}_{M, 0, 0} = 1$ とする
について、以下の操作を実施する
- について、以下の操作を実施する
  - $c = 0$ とする
  - について、以下の操作を実施する
    - $c = c + \mathit{DP}_{i + 1, j, k}$ とする
    - $\mathit{DP}_{i, j, k} = \mathit{DP}_{i, j, k} + c$ とする
- について、以下の操作を実施する
  - $c = 0$ とする
  - について、以下の操作を実施する
    - $\mathit{DP}_{i, j, k} = \mathit{DP}_{i, j, k} + c$ とする
    - $c = c + \mathit{DP}_{i + 1, j, k}$ とする
    - $j \ge C_{i}$ ならば $c = c - \mathit{DP}_{i + 1, j - C_{i}, k}$ とする
$\sum \mathit{DP}_{0}$ を出力する

計算量は $O(N^{3})$

供養

Difficulty: 1325(estimated) (記事作成時点)

$S$ を $i$ 文字目までと $i + 1$ 文字目以降で分割し、それらの最長共通部分文字列の長さを $L_{i}$ とすると、 $N - 2 \times \mathrm{max}(L_{i})$ が答えとなる
最長共通部分文字列はDPで求められる

実装は

計算量は $O(N^{3})$

~~公式解説~~

供養

Difficulty: 1878 (記事作成時点)

$1 \le i \lt j \le N$ である任意の $(i, j)$ について、 $A_{i} \ne A_{j}$ かつ $B_{i} \ne B_{j}$ であるという条件だけにする
任意のについて、ならばであるようなの個数は
- $N$ 個のうち $S$ 個は共通で選び、残りの $N - |S|$ 個は独立して選ぶ
包除原理より、が求める答えとなる
- $\mathcal{S}$ は $S$ のとりうる集合の集合
$(-1)^{|S|}X_{S}$ は $|S|$ にのみ依存するので、 $|S|$ が等しくなる項をまとめると $\sum_{k = 0}^{N} {}_{N}\mathrm{C}_{k} \times (-1)^{k} \times {}_{M}\mathrm{P}_{k} \times ( {}_{M - k}\mathrm{P}_{N - k} )^{2}$ で計算できる

実装は

$0 \le k \le M$ について、 $F_{k}, G_{k}, I_{k}$ でそれぞれ $k!, k!^{-1}, k^{-1}$ を求めておく
長さ $N + 1$ の配列 $P$ を用意し、 $P_{0} = 1$ とする
$i = 1, \dots, M$ について、 $P_{i} = P_{i - 1} \times (M - i + 1)$ とする
長さ $N + 1$ の配列 $Q$ を用意し、 $Q_{0} = P_{N}$ とする
$i = 1, \dots, N$ について、 $Q_{i} = Q_{i - 1} \times I_{M - i + 1}$ とする
$A = 0, s = 1$ とする
について、以下の操作を実施する
- $A = A + s \times {}_{N}\mathrm{C}_{k} \times P_{k} \times Q_{k} \times Q_{k}$ とする
- $s = -s$ とする
$A$ を出力する

計算量は $O(M + N)$

供養

Difficulty: 2159 (記事作成時点)

$X = A_{3} \oplus \dots \oplus A_{N}$ としたとき、 $(A_{1} - d) \oplus (A_{2} + d) = X$ であるような $0 \ge d \lt A_{i}$ の最小値を求める
$A_{1} + A_{2} = (A_{1} - d) \oplus (A_{2} + d) + 2 \times ( (A_{1} - d)\;\mathrm{AND}\;(A_{2} + d) )$ と表せる
としたとき、上式は（解が存在すれば）と表せるので、と表記できる
- $S - X \lt 0$ もしくは $(S - X) \% 2 = 1$ のときは解なし
- また、 $D$ と $X$ に共通で立っているbitがあるときも解なしとなる
$X$ のbitを2つに分けた $Y, Z$ (i.e. $Y + Z = X, Y \oplus Z = X, Y\;\mathrm{AND}\;Z = 0$ )を考えると、 $A_{1} - d = Y + D, A_{2} = Z + D$ と表せる
$X$ の上位bitから見ていって、 $Y + D \lt A_{1}$ となるように $Y$ を決めていけばよい

実装は

$X = 0$ とし、 $2 \le i \lt N$ について $X = X \oplus A_{i}$ とする
$S = A_{0} + A_{1}$ とし、 $S \gt X$ もしくは $(S - X) \% 2 = 1$ ならば -1 を出力して終了
$D = \frac{S - X}{2}$ とし、 $D\;\mathrm{AND}\;X \ne 0$ ならば -1 を出力して終了
配列 $B$ を用意し、 $x = X$ とする
となるまで以下の操作を繰り返す
- b = x\;\mathrm{AND}\;(-x) とし、 $x = x - b$ とする
- $b$ を $B$ の末尾に追加する
$i = |B| - 1, \dots, 0$ について、 $D + B_{i} \le A_{0}$ ならば $D = D + B_{i}$ としていく
$D = 0$ もしくは $D \gt A_{0}$ ならば -1 を出力して終了
$A_{0} - D$ を出力する