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

5/1: AtCoder Regular Contest 026 D - 道を直すお仕事

供養

問題

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

解法

時給 $x$ を固定したときに採算がとれるかを調べる
$\sum \frac{C}{T} \le x$ より $\sum C \le x \sum T \to \sum C - x \sum T \le 0 \to \sum (C - xT) \le 0$ が言える
$C - xT \le 0$ の辺を全て持った状態から $C - xT \gt 0$ の辺についてKruskal法などでグラフが連結になるまで辺を追加していく
最終的に採用した辺について $\sum \frac{C}{T} \le x$ ならば採算がとれる
$x$ について適当な数 $K$ 回の二分探索で答えを絞っていく

実装は

$X = \frac{\sum_{i = 0}^{N -1}C_{i}}{\sum_{i = 0}^{N - 1}T_{i}}, x = 0$ とする
Union-Findの関数 $\mathit{Find}(x)$ 、 $\mathit{Unite}(x, y)$ を用意する
以下の操作を回程度繰り返す
- $m = \frac{X + x}{2}$ とする
- $R_{i} = (A_{i}, B_{i}, C_{i}, T_{i})$ を $C_{i} - m \times T_{i}$ について昇順にソートする
- $C = 0, T = 0$ とする
- について、以下の操作を実施する
  - $r_{a} = \mathit{Find}(A_{i}), r_{b} = \mathit{Find}(B_{i})$ とする
  - $C_{i} - m \times T_{i} \gt 0$ かつ $r_{a} = r_{b}$ ならば何もせず次に行く
  - もしくはならば以下の操作を実施する
    - $\mathit{Unite}(A_{i}, B_{i})$ を実施する
    - $C_{i}$ を $C$ に追加する
    - $T_{i}$ を $T$ に追加する
- $\frac{C}{T} \le m$ ならば $X = m$ とし、そうでなければ $x = m$ とする
$X$ を出力する

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

公式解説

躓いた点

二分探索せずに求めようとしてWA
辺を考慮する順番を $\frac{C_{i}}{T_{i}}$ で考えてWA

5/2: AtCoder Beginner Contest 165 C - Many Requirements

供養

問題

Difficulty: 1197 (記事作成時点)

解法

の数列を全て作って計算する
- パターン数は
  - $N \le 10, M \le 10$ だと $_{19}\mathrm{C}_{10} = 92378$ 程度

実装は

長さ $N + 1$ の配列 $A$ を用意し、 $A_{0} = 1$ とする
とし、以下の関数についてを実行する
- $n \le N$ のとき、 $a = A_{i - 1}, \dots, M$ について $A_{i} = a$ とし、 $F(n + 1)$ を実行する
- のとき、以下を実施する
  - $x = 0$ とする
  - $0 \le i \lt Q$ について、 $A_{b_{i}} - A_{a_{i}} = c_{i}$ ならば $d_{i}$ を $x$ に加算する
  - $X = \mathrm{max}(x, X)$ とする
$X$ を出力する

計算量はパターン生成に $O(N_{N + M}\mathrm{C}_{N})$ 、1パターンあたり $O(Q)$ の計算をするので全体で $O(N_{N + M}\mathrm{C}_{N}Q)$

公式解説

躓いた点

$_{19}\mathrm{C}_{10}$ がもっと大きいと思って別の解法を探していた

5/3: AtCoder Beginner Contest 165 E - Rotation Matching

供養

問題

Difficulty: 1693 (記事作成時点)

解法

を前半と後半に分割する
- 前半 $1 \le k \le \lfloor \frac{M}{2} \rfloor$ について、 $(k, M + 1 - k)$ をマッチングさせる
- 後半 $1 \le k \le \lceil \frac{M}{2} \rceil$ について、 $(M + k, 2M + 2 - k)$ をマッチングさせる
$M$ が奇数（偶数）のとき、前半で自身の前後各 $M$ 個のうち差が偶数（奇数）のものとマッチングし、後半で差が奇数（偶数）のものとマッチングすることになる

実装は

$1 \le k \le \lfloor \frac{M}{2} \rfloor$ について、 $k, M + 1 - k$ を出力していく
$1 \le k \le \lceil \frac{M}{2} \rceil$ について、 $M + k, 2M + 2 - k$ を出力していく

計算量は $O(M)$

公式解説

躓いた点

思いつかなかった

5/4: AtCoder Beginner Contest 165 F - LIS on Tree

供養

問題

Difficulty: 1780 (記事作成時点)

解法

