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

4/15: AtCoder Regular Contest 046 C - 合コン大作戦

供養

問題

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

解法

$(A_{i}, B_{i})$ を $A_{i}$ について昇順に、 $A_{i} \ge D_{j}$ であるような $(C_{j}, D_{j})$ から $B_{i} \le C_{j}$ かつ $C_{j}$ が最小の $(C_{j}, D_{j})$ と組むよう選んでいく
$(A_{i}, B_{i})$ は $A_{i}$ について昇順に、 $(C_{j}, D_{j})$ は $C_{j}$ について昇順にソートされているとする
$(A_{i}, B_{i})$ を見ているとき、 $A_{i} \ge D_{j}$ でまだペアを組んでいない $j$ を $j$ 番目の要素の値として持っている Segment Treeに対し、 $B_{i} \le C_{m}$ であるような最小の $m$ について $\lbrack m, M)$ の範囲内で $\mathit{Inf}$ でない最小要素を見つけられたらそこでペアを組む

実装は

$(A_{i}, B_{i})$ を $A_{i}$ について昇順に、 $(C_{j}, D_{j})$ を $C_{j}$ について昇順にソートする
$\lbrack (C_{j}, D_{j}, j) \rbrack$ を $D_{j}$ について昇順にソートしたものを $G = \lbrack (C^{'}_{j}, D^{'}_{j}, j^{'}) \rbrack$ とする
要素数のSegment Tree を用意し、各要素を十分大きな数で初期化する
- $Q(s, t)$ で $\lbrack s, t )$ の最小要素を返すとする
$c = 0, k = 0$ とする
について下記のように操作する
- $k \le M \lor A_{i} \lt G_{k, 1}$ となるまで $\mathit{ST}_{G_{k, 2}}$ を $G_{k, 2}$ に更新して $k$ をインクリメントする
- であるような最小のを二分探索で求める
  - $C_{M - 1} \lt B_{i}$ ならば $m = M$ とする
- $p = Q(m, M)$ とし、 $p \lt \mathit{Inf}$ ならば $\mathit{ST}_{p}$ を $\mathit{Inf}$ に更新して $c$ をインクリメントする
$c$ を出力する

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

公式解説

躓いた点

Segment Treeの更新条件でバグらせてWA

4/16: AtCoder Beginner Contest 009 D - 漸化式

供養

問題

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

解法

との間には、ある行列を用いての関係を作れる
- (整数, XOR, AND) が半環の性質を満たすため
- 通常の行列積の代わりに、加算をXOR、乗算をANDでおこなう
したがって $X^{M - K}(A_{1}, \dots, A_{k})^{T} = (A_{M - K - 1}, \dots, A_{M})$ となる

実装は

$M \le K$ ならば $A_{M - 1}$ を出力して終了
の行列を用意し、下記のように初期化する
- $0 \le i \lt K - 1$ について、 $X_{i, i + 1} = 2^{32} - 1$
- $0 \le i \lt K$ について、 $X_{K - 1, K - 1 - i} = C_{i}$
- それ以外は0
の行列を用意し、、それ以外は0で初期化する
- 単位行列相当となる
とし、となるまで下記の更新を実施する
- $m \% 2 = 1$ ならば $Y = XY$ とする
- $X =XX, m = \lfloor \frac{m}{2} \rfloor$ とする
$a = 0$ とする
$0 \le i \lt K$ について、 $a = a \; \mathrm{XOR}\; (A_{i}\; \mathrm{AND}\; Y_{K - 1, i})$ とする
$a$ を出力する

計算量は $O(K^{3}\mathrm{log}M)$

公式解説

躓いた点

行列式にできることを思いつかなかった

4/17: AtCoder Beginner Contest 008 金塊ゲーム

供養

問題

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

解法

$\mathit{DP}_{i, j, k, l}$ で $i \lt x \lt k, j \lt y \lt k$ であるような $(x, y)$ の範囲についての最大値を持つようなDPをする
座標圧縮して計算量を削減する

実装は

長さ $N + 2$ の配列 $\mathit{AX} = \lbrack 0, X_{0}, \dots, X_{N - 1}, W + 1 \rbrack, \mathit{AY} = \lbrack 0, Y_{0}, \dots, Y_{N - 1}, H + 1 \rbrack$ を用意し、 $\mathit{AX}, \mathit{AY}$ をそれぞれソートする
連想配列 $\mathit{MX}, \mathit{MY}$ を用意し、 $0 \le i \lt N + 2$ について $\mathit{MX}_{\mathit{AX}_{i}} = i, \mathit{MY}_{\mathit{AY}_{i}} = i$ とする
$(N + 2) \times (N + 2) \times (N + 2) \times (N + 2)$ のDP表 $\mathit{DP}$ を用意する
について下記操作を実施する
- について下記操作を実施する
  - について下記操作を実施する
    - $X_{m} \le \mathit{AX}_{i} \lor \mathit{AX}_{i + dx} \le X_{m} \lor Y_{m} \le \mathit{AY}_{i} \lor \mathit{AY}_{i + dy} \le Y_{m}$ ならば何もしない
    - $k = \mathit{MX}_{X_{m}}, l = \mathit{MY}_{Y_{m}}$ とする
    - $\mathit{DP}_{i, j, i + \mathit{dx}, j + \mathit{dy}} = \mathrm{max}(\mathit{AX}_{i + \mathit{dx}} - \mathit{AX}_{i} + \mathit{AY}_{j + \mathit{dy}} - \mathit{AY}_{j} - 3 + \mathit{DP}_{i, j, k, l} + \mathit{DP}_{k, j, i + \mathit{dx}, l} + \mathit{DP}_{i, l, k, j + \mathit{dy}} + \mathit{DP}_{k, l, i + \mathit{dx}, j + \mathit{dy}}, \mathit{DP}_{i, j, i + \mathit{dx}, j + \mathit{dy}})$ とする
$\mathit{DP}_{0, 0, N + 1, N + 1}$ を出力する

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

公式解説

躓いた点

DPの整理が全くできなかった

4/18: AtCoder Regular Contest 036 C - 偶然ジェネレータ

供養

問題

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

解法

を文字目を右端とするすべての部分文字列が条件と矛盾しておらず、それら各部分文字列の (0の数)-(1の数) の最大値が、(1の数)-(0の数) の最大値がであるようなパターン数とする
- $j, k$ は長さ0の部分文字列により非負であるとする
$\mathit{DP}_{i, j, k}$ は、 $i + 1$ 文字目が 0 のとき $\mathit{DP}_{i + 1, j + 1, k - 1}$ にスライドし、1 ならば $\mathit{DP}_{i + 1, j - 1, k + 1}$ にスライドする
また、文字目が 0 のときはにスライドし、1 ならばがにスライドする
- それぞれ部分文字列において (1の数)-(0の数) または (0の数)-(1の数) が0以上になることはない状態なので $k, j$ の変化はなく $j, k$ の最大値だけが伸びる
$i + 1$ 文字目が ? のときは 0 のときと 1 のときの両方の更新をしてパターンを計算する

実装は

$(N + 1) \times (K + 1) \times (K + 1)$ のDP表 $\mathit{DP}$ を用意し、 $\mathit{DP}_{0, 0, 0} = 1$ とする
とし、について下記の更新をする
- のとき、について下記の更新をする
  - $\mathit{DP}_{i + 1, j + 1, 0}$ に $\mathit{DP}_{i, j, 0}$ を加算する
  - $0 \le k \lt K$ について、 $\mathit{DP}_{i + 1, j + 1, k}$ に $\mathit{DP}_{i, j, k + 1}$ を加算する
- のとき、について下記の更新をする
  - $\mathit{DP}_{i + 1, 0, k + 1}$ に $\mathit{DP}_{i, 0, k}$ を加算する
  - $0 \le j \lt K$ について、 $\mathit{DP}_{i + 1, j, k + 1}$ に $\mathit{DP}_{i, j + 1, k}$ を加算する
$\mathit{DP}_{N}$ の合計を出力する

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

公式解説

躓いた点

DPの整理ができなかった
DPを64bit intで作ってMLE

4/19: 天下一プログラマーコンテスト2014予選B C - 天下一王国の歴史

供養

問題

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

解法

ある状態の次の状態について、はの上下左右（存在すれば）のXORとなる
- . を0、# を1とする
上記を踏まえて $C$ の一つ前 $C^{-}$ を考える
$C^{-}$ の1行目を全て . とすると、 $C_{0, j} = C^{-}_{0, j - 1} \oplus C^{-}_{0, j + 1} \oplus C^{-}_{1, j} = C^{-}_{1, j}$ となるので $C^{-}_{1, j} = C_{0, j}$ となる
$C^{-}$ の $i \ge 2$ 行目について、 $i - 1$ 行目まで決まっているとすると、 $C_{i - 1, j} = C^{-}_{i - 2, j} \oplus C^{-}_{i - 1, j - 1} \oplus C^{-}_{i - 1, j + 1} \oplus C^{-}_{i, j}$ より、 $C^{-}_{i, j} = C_{i - 1, j} \oplus C^{-}_{i - 2, j} \oplus C^{-}_{i - 1, j - 1} \oplus C^{-}_{i - 1, j + 1}$ となる

実装は

$N \times N$ の配列 $B$ を用意する
について下記操作を実施する
- $0 \le j \lt N$ について $B_{i + 1, j = C_{i, j}}$ とする
- について下記操作を実施する
  - $C_{i + 1, j} = C_{i + 1, j} \oplus C_{i, j - 1}$ とする
  - $C_{i + 1, j - 1} = C_{i + 1, j - 1} \oplus C_{i, j}$ とする
  - $i \lt N - 2$ のとき、 $C_{i + 2, j} = C_{i + 2, j} \oplus C_{i, j}$ とする
$B$ に対応した盤面を出力する

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

~~公式解説~~

躓いた点

XOR計算であることに気付かなかった
最終行の理解が正しいか納得いっていない

4/20: AtCoder Regular Contest 036 D - 偶数メートル

供養

問題

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

解法

クエリへの自明な解として、同じ連結成分にない場合は到達不可
辺の長さは偶奇のみ意味を持つ
$2N$ 個の頂点を用意し、元のグラフで点 $v$ を意味する点は $2v, 2v + 1$ の2つあると見なす
追加した辺 $uv$ が偶数長のときは $(2u, 2v), (2u + 1, 2v + 1)$ を接続し、奇数長のときは $(2u, 2v + 1), (2u + 1, 2v)$ を接続する
クエリが来たときはが同じ連結成分にあるかを調べる
- 偶数長で到達可能な時のみ同じ連結成分に属する

実装は

長さ $2 \times N$ の配列 $R$ を用意し、 $R_{i} = i$ とする
$R$ を代表点として扱うUniion-Find関数を用意する
のとき、以下の操作を実施する
- $x = x_{i} - 1, y = y_{i} - 1, z = z \% 2$ とする
- $z = 0$ のとき、 $2x$ と $2y$ および $2x + 1$ と $2y + 1$ をそれぞれ結合する
- $z = 1$ のとき、 $2x$ と $2y + 1$ および $2x + 1$ と $2y$ をそれぞれ結合する
$w_{i} = 2$ のとき、 $2(x_{i} - 1)$ の属する連結成分の代表点と $2(y_{i} - 1)$ の属する連結成分の代表点が等しければ YES を出力し、そうでなければ NO を出力する

計算量は $O(\alpha(N))$

公式解説

躓いた点

辺の長さの偶奇で考察が止まった

4/21: AtCoder Beginner Contest 033 D - 三角形の分類

供養

問題

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

解法

任意の $\angle ABC$ について直角の数を $R$ 、鈍角の数を $O$ とすると、すべての三角形における鋭角三角形、直角三角形、鈍角三角形の数はそれぞれ $\frac{N(N - 1)(N - 2)}{6} - R - O, R, O$
各点について、以外の各点との辺を偏角ソートし、各辺についてと直角の辺と鈍角の辺の数を数えていく
- 角度はatan2関数などで求めることができる
- 2周分の角度を配列に入れることで尺取り法で計算できる

実装は

$R = 0, O = 0$ とする
について下記操作を実施する
- 空の配列 $A$ を用意する
- について下記操作を実施する
  - $i = j$ ならば何もしない
  - $a_{j} = \mathrm{atan2}(x_{j} - x_{i}, y_{j} - y_{i}), a^{'}_{j} = a_{j} + 360$ とする
  - $(a_{j}, j), (a^{'}_{j}, j)$ を $A$ に追加する
- $A$ を $a_{j}$ についてソートする
- $k_{1} = 0, k_{2} = 0$ とする
- について下記操作を実施する
  - かつが直角ではない間をインクリメントし続ける
    - 計算誤差で $\angle A_{j, 1}iA_{k_{1}, 1}$ が直角でも $A_{k_{1}, 0} = A_{j, 0} + 90$ になるとは限らない
  - $\angle A_{j, 1}iA_{k_{1}, 1}$ が直角ならば $R, k_{1}$ をそれぞれインクリメントする
  - $k_{2} = \mathrm{max}(k_{1}, k_{2})$ とする
  - $A_{k_{1}, 0} \lt A_{j, 0} + 180$ である間 $k_{2}$ をインクリメントし続ける
  - $O$ に $k_{2} - k_{1}$ を加算する
$\frac{N(N - 1)(N - 2)}{6} - R - O, R, O$ を出力する