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

4/1: CODE FESTIVAL 2014 決勝 F - 誤情報

供養

問題

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

解法

矛盾がない状態のとき、任意のはで割り切ることができる
- $\mathrm{GCD}(B_{i - 1}, B_{i + 1})$ は $A_{i - 1}, A_{i}, A_{i + 1}, A_{i + 2}$ の最大公約数であるため
をについて昇順に見ていくとき、がで割り切れなかったときはに変更するとその後の変更を最小化できる
- ただし、最初に $B_{1}$ が $\mathrm{GCD}(B_{N}, B_{2})$ で割り切れなかったときは $B_{N}$ や $B_{1}$ を誤情報としたほうが総数が少なくなる場合があるので3パターン試す

実装は

$s = 0, \dots, N - 1$ について、最初に $B_{s} \% \mathrm{GCD}(B_{(s - 1) \% N}, B_{(s + 1) \% N}) \ne 0$ となる $s$ を求め、それがなければ 0 を出力して終了
の配列を用意し、を1に、それ以外を0に初期化する
- $C_{i, j} = 1$ のとき、 $B_{j}$ を誤情報とすることを意味する
各について下記操作を実施する
- から、となるまで下記操作を実施する
  - $B_{j} \% \mathrm{GCD}(B_{(j - 1) \% N}, B_{(j + 1) \% N}) = 0$ ならば $j$ を1つインクリメントする
  - $B_{j} \% \mathrm{GCD}(B_{(j - 1) \% N}, B_{(j + 1) \% N}) \ne 0$ ならば $C_{i, (j + 1) \% N} = 1$ とし、 $j$ を3つインクリメントする
$\mathrm{min}(\mathrm{sum}(C_{i}))$ を出力する

計算量は $O(N)$

~~公式解説~~

躓いた点

$B_{N}$ と $B_{1}$ をまたぐあたりの処理でミスしてWA大量生成

4/2: AtCoder Regular Contest 018 C - 席替え

供養

問題

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

解法

を昇順に安定ソートしたときの位置をとすると、は行目に移動することになる
- であるような組があるかもしれないが、元の位置が前にあるものをそのまま前に置き続けても総移動距離は減りこそすれ増えることはない
  - 実際はそのような状況は $a \% p = 0$ のときしか起こらない
- $\sum_{i = 0}^{NM - 1}|\lfloor \frac{j}{M} \rfloor - i|$ で縦方向の総移動距離を求めることができる
移動後に行目に移るものをとしたとき、の元の大小関係を保存したまま並び替えることは総移動距離を減らすことはあっても増やすことはない
- $x_{j}$ を $M$ 個ずつ $i \% M$ について昇順にソートしたものを $x_{k}$ としたとき、 $\sum_{n}\sum|(k - i) \% M|$ で横方向の移動距離を求めることができる

実装は

$x = x_{0}, a = a \% p$ とする
$NM \times 2$ の配列 $D$ を用意し、 $D_{0} = \lbrack x, 0 \rbrack$ とする
$i = 1 \dots NM - 1$ について、 $x = (x + a) \% p, D_{i} = \lbrack x, i \rbrack$ と更新していく
$D$ を昇順に安定ソートする
とし、について下記操作を実施する
- 長さ $M$ の配列 $S$ を用意する
- $0 \le m \lt M$ について、 $C = C + \lfloor |\frac{D_{n \times M + m, 1}}{M} \rfloor - n|, S_{m} = D_{n \times M + m, 1} \% M$ とする
- $S$ を昇順にソートする
- $0 \le m \lt M$ について、 $C = C + |S_{m} - m|$ とする
$C$ を出力する

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

公式解説

躓いた点

$(0, 0)$ に $x_{0} \% p$ を置いていたためWA

4/3: 天下一プログラマーコンテスト2015予選A C - 天下一美術館

供養

問題

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

解法

白→黒、黒→白であるような隣接しあったマスを極力スワップで処理する
- $i + j$ が偶数のマスと奇数のマスでの最大マッチングとなる

実装は

