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

5/15: AtCoder Regular Contest 052 D - 9

供養

問題

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

解法

十進表記した $m$ の各桁の和を $D(m)$ としたとき、 $m \% K = S(m) \% K$ より $F(m) = (m - D(m)) \% K = 0$ であればよい
$k = \lceil \frac{\mathrm{log}_{10}M}{2} \rceil$ としたとき、 $m = a \times 10^{k} + b\;(0 \le b \lt 10^{k})$ と表すと、 $F(m) = (F(a \times 10^{k}) + F(b)) \% K$ となる
$0 \le b \lt 10^{k}$ について $F(b)$ の値ごとの出現頻度を前計算しておけば、 $0 \le m \lt \lfloor \frac{M}{10^{k}} \rfloor \times 10^{k}$ の範囲について高速に求められる
$\lfloor \frac{M}{10^{k}} \rfloor \times 10^{k} \le m \le M$ の範囲については愚直に見ていけばよい

実装は

以下の関数を作る
- $s = m, n = m$ とする
- $n \gt 0$ である間、 $s = s + n \% 10, n = \lfloor \frac{n}{10} \rfloor$ とする
- $s \% K$ を返す
$T = 1, n = 1$ とし、 $n \lt M$ である間 $T = 10 \times T, n = 100 \times n$ とする
長さ $T$ の配列 $B$ を用意し、 $B_{i} = F(i)$ とする
連想配列 $M$ を用意し、 $0 \le i \lt T$ について $M_{B_{i}}$ をインクリメントする
$C = -1$ とする
$0 \le a \lt \lfloor \frac{M}{T} \rfloor$ について、 $M_{(K - F(a)) \% K}$ を $C$ に加算する
$0 \le b \le M \% T$ について、 $(F(\lfloor \frac{M}{T} \rfloor) + F(b)) \% K = 0$ ならば $C$ をインクリメントする
$C$ を出力する

計算量は $T = O(\sqrt{M})$ より $O(\sqrt{M}\mathrm{log}\sqrt{M})$

公式解説

躓いた点

何か法則があるかと考えていた

5/16: MUJIN プログラミングチャレンジ Programming Challenge D - 括弧列

供養

問題

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

解法

文字目までの ( の登場回数から ) の登場回数を引いたものをとすると、が括弧列である条件は以下の2つである
- $P_{l_{q} - 1} = P_{r_{q}}$ である
- $\mathrm{min}(P_{l_{q}}, \dots, P_{r_{q} - 1}) \ge P_{r_{q}}$ である
の区間にある ? で ( と ) の登場回数を調整する
- それぞれ $x, y$ 個の ? を ( 、 ) に変換させるとき、先頭の $x$ 個を ( に、残りの $y$ 個を ) に変換する
あらかじめ ? を全て ( に変換した文字列と、全て ) に変換した文字列でそれぞれ $P^{L}_{i}$ と $P^{R}_{i}$ を求めておき、先頭 $x$ 個目の ? の位置までは $P^{L}_{l_{q} - 1}$ と $P^{L}_{i}$ を比較し、それ以降は $P^{R}_{r_{q}}$ と $P^{R}_{i}$ を比較すればよい

実装は

$N + 1 \times 3$ の配列 $A$ を用意する
長さ $N + 1$ の配列 $L, R$ を用意する
について、以下の操作を実施する
- $A_{i + 1} = A_{i}$ とする
- ( のとき以下の操作を実施する
  - $A_{i + 1, 0}$ をインクリメントする
  - $L_{i + 1} = L_{i} + 1$ とする
  - $R_{i + 1} = R_{i} + 1$ とする
- ) のとき以下の操作を実施する
  - $A_{i + 1, 1}$ をインクリメントする
  - $L_{i + 1} = L_{i} - 1$ とする
  - $R_{i + 1} = R_{i} - 1$ とする
- ? のとき以下の操作を実施する
  - $A_{i + 1, 2}$ をインクリメントする
  - $L_{i + 1} = L_{i} + 1$ とする
  - $R_{i + 1} = R_{i} - 1$ とする
