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

3/8: diverta 2019 Programming Contest E - XOR Partitioning

供養

問題

Difficulty: 2371 (記事作成時点)

解法

とする
- $b_{0} = 0$ である
$A_{i_{j}}\;(1 \le j \lt k)$ で $k$ 個の区間に分割するとする
分割した区間のXORが全て $X$ で等しくなるとき、 $b_{0}, b_{i_{1}}, \dots, b_{i_{k - 1}}, b_{N}$ は $0, X, 0, X, \dots$ という数列になる
$b_{N} \ne 0$ のとき、下記の $X = b_{N}$ の場合のみ考えればよい
$b_{N} = 0$ のとき、 $X = 0$ および $1 \le X \lt 2^{20}$ のそれぞれの場合の結果の合計を求める
$X = 0$ のとき、 $1 \le i \lt N$ かつ $b_{i} = 0$ の直後を区切りとするかという場合分けなので、 $1 \le i \lt N$ かつ $b_{i} = 0$ の個数を $Z$ とすると、 $2^{Z}$ 通り
のとき、もしくはのときのみに着目する
- の数列をRun Length Encodingし、とする
  - $z_{j}, x_{j}$ はそれぞれ $j$ 回目の連続した $0, X$ の長さを表す
- $C_{0} = 0, C_{X} = 1$ とする
- について下記のように更新していく
  - $C_{0} = C_{0} + C_{X} \times x_{j - 1}$
  - $C_{X} = C_{X} + C_{0} \times z_{j}$
- $b_{N} = 0$ ならば $C_{0}$ 、 $b_{N} \ne 0$ ならば $C_{X}$ が求めるパターン数

実装は

3次元配列を用意し、についてとする
- 表記の簡略化のため $C \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack$ を $C_{i, j, k}$ と表記し、末尾要素の添字を-1とする
$b = 0, Z = 1$ とする
について以下のように更新していく
- $b = b \oplus A_{i}$ とする
- $b = 0$ のとき、 $Z$ を1加算する
- $b \ne 0$ のとき、 $C_{b, -1, 0} \lt Z$ ならば $\lbrack Z, 0 \rbrack$ を $C_{b}$ の末尾に追加する
- $C_{b, -1, 1}$ をインクリメントする
上記更新終了時に $b = 0$ のとき、 $1 \le i \lt 2^{20}$ について $\lbrack Z, 0 \rbrack$ を $C_{i}$ の末尾に追加する
のときのパターン数を計算する関数を作成する
- $z = 0, x = 1$ とする
- について下記のようにの順に更新していく
  - $z = z + x \times C_{X, j - 1, 1}$
  - $x = x + z \times (C_{X, j, 0} - C_{X, j - 1, 0})$
- $b = 0$ ならば $z$ 、 $b \ne 0$ ならば $x$ を返す
$b \ne 0$ のとき、 $\mathrm{Count}(C_{X}, b)$ を出力する
$b = 0$ のとき、 $2^{Z - 2} + \sum_{X = 1}^{2^{20} - 1}\mathrm{Count}(X, 0)$ を出力する

計算量は前処理に $O(N)$ 、 $X \ne 0$ の計算は $X$ の登場回数について線形なので、合計で $O(N)$

公式解説

躓いた点

RLEの発想がなくTLE
RLE時に0の登場回数のカウント方法を間違えた

3/9: AtCoder Beginner Contest 158 E - Divisible Substring

供養

問題

Difficulty: 1849 (記事作成時点)

解法

$P = 2 \lor P = 5$ のとき、[P] で割り切れるかは評価した数の1の位が $P$ で割り切れるかのみに依存するので、 $S_{i} = P \lor S_{i} = 0$ であるような $1 \le i \le N$ の合計値が答えとなる
以降を評価した数値をとすると、からを評価した数はと表せる
- $e_{N + 1} = 0$ とする
が割り切れるかはが割り切れるかであり、それはの剰余が等しいかで判定できる
- について、の剰余にの剰余を足していくことでの剰余を高速に計算できる
  - $s_{i}$ は $S_{i}$ を評価した数である
  - $0 \le n \le 9$ について $n \times 10^{k} _{\mathrm{mod}\;P}$ の数列は長さが高々 $P$ の $M_{n}$ の循環数列となるので、 $M_{n}$ を事前に求めておけば $s_{i} \times 10^{N - i}$ の剰余を定数時間で求められる