$M \times N$ の配列 $C$ を用意し、 $C_{i, j} = B_{i, j} - A_{i, j}$ とする
$M \times N + 2$ 点のグラフ $G = (V, E)$ を用意する
$S = 0$ とする
について、下記操作を実施する
- $x = i \times N + j + 1$ とする
- $(i + j) \% 2 = 0$ (i.e. $i + j$ が偶数) ならば $v_{0} \to v_{x}$ に容量1の辺を張る
- $(i + j) \% 2 = 1$ (i.e. $i + j$ が奇数) ならば $v_{x} \to v_{M \times N + 1}$ に容量1の辺を張る
- $|C_{i, j}|$ を $S$ に加算する
- $C_{i, j} = 0$ ならば次に行く
- のとき、
  - $(i + j) \% 2 = 0$ (i.e. $i + j$ が偶数) ならば $v_{x} \to v_{x + 1}$ に容量1の辺を張る
  - $(i + j) \% 2 = 1$ (i.e. $i + j$ が奇数) ならば $v_{x + 1} \to v_{x}$ に容量1の辺を張る
- のとき、
  - $(i + j) \% 2 = 0$ (i.e. $i + j$ が偶数) ならば $v_{x} \to v_{x + N}$ に容量1の辺を張る
  - $(i + j) \% 2 = 1$ (i.e. $i + j$ が奇数) ならば $v_{x + N} \to v_{x}$ に容量1の辺を張る
$G$ の最大フロー $f$ をFord-FulkersonやDinicで求める
$S - f$ を出力する

計算量はグラフの点数、変数ともに $O(MN)$ であることから $O(M^{3}N^{3})$

~~公式解説~~

躓いた点

マッチング問題に落とし込まずに解こうとしていた
実装したDinicが遅くTLE

4/4: AtCoder Beginner Contest 161 F - Division or Substraction

供養

問題

Difficulty: 1503 (記事作成時点)

解法

割り切れる限り $N = \frac{N}{k}$ としていった後に $N \% k = 1$ となるような $k$ が $N$ を1にすることができる $k$
のときはで割り切れることはない
- $nk + 1 = N$ より、 $N - 1$ をちょうど割り切る $n$ について、 $k = \frac{N - 1}{n} \gt \sqrt{N}$ であるようなものを数えればいい
- そのようなものは最大で $\sqrt{N}$ 個
$k \le \sqrt{N}$ のときは割り切れる限り $N = \frac{N}{k}$ としていった後に $N \% k = 1$ となるかで判定できる

実装は

$K = \lfloor \sqrt{N} \rfloor, C = 0$ とする
$1 \le n \le K$ について、 $(N - 1) \% n = 0 \land \frac{N - 1}{n} \gt K$ ならば $C$ をインクリメントする
について、以下の操作を実施する
- $N \% k = 0$ である限り $N = \frac{N}{k}$ とする
- $N \% k = 1$ ならば $C$ をインクリメントする
$C$ を出力する

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

公式解説

躓いた点

時間切れ

4/5: AtCoder Regular Contest 035 D - 高橋くんとマラソンコース

供養

問題

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

解法

チェックポイント $i$ と $i + 1$ を移動する経路数は $\frac{(p_{i + 1} - p_{i} + q_{i + 1} - q_{i})!}{(p_{i + 1} - p_{i})!(q_{i + 1} - q_{i})!}$
該当区間の経路の積を持つようなSegment Treeで更新・比較を高速にできる
ただし、経路数をそのまま持つと莫大な数になりオーバーフローする
- 経路数をlogで持つ
- $\mathrm{log}(a \times b) = \mathrm{log}a + \mathrm{log}b, \mathrm{log}(\frac{a}{b}) = \mathrm{log}a - \mathrm{log}b$ を利用して計算する
- Segment Treeは区間和を持てばよい

実装は