Segment Tree を用意し、それぞれとする
- $\mathit{LST.Query}(l, r), \mathit{RST.Query}(l, r)$ でそれぞれ $\lbrack l, r)$ の区間の最小要素を返す
$\lbrack l, r \rbrack$ の範囲で $A_{i, 2} \ge x$ である最小の $i$ を二分探索する関数 $F(x, l, r)$ を作る
について以下の処理を実施する
- $(r_{q} - l_{q}) \% 2 = 0$ ならば No を出力して次に行く
- $|A_{r_{q}, 0} - A_{l_{q} - 1, 0} - A_{r_{q}, 1} + A_{l_{q} - 1, 1}| \gt A_{r_{q}, 2} - A_{l_{q} - 1, 2}$ ならば No を出力して次に行く
- $m = F(\frac{r_{q} - l_{q} + 1}{2} - A_{r_{q}, 0} - A_{l_{q} - 1, 0} + A_{l_{q} - 1, 2}, l, r)$ + 1 とする
- $(l_{q} \lt m \land \mathit{LST.Qurey}(l_{q}, m) \gt L_{l_{q} - 1}) \lor (m \lt r_{q} \land \mathit{RST.Query}(m, r_{q}) \lt R_{r_{q}})$ ならば No を出力して次に行く
- Yesを出力する

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

公式解説

躓いた点

全て ( にしたものと全て ) にしたものの2つを使うことを思いつかなかった

5/17: AtCoder Beginner Contest E - ∙ (Bullet)

供養

問題

Difficulty: 1836 (記事作成時点)

解法

のイワシは自分以外のどのイワシとも仲が悪いので、それらを選ぶときは1匹だけになる
- そのようなイワシが $z$ 匹いるならば、選び方は $z$ 通り
- 以降は $A_{i} \ne 0$ もしくは $B_{i} \ne 0$ のイワシだけを考える
$a_{i} = \frac{|A_{i}|}{\mathrm{GCD}(|A_{i}|, |B_{i}|)}, b_{i} = \frac{|B_{i}|}{\mathrm{GCD}(|A_{i}|, |B_{i}|)}$ とする
$(a_{i}, b_{i})$ が $(0, 1)$ のイワシと $(1, 0)$ のイワシは仲が悪い
との符号が同じイワシは、との符号が異なり、であるようなイワシと仲が悪い
- それぞれ $a_{i}, b_{i}$ をキーにした連想配列でまとめて計算できる
- あるグループ $k$ について、 $A_{i}$ と $B_{i}$ の符号が同じで、 $a_{i} = a_{k}, b_{i} = b_{k}$ なイワシ全てと、それらと仲が悪いイワシ全てが属しており、それぞれ $x_{k}, y_{k}$ 匹いたとき、それらのグループから0匹以上を選ぶ組合せ $C_{k}$ は $2^{x_{k}} + 2^{y_{k}} - 1$ 通り
属するグループが異なるイワシ同士はどのように組合せても問題ないので、 $C_{k}$ は独立に考えることができる
全てのグループ合計で1匹以上を選ぶ組合せは $\prod_{k}C_{k} - 1$ 通り

実装は

連想配列 $X, Y$ を用意する
$z = 0$ とする
について、以下の操作を実施する
- $A_{i} = 0 \land B_{i} = 0$ のとき、 $z$ をインクリメントする
- 上記以外のとき、以下の操作を実施する
  - $a_{i} = \frac{|A_{i}|}{\mathrm{GCD}(|A_{i}|, |B_{i}|)}, b_{i} = \frac{|B_{i}|}{\mathrm{GCD}(|A_{i}|, |B_{i}|)}$ とする
  - $(A_{i} \lt 0 \land B_{i} \lt 0) \lor (A_{i} \gt 0 \land B_{i} \gt 0) \lor A_{i} = 0$ ならば $X_{a_{i, b_{i}}}$ をインクリメントする
  - 上記以外ならば $Y_{a_{i}, b_{i}}$ をインクリメントする
$c = 1$ とする
の各キーについて、以下の操作を実施する
- $Y_{b, a}$ が存在するならば、 $c = c \times (2^{X_{a, b}} + 2^{Y_{b, a}} - 1) \% p$ とする
- $Y_{b, a}$ が存在しなければ、 $c = c \times 2^{X_{a, b}} \% p$ とする
の各キーについて、以下の操作を実施する
- $X_{b, a}$ が存在しなければ、 $c = c \times 2^{Y_{a, b}} \% p$ とする
$(z + c - 1) \% p$ を出力する

計算量は $A = \mathrm{max}(\mathrm{max}(A_{i}), \mathrm{max}(B_{i}))$ として、 $O(N\mathrm{log}A)$

公式解説

躓いた点

時間切れ
int overflow他実装上のバグを多数踏んだ

5/18: AtCoder Regular Contest 043 C - 転倒距離

供養

問題

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

解法

間の転倒距離が奇数の場合、は存在しない
- であるを仮定し、両方で順序が同じペアの数を、のみ順序が異なるペアの数を、のみ順序が異なるペアの数を、両方で順序が異なるペアの数をとすると、以下の式が成り立つ
  - $I_{A, C} = p_{1} + p_{3}$
  - $I_{B, C} = p_{2} + p_{3}$
  - $I_{A, B} = p_{1} + p_{2} = I_{A, C} + I_{B, C} + 2p_{3} = 2(I_{A, C} - p_{3})$
