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

5/8: Donutsプロコンチャレンジ2015 D - ドーナツの箱詰め

供養

問題

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

解法

箱について、であるおよび、であるを使用可能な箱から選ぶ
- 直感的にはソートした状態での両隣
- 存在しなければ $-1$ とする
箱が箱に入っているときとする
- 箱 $i$ の外側もしくは内側に箱がないとき、それぞれを $O_{i} = -1, I_{i} = -1$ で表す
- このとき、緩衝材の量の和は $\sum_{i | O_{i} \ne -1}(C_{O_{i}} - C_{i})$ である
選択できるについて、全体が個かつその時選んだものの和が最小になるよう選んでいく
- 全ての箱を使えるときは、 $C_{i}$ を昇順にソートし、 $C_{i + 1} - C_{i}$ を小さい順に $N - K$ 個選んでいく
- 箱を潰したとき、とを管理から外し、を管理対象に加える
  - どこで管理するかは $D_{i}$ の内側および外側で入れ子になっている箱があるかで判断する
選択していないものを管理する Priority Queueと、選択したものを管理するPriority Queueを使い、何を選択するか/選択から外すかを管理する
- Popしたときに現状に即していない場合は捨てる形式で管理する

実装は

$N \times 2$ の配列 $B$ を用意し、 $B_{i} = (C_{i}, i)$ とする
$B_{i}$ を $C_{i}$ について昇順でソートする
長さ $N$ の配列 $M$ を用意し、 $M_{B_{j, 1}} = j$ とする
長さ $N - 1$ の配列 $X$ を用意し、 $X_{i} = (B_{i + 1, 0} - B_{i, 0}, i, i + 1)$ とする
Priority Queue を用意する
- $P$ は各アイテムの最初の要素で比較して最小値のアイテムをPopし、 $Q$ は各アイテムの最初の要素で比較して最大値のアイテムをPopする
長さ $N$ の配列 $L, R$ を用意し、 $L_{i} = i - 1, R_{i} = i + 1$ とする
$X$ を $X_{i, 0}$ について昇順にソートする
長さ $N$ の配列 $O, I$ を用意する、 $0 \le i \lt N - K$ について、 $O_{X_{i, 1}} = X_{i, 1} + 1, I_{X_{i, 1} + 1} = X_{i, 1}$ とする
$S = 0$ とする
について、以下の操作を実施する
- $X_{i}$ を $Q$ にPushする
- $O_{X_{i, 1}} = X_{i, 2}, I_{X_{i, 2}} = X_{i, 1}$ とする
- $X_{i, 0}$ を $S$ に加算する
$N - K \le i \lt N$ について、 $X_{i}$ を $P$ に追加する
$S$ を出力する
について以下の操作を繰り返す
- $m = M_{D_{i} - 1}$ とする
- $L_{m} \ge 0$ ならば $R_{L_{m}} = R_{m}$ とする
- $R_{m} \lt N$ ならば $L_{R_{m}} = L_{m}$ とする
- $L_{m} \ge 0 \land R_{m} \lt N$ ならば $(B_{R_{m}, 0} - B_{L_{m}, 0}, L_{m}, R_{m})$ を $P$ にPushする
- のとき、以下の操作を実施する
  - $I_{y} = x$ であるような $(s, x, y)$ が出るまで $Q$ からPopする
  - $(s, x, y)$ を $P$ にPushする
  - $O_{x} = -1, I_{y} = -1$ とする
  - $s$ を $S$ から減算する
- のとき、以下の操作を実施する
  - $B_{O_{m}, 0} - B_{m, 0}$ を $S$ から減算する
  - $I_{O_{m}} = -1$ とする
- のとき、以下の操作を実施する
  - $B_{m, 0} - B_{I_{m}, 0}$ を $S$ から減算する
  - $O_{I_{m}} = -1$ とする
- のとき、以下の操作を実施する
  - $B_{O_{m}} - B_{I_{m}}$ を $S$ から減算する
  - $O_{I_{m}} = -1, I_{O_{m}} = -1$ とする
  - $R_{x} = y \land L_{y} = x$ であるような $(s, x, y)$ が出るまで $P$ からPopする
  - $(s, x, y)$ を $Q$ にPushする
  - $O_{x} = y, I_{y} = x$ とする
  - $s$ を $S$ に加算する