長さ $2 \times 10^{6} + 1$ の配列 $F$ を用意し、 $k = 1, \dots, 2 \times 10^{6} + 1$ について $F_{k} = F_{k - 1} + \mathrm{log}k$ とする
要素数のSegment Tree を用意する
- $\lbrack l, r)$ の累積和を返す関数を $\mathit{Query}(l, r)$ とする
$1 \le i \lt N$ について、 $\mathit{ST}_{i}$ を $F_{p_{i} - p_{i - 1} + q_{i} - q_{i - 1}} - F_{p_{i} - p_{i - 1}} - F_{q_{i} - q_{i - 1}}$ に更新する
について、以下の操作を実施する
- のとき
  - $p_{k_{j} - 1}, q_{k_{j} - 1}$ を $a_{j}, b_{j}$ に更新する
  - $1 \lt k_{j}$ ならば $\mathit{ST}_{k_{j}}$ を $F_{p_{k_{j}} - p_{k_{j} - 1} + q_{k_{j}} - q_{k_{j} - 1}} - F_{p_{k_{j}} - p_{k_{j} - 1}} - F_{q_{k_{j}} - q_{k_{j} - 1}}$ に更新する
  - $k_{j} \lt N$ ならば $\mathit{ST}_{k_{j} + 1}$ を $F_{p_{k_{j} + 1} - p_{k_{j}} + q_{k_{j} + 1} - q_{k_{j}}} - F_{p_{k_{j} + 1} - p_{k_{j}}} - F_{q_{k_{j} + 1} - q_{k_{j}}}$ に更新する
- のとき
  - $\mathit{Query}(l_{1j}, r_{1j}) \gt \mathit{Query}(l_{2j}, r_{2j})$ ならば FIRST を出力し、そうでなければ SECOND を出力する

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

公式解説

躓いた点

経路数をlogで圧縮する発想は出なかった
更新時の境界条件を忘れてRE

4/6: AtCoder Regular Contest 003 C - 暗闇帰り道

供養

問題

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

解法1

スタートから各地点までの明るさをDPで求める

実装は