$C_{0} = B$ とすると $I_{A, C_{0}} = I_{A, B}, I_{B, C_{0}} = 0$ である
$C_{0}$ から $A$ に近づいていくようにバブルソートの入れ替えを1回実行したものを $C_{1}$ とすると、 $I_{A, C_{1}} = I_{A, B} - 1, I_{B, C_{1}} = 1$ となる
したがって $C_{\frac{I_{A, B}}{2}}$ を作ればよい
について、におけるの位置より前にあるの数をとすると、の間はとなるようにすればよい
- $x_{i}$ はBITなどで高速に求められる
$\sum_{k}x_{k} \gt \frac{I_{A, B}}{2}$ となるときは、 $B$ で $A_{k}$ を必要なだけ入れ換える操作をして、残りは $B$ の順番通りに出力すればよい

実装は

長さ $N + 1$ の配列 $M$ を用意し、 $0 \le i \lt N$ について [M_{A_{i}} = i + 1] とする
$N \times 3$ の配列 $X$ を用意し、 $0 \le i \lt N$ について $X_{i} = (M_{B_{i}}, B_{i}, i + 1)$ とする
$X$ を各エントリの最初の要素について昇順にソートする
$I = 0$ とする
BITを用意する
- $\mathit{Update}(k, x)$ で $k$ 番目の要素を $x$ に更新し、 $\mathit{Query}(s, t)$ で区間 $\lbrack s + 1, t \rbrack$ の和を出力する
について以下の操作を実施する
- $\mathit{Query}(X_{i, 2}, N)$ を $I$ に加算する
- $\mathit{Update}(X_{i, 2}, 1)$ を実行する
$I \% 2 = 1$ ならば -1 を出力して終了
長さ $N$ の配列 $C$ を用意する
$S = 0$ とする
について以下を実施する
- $\mathit{Update}(X_{i, 2}, 0)$ を実行する
- $s = \mathit{Query}(0, X_{i, 2})$ とする
- ならば以下を実施する
  - $s$ を $S$ に加算する
  - $C_{i} = X_{i, 1}$ とする
  - $B_{X_{i, 2} - 1} = 0$ とする
- 上記以外の場合以下を実施する
  - について、である間以下の操作を実施する
    - $B_{j - 1}$ と $B_{j}$ をswapする
    - $B_{j}$ (i.e. 交換前の $B_{j - 1}$ ) が0以上ならば $S$ をインクリメントする
  - $j = i$ とし、[0 \le j \lt N] について $B_{j} \ge 0$ ならば $C_{k} = B_{j}$ とし、 $k$ をインクリメントする
$C$ を出力する

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

公式解説

躓いた点

バブルソートの入れ替えで転倒数が1動くことに思い至らなかった

5/19: CODE FESTIVAL 2015 予選A D - 壊れた電車

供養

問題

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

解法

ある時刻を固定したときにどれだけの車両を点検できるか考える
- 整備士まででまでの車両を点検できるとする
  - $R_{0} = 0$
- 整備士 $i$ は少なくとも $L_{i} = \mathrm{max}(X_{i} - R_{i - 1} - 1, 0)$ 分を使って $\min(R_{i - 1} + 1, X_{i})$ 両目から $X_{i}$ 両目を整備する必要がある
- $R_{i}$ ははじめに $0$ 両目方向に向かう場合と $N$ 両目方向に向かう場合を比較して $X_{i} + \mathrm{max}(T - 2L_{i}, \frac{T - L_{i}}{2})$ で求められる
- $R_{N} \ge N$ ならば全車両を点検できる
$T$ について二分探索する

実装は

以下の関数を作成する
- $R = 0$ とする
- について、以下の操作を実施する
  - $X_{i} - T \gt R + 1$ ならば $\mathit{false}$ を返す
  - $L = \mathrm{max}(X_{i} - R - 1, 0)$ とする
  - $R = X_{i} + \mathrm{max}(T - 2L, \frac{T - L}{2})$ とする
- $R \ge N$ ならば $\mathit{true}$ 、そうでなければ $\mathit{false}$ を返す
$t = -1, T = 2N$ とし、 $F(T) = \mathit{true}$ である最小の $T$ を二分探索する
$T$ を出力する

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

公式解説

躓いた点

二分探索が思いつかなかった

5/20: AtCoder Beginner Contest 163 F - path pass i

供養

問題

Difficulty: 2401 (記事作成時点)

解法