$i = N, \dots, 1$ について $e_{i}$ の剰余を計算し、剰余が等しい $e_{j \gt i}$ の数を足し合わせていったものが答えとなる

実装は

$P = 2 \lor P = 5$ ならば $1 \le i \le N$ について $S_{i}$ が $P$ で割り切れる数字ならば $i$ を加算していって合計を出力する
二次元配列 $M$ を用意する
について下記操作でを構成する
- $n^{'} = n \% P$ とし、 $n^{'}$ を $M_{n}$ の末尾に追加する
- $M_{n}$ が循環するまで $n^{'} = n^{'} \times 10 \% P$ と更新しながら $n^{'}$ を $M_{n}$ の末尾に追加していく
配列 $E$ を用意し、 $E_{0} = 1, e = 0, A = 0$ とする
について、下記操作を実施する
- [tex; M_{S_{i}, (N - i) \% |M_{S_{i}}|}] を $e$ に加算する
- $E_{e}$ を $A$ に加算する
- $E_{e}$ をインクリメントする
$A$ を出力する

計算量は $M_{n}$ の前計算に $O(P)$ 、 $e_{i}$ を合計 $O(N)$ で求められるので、合計で $O(N + P)$

公式解説

躓いた点

$e_{l} - e_{r + 1}$ の形式を作れなかった
$P = 2 \lor P = 5$ の場合分けを忘れてWA
$e_{i}$ の計算の高速化で失敗してWA

3/10: AtCoder Beginner Contest 158 F - Removing Robots

供養

問題

Difficulty: 1975 (記事作成時点)

解法

任意のロボットを起動したときに連鎖的に起動するロボットはロボットの起動順に依らない
- ロボット $i$ を起動するとロボット $j$ も起動するとき、先にロボット $j$ を起動した状態でロボット $i$ を起動しても結果は同じ
ロボットが初期位置の昇順にソートされているとする
ロボットを起動したことで最終的に起動するロボットの最大値をとすると、について、と求めていくことができる
- 二分探索で見る範囲を決めて、Segment Treeで最大値を探してUpdateすればよい
以降のみ考慮したパターン数をDPで数える
- $i$ を起動しないパターンを $\mathit{dp}_{i, 0}$ 、 $i$ を起動するパターンを $\mathit{dp}_{i, 1}$ とする
$\mathit{dp}_{N + 1, 0} = 1, \mathit{dp}_{N + 1, 1} = 0$ とし、 $i = N, \dots, 1$ について、 $\mathit{dp}_{i, 0} = \mathit{dp}_{i + 1, 0} + \mathit{dp}_{i + 1}$ 、 $\mathit{dp}_{i, 1} = \mathit{dp}_{R_{i} + 1, 0} + \mathit{dp}_{R_{i} + 1, 1}$ と求められる

実装は

$(X_{i}, D_{i})$ を $X_{i}$ について昇順にソートする
Segment Tree を用意し、についてSegment Treeの番目の要素がとなるように初期化する
- 以降、Segment Treeの $i$ 番目の要素を $\mathit{ST}_{i}$ と表記する
について、以下の操作を実施する
- $X_{i} \le X_{j} \lt X_{i} + D_{i}$ である最大の $j$ を求める
- $\mathit{ST}_{i} = \mathrm{max}(\mathit{ST}_{i}, \dots, \mathit{ST}_{j})$ と更新する
二次元配列 $\mathit{DP}$ を用意し、 $\mathit{DP}_{N + 1, 0} = 1, \mathit{DP}_{N + 1, 1} = 0$ とする
$i = N, \dots, 1$ について、 $\mathit{DP}_{i, 0} = \mathit{DP}_{i + 1, 0} + \mathit{DP}_{i + 1}$ 、 $\mathit{DP}_{i, 1} = \mathit{DP}_{\mathit{ST}_{i} + 1, 0} + \mathit{DP}_{\mathit{ST}_{i} + 1, 1}$ とする
$\mathit{DP}_{1, 0} + \mathit{DP}_{1, 1}$ を出力する

計算量は $O(N\mathrm{log}N)$

公式解説

躓いた点

Segment TreeではなくUnion-Findで解こうとしてWA

3/11: 日立製作所社会システム事業部プログラミングコンテスト2020 C - ThREE

供養

問題

Difficulty: 2012 (記事作成時点)

解法

$n \% 3 = m$ であるような集合を $N_{m}$ とする
$(i, j)$ が距離3の $p_{i}, p_{j}$ において、 $p_{i}, p_{j} \in N_{1}$ もしくは $p_{i}, p_{j} \in N_{2}$ にならないように割り当てる必要がある
木を2部グラフ $(V, W, E)$ として見たときに、距離3の点は自分が属していない方の点集合に属する
の大きさで場合分けして割り当て方を変える
- $|V| \le \lfloor \frac{N}{3} \rfloor$ のとき、 $v \in V$ である $p_{v}$ に $n \in N_{0}$ を割り当て、残りを $W$ に割り当てる
- $|W| \le \lfloor \frac{N}{3} \rfloor$ のとき、 $w \in W$ である $p_{w}$ に $n \in N_{0}$ を割り当て、残りを $V$ に割り当てる
- それ以外のとき、 $n \in N_{1}$ を $v \in V$ である $p_{v}$ に、 $n \in N_{2}$ を $w \in W$ である $p_{w}$ に割り当て、不足分を $n \in N_{0}$ で割り当てる
割り当ては必ずできる

実装は

適当な点 $r$ から探索して、 $1 \le i \le N$ について $r$ との距離 $d_{i}$ を求める
$V = | \lbrace v \mid d_{v} \% 2 = 0 \rbrace|, W = | \lbrace w \mid d_{w} \% 2 = 1 \rbrace |$ とする
$k_{1} = 0, k_{2} = 0, k_{3} = 0$ とする
配列 $A$ を用意する
について、記載順の優先順位で割り当てていく
- のとき
  - $V \le \lfloor \frac{N}{3} \rfloor$ ならば $A_{i} = 3 \times k_{3} + 3$ とし、 $k_{3}$ をインクリメントする
  - $W \le \lfloor \frac{N}{3} \rfloor \land 3 \times k_{1} + 1 \le N$ ならば $A_{i} = 3 \times k_{1} + 1$ とし、 $k_{1}$ をインクリメントする
  - $3 \times k_{2} + 2 \le N$ ならば $A_{i} = 3 \times k_{2} + 2$ とし、 $k_{2}$ をインクリメントする
  - $A_{i} = 3 \times k_{3} + 3$ とし、 $k_{3}$ をインクリメントする
- のとき
  - $W \le \lfloor \frac{N}{3} \rfloor$ ならば $A_{i} = 3 \times k_{3} + 3$ とし、 $k_{3}$ をインクリメントする
  - $3 \times k_{1} + 1 \le N$ ならば $A_{i} = 3 \times k_{1} + 1$ とし、 $k_{1}$ をインクリメントする
  - $V \le \lfloor \frac{N}{3} \rfloor \land 3 \times k_{2} + 2 \le N$ ならば $A_{i} = 3 \times k_{2} + 2$ とし、 $k_{2}$ をインクリメントする
  - $A_{i} = 3 \times k_{3} + 3$ とし、 $k_{3}$ をインクリメントする
$A$ を出力する

計算量は $O(N)$

公式解説

躓いた点

場合分けの条件に気付くのが遅れて時間切れ

3/12: CADDi 2018 E - Negative Doubling

供養

問題

Difficulty: 2372 (記事作成時点)

解法

$A_{i}$ を-2倍する操作を $n$ 回、4倍する操作を $m$ 回とすると、全操作回数は $n + 2m$ 回である
-2倍の操作は $i \le n$ であるような $A_{i}$ に1回ずつ行えばよいので、以降、4倍の操作について考える
操作後の数が正の区間と負の区間で独立して考えることができる
をを回4倍したときにで条件を満たすために必要な4倍操作の回数とする
- $1 \le i \lt N$ について、 $4^{k} \le \frac{A_{i}}{A_{i + 1}} \lt 4^{k + 1}$ であるとき $\mathit{DP}_{i, j} = \mathit{DP}_{i + 1, \mathrm{max}(j + k, 0)} + j$ である
- ここで、 $10^{9} \lt 4^{15}$ より、 $j \gt 15$ 回以上の操作は $\mathit{DP}_{i, j \gt 15} = \mathit{DP}_{i, 15} + (N + 1 - i) \times (j - 15)$ であることが言える
- よって、DP表のサイズは $N \times 15$ で抑えられる
負区間の計算はとの比較の代わりにとの比較をすることで同様に求められる
- $\mathit{DP2}_{i, j}$ とする
について、を-2倍操作を回したときの操作回数とすると、となるので、これらの最小値が答えとなる
- $\mathit{DP}_{N + 1, 0} = 0, \mathit{DP2}_{0, 0} = 0$ とする

実装は

二次元配列 $\mathit{DP}, \mathit{DP2}$ を用意する
$1 \le i \le N, 0 \le j \le 15$ について、 $\mathit{DP}_{i, j} = i, \mathit{DP2}_{i, j} = j$ とする
について、以下のようにを更新する
- であるようなを求める
  - $\mathrm{log}_{4}\frac{A{i}}{A_{i + 1}}$ を求めて少数切り捨てや、 $k = 0$ から $A_{i} \le A_{i + 1} \times 4^{k}$ となるまで $k$ をインクリメントし、 $4^{k} \times A_{i} \le A_{i + 1}$ である間 $k$ をデクリメントし続けて求めてもよい
- $0 \le j \le 15$ について、 $\mathit{DP}_{i, j} = j + \mathit{DP}_{i + 1, \mathrm{min}(\mathrm{max}(j + k, 0), 15)} + (N - i) \times \mathrm{max}(j + k - 15, 0)$ とする
について、以下のようにを更新する
- $4^{k} \le \frac{A_{i}}{A_{i - 1}} \lt 4^{k + 1}$ であるような $k$ を求める
- $0 \le j \le 15$ について、 $\mathit{DP2}_{i, j} = j + \mathit{DP2}_{i - 1, \mathrm{min}(\mathrm{max}(j + k, 0), 15)} + (i - 1) \times \mathrm{max}(j + k - 15, 0)$ とする
配列 $C$ を用意する
$0 \le i \le N$ について、 $C_{i} = i + 2 \times (\mathit{DP}_{i + 1, 0} + \mathit{DP2}_{i, 0})$ とする
$C$ の最小値を出力する

計算量は $O(N)$

公式解説

躓いた点

$10^{9} \lt 4^{15}$ に思い至らず、DP以外の方法を探していた

3/13: AtCoder Beginner Contest 138 F - Coincidence

供養

問題

Difficulty: 2376 (記事作成時点)

解法

任意の $L \le x \le y \le R$ において、 $y$ のMSBが(0-originで) $n$ bit目であるとしたとき、 $x$ の $n$ bit目が 0 とすると $y \% x \lt 2^{n} \le y \oplus x$ となるため、 $x$ のMSBも $n$ bit目である
$x \gt \frac{y}{2}$ より $y \% x = y - x = y \oplus x$ である
$x, y$ の $i$ bit目をそれぞれ $x_{i}, y_{i}$ としたとき、 $y - x = y \oplus x$ より任意の $i$ において $x_{i} \le y_{i}$ である(i.e. 桁下がりが発生しない)
上記の条件を満たすようなbit列をDPで求める
$M_{i, x, y, b}$ を、 $i + 1$ bit目以降が決まった状態で、 $L \lt x, y lt R$ がそれぞれ確定しているか、確定したbitの中にMSBがあるか、を表す $60 \times 2 \times 2 \times 2$ の配列とする
$i = -1$ のとき、すべてのbitが決まった状態なので、これを満たすパターンは1つだけである
既に $M_{i, x, y, b}$ を求めているとき、その結果を再利用できる
が確定しているか、もしくはであるときはとしてもよい
- $R_{i} = 1$ のとき、 $y \lt R$ を確定させることができる
- $M_{i - 1, x, y;\mathrm{OR}\;R_{i}, b}$ を $M_{i, x, y, b}$ に加算する
が確定しているか、もしくはであるときはとしてもよい
- $L_{i} = 0$ のとき、 $L \lt x$ を確定させることができる
- $i$ bit目以降にMSBがあることを確定させることができる
- $M_{i - 1, x;\mathrm{OR}\;\bar{L_{i}} , y, 1}$ を $M_{i, x, y, b}$ に加算する
「が確定しているか、もしくはである」かつ「が確定しているか、もしくはである」かつ確定したbitにMSBがある場合、としてもよい
- $M_{i - 1, x, y, b(=1)}$ を $M_{i, x, y, b}$ に加算する

実装は

$L, R$ を2進表記し、(0-originで) $i$ bit目をそれぞれ $L_{i}, R_{i}$ とする
$60 \times 2 \times 2 \times 2$ の配列 $M$ を用意する
DPのための関数を以下のように作る
- $i \lt 0$ ならば1を返す
- $M_{i, x, y, b}$ が既に求められているならばその値を返す
- $m = 0$ とする
- $x\;\mathrm{OR}\;(1 - L_{i}) = 1$ ならば $F(i - 1, x, y\;\mathrm{OR}\;R_{i}, b)$ を $m$ に加算する
- $y\;\mathrm{OR}\;R_{i} = 1$ ならば $F(i - 1, x\;\mathrm{OR}\;(1 -L_{i}), y, 1)$ を $m$ に加算する
- $(x\;\mathrm{OR}\;(1 - L_{i}) = 1) \land (y\;\mathrm{OR}\;R_{i} = 1) \land (b = 1)$ ならば $F(i - 1, x, y, b)$ を $m$ に加算する
- $M_{i, x, y, b} = m$ とする
- $m$ を返す
$F(59, 0, 0, 0)$ の計算結果を出力する

計算量は $O(\mathrm{log}R)$

公式解説

躓いた点

条件を満たす計算方法が思い浮かばなかった

3/14: AtCoder Grand Contest 004 D - Teleporter

供養

問題

Difficulty: 2379 (記事作成時点)

解法

どの点からも $v \to a_{v}$ を0回以上繰り返すことで $1$ に到達できるので、 $v = 2, \dots, N$ について $a_{v} \to v$ に有向辺を張ると $1$ を根とする木となる
向きを変えた後は $a_{1} = 1$ である必要がある
$\because$ $a_{1} \ne 1$ とすると、点 $v$ がちょうど $K$ 回の移動で $1$ に到達するとき、 $v$ の親 $u$ は $K - 1$ 回の移動で $1$ に到達しており、次の移動後に $a_{1} \ne 1$ にいるため条件に反する
いくつかの点 $v$ に対して、 $v$ に伸びる辺 $u \to v$ を $1 \to v$ に変えることで高さ $K$ 以下の木にする

実装は

から各点を幅優先探索して発見順にとし、と点の距離をとする
- $v_{1} = 1$ である
$C = 0$ とし、 $a_{1} \ne 1$ ならば $C = 1$ とする
配列 $V$ を用意する
について、以下のように更新する
- $d_{v_{i}} \le K$ ならば更新終了
- $V_{v_{i}} \gt 0$ ならば何もしない
- $v_{i}$ の $K - 1$ つ上の先祖を求め $u_{i}$ とする
- $u_{i}$ 自身と全ての子孫について $V_{j} = 1$ とする
- $C$ を1加算する
$C$ を出力する

計算量は $O(N)$

公式解説

躓いた点

葉からではなく根からDPで解こうとして失敗

そのうち誰かの役に立つ

もしくは誰の役にも立たない

AtCoderチャレンジ供養会場(2020/03/08-2020/03/14)

3/8: diverta 2019 Programming Contest E - XOR Partitioning

問題

解法

躓いた点

3/9: AtCoder Beginner Contest 158 E - Divisible Substring

問題

解法

躓いた点

3/10: AtCoder Beginner Contest 158 F - Removing Robots

問題

解法

躓いた点

3/11: 日立製作所社会システム事業部プログラミングコンテスト2020 C - ThREE

問題

解法

躓いた点

3/12: CADDi 2018 E - Negative Doubling

問題

解法

躓いた点

3/13: AtCoder Beginner Contest 138 F - Coincidence

問題

解法

躓いた点

3/14: AtCoder Grand Contest 004 D - Teleporter

問題

解法

躓いた点

3/8: diverta 2019 Programming Contest E - XOR Partitioning

問題

解法

躓いた点

3/9: AtCoder Beginner Contest 158 E - Divisible Substring

問題

解法

躓いた点

3/10: AtCoder Beginner Contest 158 F - Removing Robots

問題

解法

躓いた点

3/11: 日立製作所 社会システム事業部 プログラミングコンテスト2020 C - ThREE

問題

解法

躓いた点

3/12: CADDi 2018 E - Negative Doubling

問題

解法

躓いた点

3/13: AtCoder Beginner Contest 138 F - Coincidence

問題

解法

躓いた点

3/14: AtCoder Grand Contest 004 D - Teleporter

問題

解法

躓いた点

3/11: 日立製作所社会システム事業部プログラミングコンテスト2020 C - ThREE