$(N + 2) \times (M + 2)$ の配列 $C$ を用意し、各要素を $-1$ で初期化する
について、[c_{ij}] が s もしくは g ならばとし、に数値が与えられているならをその値にする
- $c_{i, j}$ が # なら何もしない
スタート地点を $(n_{s}, m_{s})$ 、ゴール地点を $(n_{g}, m_{g})$ とする
$(N + 2) \times (M + 2)$ の配列 $B$ を用意し、各要素を $-1$ で初期化する
キュー $Q$ を用意し、 $(10, n_{s}, m_{s}, 1)$ を $Q$ の末尾に挿入する
が空になるまで下記を繰り返す
- $Q$ の先頭の要素を取り出し、 $(b, n, m, t)$ とする
- $t^{'} = t \times 0.99$ とする
- $b^{'} = \mathrm{min}(C_{n - 1, m} * t, b)$ とし、 $C_{n - 1, m} \gt 0 \land B_{n - 1, m} \lt b^{'}$ ならば $B_{n - 1, m} = b^{'}$ とし、 $(b^{'}, n - 1, m, t^{'})$ を $Q$ の末尾に挿入する
- $b^{'} = \mathrm{min}(C_{n + 1, m} * t, b)$ とし、 $C_{n + 1, m} \gt 0 \land B_{n + 1, m} \lt b^{'}$ ならば $B_{n + 1, m} = b^{'}$ とし、 $(b^{'}, n + 1, m, t^{'})$ を $Q$ の末尾に挿入する
- $b^{'} = \mathrm{min}(C_{n, m - 1} * t, b)$ とし、 $C_{n, m - 1} \gt 0 \land B_{n, m - 1} \lt b^{'}$ ならば $B_{n, m - 1} = b^{'}$ とし、 $(b^{'}, n, m - 1, t^{'})$ を $Q$ の末尾に挿入する
- $b^{'} = \mathrm{min}(C_{n, m + 1} * t, b)$ とし、 $C_{n, m + 1} \gt 0 \land B_{n, m + 1} \lt b^{'}$ ならば $B_{n, m + 1} = b^{'}$ とし、 $(b^{'}, n, m + 1, t^{'})$ を $Q$ の末尾に挿入する
$B_{n_{g}, m_{g}}$ を出力する

計算量は $O(NM)$

解法2

ゴールから逆に辿って、自分の一つ手前がスタートのつもりで明るさを計算する
- スタート以外の途中計算結果は必ずしもその場所までの明るさを保証しない

実装は

解法1と同様に $C, (n_{s}, m_{s}), (n_{g}, s_{g}), B$ を用意する
Priority Queue を用意し、をにPushする
- 各エントリの第一要素の大きい順にPopする
が空になるまで下記を繰り返す
- $\mathit{PQ}$ からPopしたものを $(b, n, m)$ とする
- $(n, m) = (n_{s}, m_{s})$ ならばループ終了
- $b \lt B_{n, m}$ ならば何もせず次に行く
- $b^{'} = b \times 0.99$ とする
- $b^{''} = \mathrm{min}(C_{n - 1, m}, b^{'})$ とし、 $C_{n - 1, m} \gt 0 \land B_{n - 1, m} \lt b^{''}$ ならば $B_{n - 1, m} = b^{''}$ とし、 $(b^{''}, n - 1, m)$ を $\mathit{PQ}$ にPushする
- $b^{''} = \mathrm{min}(C_{n + 1, m}, b^{'})$ とし、 $C_{n + 1, m} \gt 0 \land B_{n + 1, m} \lt b^{''}$ ならば $B_{n + 1, m} = b^{''}$ とし、 $(b^{''}, n + 1, m)$ を $\mathit{PQ}$ にPushする
- $b^{''} = \mathrm{min}(C_{n, m - 1}, b^{'})$ とし、 $C_{n, m - 1} \gt 0 \land B_{n, m - 1} \lt b^{''}$ ならば $B_{n, m - 1} = b^{''}$ とし、 $(b^{''}, n, m - 1)$ を $\mathit{PQ}$ にPushする
- $b^{''} = \mathrm{min}(C_{n, m + 1}, b^{'})$ とし、 $C_{n, m + 1} \gt 0 \land B_{n, m + 1} \lt b^{''}$ ならば $B_{n, m + 1} = b^{''}$ とし、 $(b^{''}, n, m + 1)$ を $\mathit{PQ}$ にPushする
$B_{n_{s}, m_{s}}$ を出力する

計算量は解法1と同様に $O(NM)$ だが実測値はかなり早い

~~公式解説~~

躓いた点

解法1でゴール以外の初期値を0にしたら（おそらく）更新が途中で止まってWA

4/7: AtCoder Regular Contest 020 C - A mod B Problem

供養

問題

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

解法

を回繰り返した数をで割った余りをとする
- $a_{i}$ が十進 $k$ 桁の数とすると、 $C_{i, j} = (C_{i, j - 1} \times (10^{2^{j - 1}k} + 1))_{B}$ と表すことができる
- $10^{2^{j - 1}k}$ についても、 $D_{i, 0} = (10^{k})_{B}, D_{i, j} = (D_{i, j - 1}^{2})_{B}$ とすることで、 $j \ge 1$ について $C_{i, j} = (C_{i, j - 1} \times (D_{i, j - 1} + 1))_{B}$ と表すことができる
$L_{i}$ を二進表現したときに下から $j$ bit目(0-origin)が1ならば、それまでの値を $D_{i, j}$ 倍した後に $C_{i, j}$ を足すことで、末尾に $a_{i}$ を $2^{j}$ 回繰り返し追加した数を $B$ で割った余りを求めることができる

実装は

$X = 0$ とする
について下記の操作を実施する
- 配列を用意し、をの末尾に追加する
  - それぞれ末尾の要素を $C_{-1}, D_{-1}$ で表現する
- $R = 1$ とし、 $R \le a_{i}$ である間 $R = 10 \times R$ とする
- $(R)_{B}$ を $D$ の末尾に追加する
- とし、となるまで下記操作を繰り返す
  - $c = C_{-1}, d = D_{-1}$ とする
  - $(c \times (d + 1))_{B}$ を $C$ の末尾に追加する
  - $(d \times d)_{B}$ を $D$ の末尾に追加する
  - $j$ を2倍にする
- 配列 $K$ を用意し、 $K_{j}$ を $L_{i}$ を二進表記したときの下位 $j$ bit目とする
- について下記操作を実施する
  - $K_{j} = 0$ ならば何もしない
  - $K_{j} = 1$ ならば $X = (X \times D_{j} + C_{j})_{B}$ とする
$X$ を出力する