各点 $u$ について、根から $u$ までのパスにおける $A_{u}$ を用いた最長増加部分列の長さを $l_{u}$ とする
根から $u$ までのパス上の各点 $v$ を用いて $L_{i} = \mathrm{min}(A_{v} | l_{v} = i)$ としたときに、 $L_{i} \lt A_{u}$ であるような最大の $i$ を用いて $l_{u} = i + 1$ と表せる
$A_{u} \ge L_{i}$ であるような最小の $i$ について $L_{i} = A_{u}$ と更新していくことで深さ優先探索をしながら $l_{u}$ を求めることができる
求めたい値は $u$ の親 $p$ までの最長増加部分列の長さ $M_{p}$ を用いて $\mathrm{max}(M_{p}, l_{u})$

実装は

0-indexで木 $T$ を作成する
長さ $N + 1$ の配列 $L$ を用意し、 $L_{0} = 0, L_{i \ne 0} = \mathrm{max}(A) + 1$ とする
長さ $N$ の配列 $P$ を用意する
長さ $N$ の配列 $\mathit{DP}$ を用意する
下記関数を定義し、を実行する
- $A_{u} \le L_{i}$ であるような最小の $i$ を二分探索する
- $\mathit{val} = L_{i}$ とする
- $L_{i} = A_{u}$ とする
- $\mathit{DP}_{u} = \mathrm{max}(i, \mathit{DP}_{P_{u}})$ とする
- の各隣接点について下記を実行する
  - $v = P_{u}$ ならば何もしない
  - $v \ne P_{u}$ ならば $P_{v} = u$ とし、 $F(v)$ を実行する
- $L_{i} = \mathit{val}$ とする
$i = 0, \dots, N$ について $M_{i}$ を出力していく

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

公式解説

躓いた点

時間切れ
$L$ の更新手法を閃くのが遅かった

5/5: AtCoder Regular Contest 054 C - 鯛焼き

供養

問題

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

解法

$N$ 要素の任意の順列 $\sigma$ およびその集合 $P$ について、 $\sum_{\sigma \in P}\prod_{i = 1}^{N}S_{i, \sigma(i)}$ の偶奇が求めたいもの
ところで、行列 $S$ の行列式は $|S| = \sum_{\sigma \in P}\mathit{sgn}(\sigma)\prod_{i = 1}^{N}S_{i, \sigma(i)}$ である
$\mathit{sgn}(\sigma)$ は $\pm 1$ なので偶奇としては必ず奇数であり、 $\sum_{\sigma \in P}\prod_{i = 1}^{N}S_{i, \sigma(i)} \equiv |S|\; (\mathrm{mod}\; 2)$ である
また、 $|S|$ の計算過程に出てくる各要素も偶奇だけに着目して常に $S_{i, j} \in \lbrace 0, 1 \rbrace$ としても $|S| \% 2$ と一致する

実装は

の行列に関する以下の関数を作成する
- について以下の計算をする
  - ならば、について以下の操作を実施する
    - $S_{k, 1} = 1$ ならば $S_{i}$ と $S_{k}$ を入れ換えてループを抜ける
  - $S_{i, i} = 0$ ならば 0 を返す
  - について以下の操作を実施する
    - $s = S_{k, i}$ とする
    - $j = i, \dots, N - 1$ について $S_{k, j} = S_{k, j}\; \mathrm{XOR}\; (S_{i, j} \times s)$ とする
- 1 を返す
$\mathit{det}(S) = 0$ ならば Even を出力し、そうでなければ Odd を出力する

計算量は $O(N^{3})$

公式解説

躓いた点

行列式との関係が思い至らなかった
行列式の計算が上手く実装できずWA

5/6: AtCoder Regular Contest 052 C - 高橋くんと不思議な道

供養

問題

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

解法

各点 $u$ について、タイプBの道を極力通らずに到達させる場合の最短距離を $d^{'}_{u}$ 、このときのタイプBの道の使用回数を $c^{'}_{u}$ とする
までの最短路について、タイプBの道の使用回数をとしたとき、は高々である
- $c^{*}_{u} = c_{u} + k$ としたとき、 $\frac{(c_{u} + k)(c_{u} + k + 1)}{2} + \alpha \le \frac{c(c + 1)}{2} + \beta$ より $k(k + 2c + 1) \le 2(\beta - \alpha)$ となり、 $\alpha, \beta$ はそれぞれタイプAの道の使用回数であることから $k^{2} \le k(k + 2c + 1) \le 2(\beta - \alpha) \le 2N$ である
あらかじめ各点 $u$ について $c_{u}$ を求めておき、 $u$ に到達するまでのタイプBの道の使用回数が $c_{u} \le k \le c_{u} + \sqrt{2N}$ のときの最短距離を求めていけばよい

