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

6/15: AtCoder Grand Contest 009 C - Division into Two

供養

問題

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

解法

一般性を失わず $A \le B$ とする
$1 \le i \le N - 2$ について $S_{i + 2} - S_{i} \lt A$ ならば条件を満たすように $S_{i}, S_{i + 1}, S_{i + 2}$ を振り分けることができないので答は0
でまでを分配したときにに振り分けた最大値がであるパターン数とする
- 便宜的に $S_{0} = -\infty$ とし、 $S_{0}$ は $Y$ に分配しているとする
$S_{i} - S_{i - 1} \ge A$ で $S_{i}$ を $X$ に分配するパターン数は $\mathit{X}_{i, j} = \mathit{DP}_{i - 1, j}$ となる
$S_{i} - S_{i - 1} \lt A$ で $S_{i}$ を $X$ に分配するときは $S_{i - 1}$ は $Y$ に分配されている必要があるので、 $\mathit{X}_{i, j \lt i - 1} = 0, \mathit{X}_{i, i - 1} = \mathit{DP}_{i - 1, i - 1}$ となる
$S_{i}$ を $Y$ に分配するときは $\mathit{Y}_{i, j \lt} = 0, \mathit{Y}_{i, i} = \sum_{j | S_{i} - S_{j} \ge B} \mathit{DP}_{i - 1, j}$ となる
$\mathit{DP}_{i, j} = \mathit{X}_{i, j} + \mathit{Y}_{i, j}$ より、 $j \lt i について \mathit{DP}_{i, j} = \mathit{X}_{i, j}$ を求め、 $\mathit{DP}_{i, i} = \mathit{Y}_{i, i}$ とすればよい
愚直に計算すると $O(N^{2})$ だが、 $X_{i, j} = 0$ となる最大の $j$ は $i$ について単調増加であり、 $\sum_{j | S_{i} - S_{j} \ge B} \mathit{DP}_{i - 1, j}$ である最大の $j$ も $i$ について単調増加であることから $\mathit{DP}_{i - 1}$ を使いまわして $\mathit{DP}_{i}$ を作成することが可能で、更新回数の合計も尺取りで $O(N)$ に抑えることができる

実装は

$A \gt B$ ならば $A, B$ を入れ換える
長さ $N + 2$ の配列 $\mathit{DP}$ を用意し、 $\mathit{DP}_{0} = 1, \mathit{DP}_{j \gt 0} = 0$ とする
$S_{0} = -\infty$ とする
$s = 0, t = -1$ とする
について、以下の処理を実施する
- $i \gt 1$ かつ $S_{i} - S_{i - 2} \lt A$ ならば 0 を出力して終了
- である間、以下の処理を実施する
  - $t$ をインクリメントする
  - $\mathit{DP}_{i}$ に $\mathit{DP}_{t}$ を加算する
- $\mathit{DP}_{i + 1} = \mathit{DP}_{i}$ とする
- ならば、となるまで以下の処理を実施する
  - $s \le t$ ならば、 $\mathit{DP}_{i + 1}$ から $\mathit{DP}_{s}$ を減算する
  - $\mathit{DP}_{s} = 0$ とする
  - $s$ をインクリメントする
$\sum_{0 \le i \le N}\mathit{DP}_{i}$ を出力する

計算量は $O(N)$

公式解説

躓いた点

DPを上手く書けなかった

6/18: AtCoder Regular Contest 047 B - 同一円周上

供養

問題

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

解法

$(x_{i}, y_{i})$ は点 $P$ を中心とする軸と並行な状態から45度回転させた正方形上に位置する
全ての点を原点から45度回転させると軸と平行な正方形の状態で計算することが可能
をにマッピングする
- 原点からの距離が $\sqrt{2}$ 倍になるが最終的に戻すので問題ない
マッピング後の正方形の1辺の長さ $D$ は $X = \mathrm{max}(x_{i}^{'}), x = \mathrm{min}(x_{i}^{'}), Y = \mathrm{max}(y_{i}^{'}), y = \mathrm{min}(y_{i}^{'})$ として $D = \mathrm{max}(X - x, Y - y)$ で求められる
このとき、正方形の中心点はのいずれかである
- これらのうちいくつかは同じ点を指すことがある
中心点候補の各点 $(p_{x}^{'}, p_{y}^{'})$ から $(p_{x}, p_{y}) = (\frac{p_{x}^{'} + p_{y}^{'}}{2}, \frac{p_{x}^{'} - p_{y}^{'}}{2})$ に戻し、全ての $(x_{i}, y_{i})$ とのマンハッタン距離が等しい点を1つ出力する