- $O_{m} = -1, I_{m} = -1$ とする
- $S$ を出力する

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

~~公式解説~~

躓いた点

管理にSegment Treeを使ってTLE
Priority QueueにPushするタイミングを間違えてWA

5/9: AtCoder Regular Contest 048 C - 足の多い高橋君

供養

問題

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

解法

どの足のパターンについても、先端から文字は同じパターンとなる
- この部分にそれ以外の制約はない
の文字目以降について、以下が成立する
- 任意のについてとを繋げたものは回文になる
  - ここで $p_{j}^{-1}$ は $p_{j}$ を逆から見たものである
$\mathrm{min}(L_{i} - D) = 0$ より、 $p_{i}$ もそれだけで回文である
長さ0でないのうち最短のものをとするとであるについて以下が成り立つ
- $p^{'}$ と $p_{i}^{-1}$ の結合を考えることで $p_{i}$ の先頭 $|p^{'}|$ 文字は $p^{'}$ と一致する
- $p_{i}$ 自身が回文なので、 $p_{i}$ の先頭 $|p^{'}|$ 文字と末尾から $|p^{'}|$ 文字は一致する
- また $p^{'}$ と $p_{i}^{-1}$ の結合を考えることで $p_{i}$ の先頭 $|p^{'}| + 1$ から $2|p^{'}|$ 文字は $p_{i}$ の末尾 $|p^{'}|$ 文字 i.e. $p^{'}$ と一致する
- 上記を繰り返すと $p^{'}$ の先頭と末尾それぞれ $|p^{''}| = |p_{i}| \% |p^{'}|$ 文字が重なる
- $p^{'}$ と $p^{''}$ について、上記と同様の関係が成り立つ
- よって $p_{i}$ は長さ $\mathit{GCD}(p_{i}, p^{'})$ の回文の繰り返しであることが分かる
上記より、任意の長さ0でない $p_{i}$ は長さ $\mathit{GCD}(L)$ の回文 $p^{*}$ の繰り返しである
以上から、制約を満たすパターンは $2^{D + \lfloor \frac{|p^{*}|}{2} \rfloor}$ 通り

実装は

$m = \mathrm{min}(L_{i})$ とする
$g = 0$ とし、 $0 \le i \lt N$ について $g = \mathit{GCD}(L_{i} - m, g)$ とする
$2^{m + \lfloor \frac{g}{2} \rfloor}$ を出力する

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

公式解説

躓いた点

$2^{m + \lfloor \frac{g}{2} \rfloor}$ の実装を間違えていた

5/10: AtCoder Regular Contest 003 D - シャッフル席替え

供養

問題

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

解法

制限時間が長く、許容誤差も大きいのでシミュレーションして成功率を出す
- 確率的には $10^{6}$ 回程度試行すればおおむね通る

実装は

$N \times N$ の配列 $E$ を用意し、各要素を $\mathit{false}$ で初期化する
$0 \le i \lt N$ について、 $E_{a_{i}, b_{i}} = \mathit{true}, E_{b_{i}, a_{i}} = \mathit{true}$ とする
$S = 0, T = 1000000$ とする
以下の試行を回実行する
- 長さ $N$ の配列 $A$ を用意し、 $A_{i} = i$ とする
- $0 \le a \lt b \lt N$ である $a, b$ をランダムに選び、 $A_{a}$ と $A_{b}$ を交換する操作を $K$ 回実行する
- $0 \le i \lt N$ について、 $E_{A_{i}, A_{(i + 1) \% N}} = \mathit{true}$ ならば次の試行に行く
- $S$ をインクリメントする
$\frac{S}{T}$ を出力する

計算量は $O(T(N + K))$

~~公式解説~~

躓いた点

シミュレーションの発想はなかった
~~正直今のコンテスト規模ではできないと思う~~

5/11: AtCoder Beginner Contest 167 F - Bracket Sequencing

供養

問題

Difficulty: 1895 (記事作成時点)

解法

括弧列を先頭から見たとき、常に (それまでに登場した ( の数) $\ge$ (それまでに登場した ) の数) となる
について、の先頭から文字目までの ( の数と ) の数の差をとしたとき、とする
- $\sum c_{i} \ne 0$ ならば括弧の数が合っていないので自明に括弧列は作れない
以下の順番でを並べていき、どの時点においてもそれまでに登場した ( の数が ) の数を下回らないかをチェックする
- $m_{i} \ge 0$ である $S_{i}$
- 上記以外で $c_{i} \gt 0$ である $S_{i}$ を $m_{i}$ の降順に
- 上記以外で $c_{i} \gt m_{i}$ である $S_{i}$ を $m_{i}$ の昇順に
- 上記以外

実装は

空の配列 $P_{0}$ から $P_{3}$ を用意する
とし、各について以下の操作を実施する
- $c = 0, m = 0$ とする
- $S_{i}$ を先頭から見ていき、( ならば $c = c + 1$ とし、) ならば $c = c - 1, m = \mathrm{min}(c, m)$ とする
- $c$ を $s$ に追加する
- $m \ge 0$ ならば $(c, m)$ を $P_{0}$ に追加して次に行く
- $c \gt 0$ ならば $(c, m)$ を $P_{1}$ に追加して次に行く
- $c \gt m$ ならば $(c, m)$ を $P_{2}$ に追加して次に行く
- $(c, m)$ を $P_{3}$ に追加する
$s \ne 0$ ならば No を出力して終了
$P_{1}$ を $m$ について降順にソートする
$P_{2}$ を $m$ について昇順にソートする
$C = 0$ とする
についてを先頭から見ていき、以下の処理を実施する
- $C + m \lt 0$ ならば No を出力して終了
- $c$ を $C$ に加算する
Yes を出力する

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

公式解説

躓いた点

解けはしたがコンテストなら時間切れ

5/12: AtCoder Regular Contest 050 C - LCM 111

供養

問題

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

解法

1を $k$ 個並べた数を $O_{k}$ としたとき、 $\mathit{GCD}(O_{A}, O_{B}) = O_{\mathit{GCD}(A, B)}$ である
$\mathit{LCM}(O_{A}, O_{B}) = \frac{O_{A} \times O_{B}}{\mathit{GCD}(O_{A}, O_{B})} = O_{A} \times \frac{O_{B}}{O_{\mathit{GCD}(A, B)}}$ である
$O_{A}$ は $X_{1} = 1, X_{k} = 10 \times X_{k - 1} + 1$ で定義される数列の第 $A$ 項であるので、以下の行列式から求めることができる

$G = \mathit{GCD}(A, B)$ としたとき、 $\frac{O_{B}}{O_{\mathit{GCD}(A, B)}} = \frac{O_{B}}{O_{G}}$ は $Y_{1} = 1, Y_{k} = 10^{G} \times Y_{k} + 1$ で定義される数列の第 $\frac{B}{G}$ 項であるので、以下の行列式から求めることができる

行列の累乗を作るときに各要素を $\mathrm{mod}\; M$ にすることで $O_{A} \% M$ や $\frac{O_{B}}{O_{G}} \% M$ を求めることができる

実装は

以下の関数を実装する
- $m = 1$ とし、 $2^{m} \gt k$ となるまで $m$ をインクリメントする
- 長さ $m \times 2 \times 2$ の配列を用意し、 $X_{0} = \lbrack \lbrack 1, 0 \rbrack, \lbrack 1, n \rbrack \rbrack$ とする
- について、とする
  - $\mathit{MM}(X, Y, p)$ は行列 $X, Y$ の乗算をし、各要素を $\mathrm{mod}\; p$ したものを返す関数
- とし、について以下の操作を実施する
  - $k \% 2 = 1$ ならば $A = \mathit{MM}(X_{i}, A, p)$ とする
  - $k = \lfloor \frac{k}{2} \rfloor$ とする
- $A_{1, 0}$ を返す
$G = \mathit{GCD}(A, B)$ とする
$F(10, A - 1, M) \times F(\mathit{Pow}(10, G, M), \frac{B}{G} - 1, M) \% M$ を出力する

計算量は $O(\mathrm{log}A + \mathrm{log}B)$

公式解説

躓いた点

行列式で表現する発想が出なかった

5/13: 天下一プログラマーコンテスト2015予選A B - stepモード

供養

問題

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

解法

$S_{i}$ が $E{i}$ 以後になっているとき、巻き戻りが $(S_{i}, E_{i} + 1000)$ の間のどこかで発生したことが分かる
したがって、巻き戻りの発生地点候補は $S_{i} \ge E_{i}$ なる $i$ について $(\mathrm{max}(S_{i}), \mathrm{min}(E_{i}) + 1000)$ となる
よって時間が二重に記録される可能性がある区間 $(L, R)$ は $(L, R) = (\mathrm{max}(S_{i}) - 1000, \mathrm{min}(E_{i}) + 1000)$
$E_{i} \le L \lor R \le S_{i}$ であるようなスクリプトの実行時間は $E_{i} - S_{i}$
$S_{i} \le L \land R \le E_{i}$ もしくは $S_{i} \ge E_{i}$ であるようなスクリプトの実行時間は $E_{i} - S_{i} + 1000$
$(L, R)$ が不定だったり、上記の条件に該当しない場合は実行時間は一意に定めることはできない

実装は

$S_{i}, E_{i}$ をミリ秒で保持する
$L = -1001, R = 10^{9}$ とする
$0 \le i \lt N$ について、 $S_{i} \ge E_{i}$ ならば $L = \mathrm{max}(S_{i} - 1000, L), R = \mathrm{min}(E_{i} + 1000, R)$ とする
について、以下の操作を実行する
- $L \lt 1000$ ならば $-1$ を出力
- 上記以外で $E_{i} \le L \lor R \le S_{i}$ ならば $E_{i} - S_{i}$ を出力
- 上記以外で $(S_{i} \le L \land R \le E_{i}) \lor S_{i} \ge E_{i}$ ならば $E_{i} - S_{i} + 1000$ を出力
- 上記以外ならば $-1$ を出力

計算量は $O(N)$

~~公式解説~~

躓いた点

$(L, R) = (\mathrm{min}(E_{i}), \mathrm{min}(E_{i}) + 1000)$ で考えていてWA

5/14: 第2回ドワンゴからの挑戦状予選 C - メンテナンス明け

供養

問題

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

解法

路線を方向に移動中に寝過ごしたとき、それ以降のコストは方向の終点までのコストとからまでのコストの和
- $u = s_{m, i}, v = s_{m, i + 1}$ ならば $c_{u, x} = \sum_{j} w_{m, j} - \sum_{k = 0}^{i - 1} w_{m, k}$
- $u = s_{m, i + 1}, v = s_{m, i}$ ならば $c_{u, x} = \sum_{k = 0}^{i} w_{m, k}$
- $x$ から $\mathit{dst}$ までのコストは $\mathit{dst}$ からの最短路探索で求められる
寝過ごしを加味した上での最短コストをとしたとき、以下のようにを求められる
- $D_{\mathit{dst}} = 0, D_{u \ne \mathit{dst}} = \mathit{Inf}$ とする
- 未決定の $D_{u}$ のうち最小のものを選び $D_{u^{'}}$ とし、 $D_{u^{'}}$ の値をそれで決定する
- 路線 $m$ で $v \to u^{'}$ である $v$ について、 $v \to u^{'}$ のコストを $w$ としたとき、 $\mathrm{min}(\mathrm{max}(C_{m, v, u^{'}}, w + D_{u^{'}}), D_{v})$ で $D_{v}$ を更新する

実装は

長さ $N$ の配列 $G$ を用意する
について、以下の操作を実施する
- $x = 0, X = \sum_{j} w_{m, j}$ とする
- について、以下の操作を実施する
  - $(s_{m, i}, w_{m, i}, s_{m, L_{m} - 1}, X - x)$ を $G_{s_{i + 1}}$ に追加する
  - $w_{m, i}$ を $x$ に加算する
  - $(s_{m, i + 1}, w_{m, i}, s_{0}, x)$ を $G_{s_{i}}$ に追加する
Priority Queue を用意する
- 各エントリの最初の要素で比較して最小のものをPopする
$G$ における $\mathit{dst}$ から各点への最小コストの配列を $C$ とする
長さの配列を用意し、とする
- $\mathit{Inf}$ は $10^{9}$ 程度あれば十分
$(0, \mathit{dst})$ を $\mathit{PQ}$ にPushする
が空になるまで以下の操作を繰り返す
- $\mathit{PQ}$ からPopし $(d, u)$ とする
- $D_{u} \le d$ ならば何もせず次へ行く
- $D_{u} = d$ とする
- $G_{u}$ の各要素 $(v, w, x, y)$ について、 $(\mathrm{max}(y + C_{x}, w + D_{u}), v)$ を $\mathit{PQ}$ にPushする
$D_{\mathit{src}}$ を出力する