実装は

Priority Queue を用意する
- $\mathit{PQ}$ の各要素を $e$ としたとき、 $e$ のうち最初の要素が小さい順にPopするとする
長さ $N$ の配列 $D$ を用意し、 $D_{0} = 0, D_{i \ne 0} = N \times N$ とする
以下のルールで点0を起点にグラフを探索し、点までの最短距離をとする
- $C_{j} = 0$ の道を通るときは長さ $1$ とする
- $C_{j} = 1$ の道を通るときは長さ $N$ とする
長さ $N$ の配列 $X, Y$ を用意し、 $0 \le i \lt N$ について $X_{i} = \lfloor \frac{D_{i}}{N} \rfloor, Y_{i} = D_{i} \% N + \frac{X_{i}(X_{i} + 1)}{2} + 1$ とする
$N$ 個のハッシュマップの配列 $H$ を用意し、 $H_{0, 0} = 0$ とする
にをPushする
- 距離、頂点、タイプBの道の使用回数の組とする
が空になるまで下記操作を実施する
- $\mathit{PQ}$ からPopし $(d, u, k)$ とする
- $d \gt H_{u, k}$ ならば何もせず次に行く
- の各隣接点について下記操作を実施する
  - 辺がタイプAの場合
    - $d + 1 \ge \mathrm{min}(H_{v, k}, Y_{v})$ ならば何もせず次に行く
    - $d + 1 \lt \mathrm{min}(H_{v, k}, Y_{v})$ ならば $H_{v, k} = d + 1$ とし、 $(d + 1, v, k)$ を $\mathit{PQ}$ にPushする
  - 辺がタイプBの場合
    - $d + k + 1 \ge \mathrm{min}(H_{v, k + 1}, Y_{v})$ ならば何もせず次に行く
    - $d + k + 1 \lt \mathrm{min}(H_{v, k + 1}, Y_{v})$ ならば $H_{v, k + 1} = d + k + 1$ とし、 $(d + k + 1, v, k + 1)$ を $\mathit{PQ}$ にPushする
$0 \le i \lt N$ について $\mathrm{min}(H_{i})$ を出力していく

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

公式解説

躓いた点

タイプBの使用回数の最小値をあらかじめ求めておくアイデアがなかった
不要な要素をPriority Queueに入れないなどの高速化処理が甘くTLE連発

5/7: AtCoder Regular Contest 049 C - ぬりまーす

供養

問題

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

解法

ある2点 $a, b$ について、 $b$ よりも $a$ を先に塗らないといけないという関係を $a \to b$ で表す
タイプ1の辺について、 $y_{i} \to x_{i}$ となる
タイプ2の辺について、 $u_{j}$ を塗らないか、 $u_{j} \to v_{j}$ とするかを選ぶ
任意の $b$ について、 $a \to b$ であるような全ての $a$ が塗られていれば $b$ を塗るという操作を更新されなくなるまで実施して塗った点を数えればよい
上記の計算をタイプ2でどちらを選択したかについて全通り試して最大値を返す

実装は

タイプ1の辺について0-indexで格納する
タイプ2の辺について0-indexで格納する
入力について以下の計算をする関数を作成する
- 長さ $N$ の配列 $V, C$ を用意し、 $C_{i} = 0$ とする
- とし、である間以下の更新を繰り返す
  - $\mathit{update} = \mathit{false}$ とする
  - $0 \le k \lt N$ について $V_{k} = 1$ とする
  - $0 \le i \lt A$ について、 $V_{x_{i}} = V_{x_{i}}\; \mathrm{AND}\; C_{y_{i}}$ とする
  - について、以下の操作を実施する
    - $m\; \mathrm{AND}\; 2^{j} = 0$ ならば $V_{u_{j}} = 0$ とする
    - $m\; \mathrm{AND}\; 2^{j} \gt 0$ ならば $V_{v_{j}} = V_{v_{j}}\; \mathrm{AND}\; C_{u_{j}}$ とする
  - $0 \le k \lt N$ について、 $V_{k} = 1 \land C_{k} = 0$ ならば $C_{k} = 1, \mathit{update} = \mathit{true}$ とする
- $\sum_{k = 0}^{N - 1}C_{k}$ を出力する
$0 \le m \lt 2^{B}$ について、 $\mathrm{max}(F(m))$ を出力する