実装は

長さ $N$ の配列 $X, Y$ を用意し、 $X_{i} = x_{i} + y_{i}, Y_{i} = x_{i} - y_{i}$ とする
$x_{\mathit{max}} = \mathrm{max}(X), x_{\mathit{min}} = \mathrm{min}(X), y_{\mathit{max}} = \mathrm{max}(Y), y_{\mathit{min}} = \mathrm{min}(Y)$ とする
$D = \frac{\mathrm{max}(x_{\mathit{max}} - x_{\mathit{min}}, y_{\mathit{max}} - y_{\mathit{min}})}{2}$ とする
$C = \lbrack (x_{\mathit{max}} - D, y_{\mathit{max}} - D), (x_{\mathit{max}} - D, y_{\mathit{min}} + D), (x_{\mathit{min}} + D, y_{\mathit{max}} - D), (x_{\mathit{min}} + D, y_{\mathit{min}} + D)\rbrack$ とする
について以下の操作を実施する
- $x = \frac{C_{i, 0} + C_{i, 1}}{2}, y = \frac{C_{i, 0} - C_{i, 1}}{2}$ とする
- $d = |x_{0} - x| + |y_{0} - y|, \mathit{unique} = \mathrm{true}$ とする
- $1 \le j \lt N$ について、 $|x_{j} - x| + |y_{j} - y| \ne d$ ならば $\mathit{unique} = \mathrm{false}$ とする
- $\mathit{unique} = \mathrm{true}$ ならば $(x, y)$ を出力して終了

計算量は $O(N)$

公式解説

躓いた点

座標を回転させることを思いつかなかった

6/21: AtCoder Grand Contest 046 B - Extension

供養

問題

Difficulty: 1577 (記事作成時点)

解法

ある操作列によって到達可能な塗り方について、そこに到達するまでの操作列を以下のように決める
- 操作によって $i$ 行 $j$ 列となるときに、 $i$ 行目の $j$ 列目までに最終的に黒く塗られるマスがちょうど1つのときはマスを縦に拡張し、そうでない場合は横に拡張する
- $C$ 行 $D$ 列の状態から最上段の黒マスの数に合わせてマスを削減していくことを考え、その逆順に相当する
上記のルールのもと、行列となるときの操作が縦への拡張の場合と、横への拡張の場合のそれぞれについてDPで求める
- 縦への拡張の場合の数を、横への拡張の場合の数をとするとそれぞれ以下のように求められる
  - $\mathit{DP}_{i, j, 0} = (\mathit{DP}_{i - 1, j, 0} + \mathit{DP}_{i - 1, j, 1}) \times j$
  - $\mathit{DP}_{i, j, 1} = \mathit{DP}_{i, j - 1, 0} + \mathit{DP}_{i, j - 1, 1} \times i$
- 便宜的に $\mathit{DP}_{A, B, 1} = 1$ とする

実装は

$(C + 1) \times (D + 1) \times 2$ のDP表 $\mathit{DP}$ を用意し、 $\mathit{DP}_{A, B, 1} = 1$ とする
について、以下の操作を実施する
- について、以下の操作を実施する
  - $i = A$ かつ $j = B$ ならば何もせず次に行く
  - $\mathit{DP}_{i, j, 0} = (\mathit{DP}_{i - 1, j, 0} + \mathit{DP}_{i - 1, j, 1}) \times j$ とする
  - $\mathit{DP}_{i, j, 1} = \mathit{DP}_{i, j - 1, 0} + \mathit{DP}_{i, j - 1, 1} \times i$ とする
$\mathit{DP}_{C, D, 0} + \mathit{DP}_{C, D, 1}$ を出力する