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

6/1: AtCoder Regular Contest 039 D - 旅行会社高橋君

供養

問題

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

解法

グラフを二辺連結成分に分解する
- DFSをしながら各点 $v$ の深さ $D_{v}$ を求めていく
- DFSの探索木に含まれない辺を後退辺とする
  - $uv$ が後退辺のとき、 $|D_{u} - D_{v}| \ge 2$ となる
- 各点から深さを増加させる方向の辺を任意の回数、後退辺を1回以下使用して到達できる最小の深さ(low-link)をとする
  - 自身および自身の親以外の隣接点の深さの最小値を覚えておき、葉から根方向へボトムアップに最小値を更新していけば求めることができる
- DFSの探索木に含まれる辺について、を親としたときにならばは橋(bridge)である
  - bridgeを取り除くとグラフは連結でなくなる
- グラフからbridgeを全て取り除いたときに残ったそれぞれの連結成分は二辺連結成分である
各二辺連結成分の代表点とbridgeからなるグラフを考える
- $G$ の各点 $v$ について、 $v$ が属する二辺連結成分の代表点に対応する $H$ 上の点を $V_{v}$ とする
- bridge $uv$ は $V_{u}$ と $V_{v}$ を結ぶとする
- このとき、 $H$ は木となる
二重連結成分の任意の3点はそれらを含む辺素なサイクルを構成できるので、 $A_{i}, B_{i}, C_{i}$ が同一二辺連結成分に属していれば OK となる
とが同一二辺連結成分に属していれば、からを経由して2点が属する二辺連結成分の出口、[tec: C_{i}] が属する二辺連結成分の入口、と移動していくことができる
- $B_{i}$ と $C_{i}$ が同一二辺連結成分に含まれている場合も同様
とが属する二辺連結成分がそれぞれ異なり、とが属する二辺連結成分がそれぞれ異なるとき、上でからへのパス上にがいるかで判定する
- $V_{A_{i}}, V_{B_{i}}$ 間の距離 $+ V_{B_{i}}, V_{B_{i}}$ 間の距離 $= V_{A_{i}}, V_{C_{i}}$ 間の距離であるかで判定できる
- 2点 $u, v$ 間の距離は $u$ の深さ $+ v$ の深さ $- 2 \times \mathit{LCM}(u, v)$ の深さで計算できる
同一の二辺連結成分に属する場合は上記の距離は0となるので、

実装は