各色について、その色を通らない単純パスの数を数える
適当な点を根とする根つき木として見たときに、ある点のそれぞれの子について、を通りの色を使わない単純パスを求める
- $v$ の子孫で $c_{w} = c_{u}$ であるような $w$ を根とする部分木 $T_{w}$ に含まれる点は、そこから $v$ を通るパス上で必ず $w$ を通るので $c_{u}$ を使うことになる
- $c_{w} = c_{u}$ かつ $uw$ 間に同色の点がないような $w$ について、 $T_{v} \setminus \cup_{w}T_{w}$ の点を両端とする単純パスは色 $c_{u}$ を使用しないパスである
各色に対応する配列を用意し、DFSで発見したがどのに関連付けて計算されるべきかを管理しながら値を更新していく
- 初期値としてすべての配列は $N$ を持つ
- を訪れたときにの末尾の要素からを減算し、をの末尾に追加する
  - 追加した値を $d$ とする
  - $d$ は $u$ の探索が終わった時に取り除く
- $u$ のそれぞれの子 $v$ について $v$ を探索する前の $d$ の値を $d_{s}$ 、探索後を $d_{t}$ とすると、 $|T_{v} \setminus \cup_{w}T_{w}| = |T_{v}| - (d_{s} - d_{t})$ で表せる

実装は

長さ $N$ の配列 $P, Q, S$ を用意し、0から探索した発見順に $Q$ 、 $P_{v}$ を $v$ の親、 $S_{v}$ を $v$ を根とする部分木の頂点数とする
$N$ 個の空の配列 $D$ を用意し、それぞれ $N$ を配列に挿入する
長さ $N$ の配列 $A$ を用意し、 $A_{i} = \frac{N(N + 1)}{2}$ で初期化する
深さ優先探索をするための関数を以下のように作り、を実行する
- $l = |D_{c_{u}}|$ とし、 $D_{c_{u}, l - 1}$ から $S_{u}$ を減算し、 $S_{u}$ を $D_{c_{u}}$ の末尾に追加する
- の各隣接点について以下の操作を実施する
  - $v = P_{u}$ ならば何もせず次に行く
  - $d_{s} = D_{c_{u}, l}$ とする
  - $\mathit{DFS}(v)$ を実施する
  - $d_{t} = D_{c_{u}, l}$ とする
  - $\frac{(S_{v} - d_{s} + d_{t})(S_{v} - d_{s} + d_{t} + 1)}{2}$ を $A_{c_{u}}$ から減算する
- $D_{c_{u}, l}$ を取り除く
$0 \le i \lt N$ について、 $\frac{D_{i, 0}(D_{i, 0} + 1)}{2}$ を $A_{i}$ から減算する
$0 \le i \lt N$ について、 $A_{i}$ を出力していく

計算量は $O(N)$

公式解説

躓いた点

葉から根方向にDPすると思っていて計算できなかった

5/21: AtCoder Beginner Contest 135 F - Strings of Eternity

供養

問題

Difficulty: 2401 (記事作成時点)

解法

を任意回数繰り返して作成した文字列の文字目から文字でと一致するとき、連続して一致するかの次の判定は文字目から始まる
- 文字列の一致はKMP法などで計算できる
これを $|s|$ の剰余で考えれば、 $0 \le i \lt |s|$ について、 $i$ 文字目から一致し、 $(i + |t|) \% |s|$ 文字目からも一致するなら連続で一致する
上記の関係を $|s|$ 点のグラフで $v_{i} \to v_{(i + |t|) \% |s|}$ の有向辺で表す
連続一致回数の最大値はこのグラフ上での最長パスとなる
- グラフでループが発生しているとき、連続一致回数は無限となる

実装は

$s = s + s$ とし、 $|s| \ge 2 \times |t|$ となるまで $s = s + s$ とする
KMP法で $s$ のうち $t$ とマッチングする開始位置を求め、それらの集合を $K$ とする
長さ $|s|$ の配列 $G$ を用意し、 $G_{i} = -1$ で初期化する
各 $k \in K$ について、 $G_{k \% |s|} = (k + |t|) % |s|$ とする
長さ $|s|$ の配列 $A$ を用意する
について、以下の処理を実施する
- $v = G_{i}$ とする
- である間、以下の操作を実施する
  - $v = i$ ならば $A_{i} = |s|$ としてループを抜ける
  - $A_{i}$ をインクリメントする
  - $A_{v} \gt 0$ ならば $A_{v}$ を $A_{i}$ に加算してループを抜ける
  - $u = v, v = G_{v}$ とし、 $G_{u} = -1$ とする
$\mathrm{max}(A) \ge |s|$ ならば -1 を出力し、そうでなければ $\mathrm{max}(A)$ を出力する