長さ $N$ の配列 $D, L, P$ および配列 $F$ を用意する
グラフを点0からDFSし、点の深さを、から伸びる後退辺の先の深さの最小値を、の親を、発見順をに記録していく
- 後退辺が存在しない点については $L_{v} = D_{v}$ とする
$F$ の逆順に見ていき、現在見ている点 $v$ について $L_{P_{v}} = \mathrm{min}(L_{v}, L_{P_{v}})$ と更新していく
Union-Findのための関数 $\mathit{Unite}(u, v), \mathit{Find}(u)$ を用意する
配列 $B$ を用意する
について、以下の操作を実施する
- $D_{x_{i}} \gt D_{y_{i}}$ ならば $x_{i}$ と $y_{i}$ を入れ換える
- $D_{y_{i}} - D_{x_{i}} \ge 2$ ならば後退辺なので何もせず次へ行く
- $D_{v} \ge L_{y_{i}}$ ならば $\mathit{Unite}(x_{i}, y_{i})$ をする
- $D_{v} \ge L_{y_{i}}$ ならば $i$ を $B$ の末尾に追加する
$N$ 個の独立点からなるグラフ $H$ を用意する
$B$ の各要素 $i$ について、 $H$ 上の点 $\mathit{Find}(x_{i})$ と $\mathit{Find}(y_{i})$ を接続する
$H$ を0から探索し、各点の深さ $D^{'}_{v}$ を求める
$H$ 上の任意の2点 $u, v$ のLCAを求める関数 $\mathit{LCA}(u, v)$ を用意する
上の任意の2点の距離を求める関数を以下のように用意する
- $w = \mathit{LCA}(u, v)$ とし、 $D^{'}_{u} + D^{'}_{v} - 2D^{'}_{w}$ を返す
について以下の操作を実施する
- $a = \mathit{Find}(a_{i}), b = \mathit{Find}(b_{i}), c = \mathit{Find}(c_{i})$ とする
- $\mathit{Dist}(a, b) + \mathit{Dist}(b, c) = \mathit{Dist}(a, c)$ ならば OK を出力し、そうでなければ NG を出力する

計算量は前処理が $O(N + M)$ 、クエリごとに $O(\mathrm{log}N)$ なので全体で $O(N + M + Q\mathrm{log}N)$

公式解説

躓いた点

二辺連結成分分解すればいいという発想が出なかった

6/2: AtCoder Beginner Contest 137 F - Polynomial Construction

供養

問題

Difficulty: 2435 (記事作成時点)

解法

Fermatの小定理より $a \% p \neq 0$ について $a^{p - 1} = 1$ から、 $1 - (x - i)^{p - 1}$ は $x = i$ ならば1、そうでなければ0
上記の式がすべての $A_{i} = 1$ である $i$ のときに成立すればよいので、求める式は $\sum_{i | A_{i} = 1}\bigl(1 - (x - i)^{p - 1}\bigr)$

実装は

長さの配列を用意し、についてとする
- 事前に $0 \le k \lt p$ について $k!, k!^{-1}$ を求めておく
$p \times p$ の配列 $C$ を用意し、 $C_{i, j} = (-i)^{j}$ とする
長さ $p$ の配列 $D$ を用意する
について以下の操作を実施する
- $D_{0}$ に $A_{i}$ を加算する
- $0 \le j \lt p$ について、 $D_{j}$ にから $A_{i} \times B_{j} \times C_{i, p - 1 - j}$ を減算する
$D$ を出力する

計算量は $O(p^{2})$

公式解説

躓いた点

愚直に掃き出し法をやってTLE
式変換が思いつかなかった

6/5: DISCO presents ディスカバリーチャンネルコードコンテスト2020 予選 C - アメージングな文字列は、きみが作る！

供養

問題

Difficulty: 2443 (記事作成時点)

解法

$S$ に a 以外の文字が $K$ 個以下しかないとき、 $|S| - K$ 個の a にするのが辞書順最小
そうでないとき、先頭から連続する a の長さを最大化した上で、残りが辞書順最小になるようにするのが辞書順最小
先頭から見て a でない文字が $K + 1$ 個登場するまでに登場した a の集合を $A$ 、 $A$ で最後に登場した位置を $j$ とする
$i \lt j$ で a でない文字 $s_{i}$ は a に置換することで先頭から連続する a の長さを最大化できる
以降については先頭に a を挿入しても置換しても先頭から連続する a の長さはで変わらないので、後に続く文字列が辞書順最小になるよう置換する文字数を決める
- Suffix Arrayを使えば求められる

実装は

配列 $T$ を用意し、 $a = 0, j = 0$ とする
について、以下の処理を実施する
- $|T| \le K \land s_{i} =$ a のとき、 $a = a + 1, j = i$ とする
- $s_{i} \ne$ a のとき、 $T$ の末尾に $i$ を追加する
$|T| \le K$ のとき、a を $|S| - K$ 文字連続させた文字列 $S^{'}$ を出力して終了
a を $K + a$ 文字連続させた文字列 $S^{'}$ を作る
$S$ の Suffix Array $\mathit{A}$ を作る
について以下の処理を実施する
- ならばを出力して終了
  - $S_{A_{i}\dots}$ は $S$ の(0-indexedで) $A_{i}$ 文字目以降

計算量は $O(|S|)$

公式解説

躓いた点

a の最大化の方法を間違えた

6/6: AtCoder Regular Contest 038 C - 茶碗と豆

供養

問題

Difficulty: 2445 (記事作成時点)

解法

この問題は個数 $i$ の山が $A_{i}$ 個あるNimである
同じ山が $A_{i}$ 個あっても、勝敗に影響するのは $A_{i} % 2$ 個
各についてGrundy数を求めればよい
- $j \lt i$ についてGrundy数 $g$ が最後に登場した $j$ をSegment Treeの $g$ の要素で覚えておく
- $\lbrack 0, g)$ の範囲の最小値が $i - C_{i}$ 以上ならば $i$ のGrundy数は $g$ 以上である
- $g$ について二分探索して求めていく

実装は

要素のSegmnt Tree を用意し、とする
- $\mathit{Get}(g) で \lbrack T_{0}, \dots, T_{g} )$ の範囲の最小値を返す
- $\mathit{Update}(i, x)$ で $T_{i} = x$ に更新する
Grundy数を求める関数を以下のように作る
- $\mathit{Get}(1) \lt i - c$ ならば $0$ を返す
- $\mathit{Get}(m + 1) \ge i - c$ ならば $m +1$ を返す
- $0 \le g \lt m + 1$ の範囲で $\mathit{Get}(g) \ge i - c$ となる最大の $g$ を二分探索で求めて返す
$m = 0$ とする
長さ $N$ の配列 $G$ を用意する
について以下の処理を実施する
- $G_{i} = \mathit{Grundy}(i, C_{i}, m)$ とする
- $\mathit{Update}(G_{i}, i)$ を実施する
- $m = \mathrm{max}(G_{i}, m)$ とする
$X = 0$ とする
$0 \le i \lt N$ について $X = X \oplus (G_{i} \times (A_{i} \% 2))$ とする
$X \ne 0$ ならば First、そうでなければ Second を出力する

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

公式解説

躓いた点

Grundy数を高速に求める方法を思いつかずにTLE

6/7: AtCoder Regular Contest 024 D - バス停

供養

問題

Difficulty: 2447 (記事作成時点)

解法

$x$ を固定して $(x, y_{i})$ にバス停を設置すると、 $x_{i} \le x \le x_{j}$ であるような $i, j$ はマンハッタン距離での移動ができる
$x_{i}, x_{j}$ がともに $x$ より小さい、もしくはともに $x$ より大きい場合は $(x, y_{i}), (x, y_{j})$ を使った移動がマンハッタン距離ではないので、それぞれの集合について再帰的にバス停の配置をしていく
バス停の座標を管理して重複を排除する

実装は

連想配列 $D$ を用意して $D_{x, y}$ に値があれば $(x, y)$ にバス停があるとする
$0 \le i \lt N$ について $D_{x_{i}, y_{i}}$ に値をセットする
$(x_{i}, y_{i})$ を $x_{i}$ についてソートする
空の配列 $B$ を用意する
以下の関数を用意する
- $l = r$ ならそのまま返す
- $m = \frac{l + r}{2}$ とする
- $F(l, m), F(m + 1, r)$ を実施する
- について、以下の処理を実施する
  - $D_{x_{m}, y_{i}}$ に値があれば何もせず次に行く
  - $B$ に $(x_{m}, y_{i})$ を追加する
  - $D_{x_{m}, y_{i}}$ に値をセットする
$F(0, N - 1)$ を実行する
$|B|$ を出力する
$B$ の各要素を出力していく