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

1/1: AtCoder Beginner Contest 149 E - Handshake

供養

問題

Difficulty: Undefined (記事作成時点)

解法

「左手で握手する相手を固定したときに幸福度上昇値が $X$ 以上となる右手の相手の数」の合計が $M$ 人以上になるような $X$ を最大化する

をパワー以上のゲストが何人いるかを表す配列とする
- 累積和で計算可能
$P_{X} = \sum_{1 \le i \le N}B[X - A_{i}\rbrack \ge M$ となるような最大の $X$ を二分探索で求める
$A$ を降順にソートして累積和を求めたものを $C = \lbrack c_{k} \mid c_{k} = \sum_{i \le k}A_{i},\; \forall \; i, j. \; i \le j \Rightarrow A_{i} \ge A_{j} \rbrack$ とする
i.e. 左手を固定して $j$ 人と握手したときの幸福度上昇の右手の寄与分の最大値となる
を出力する
- $P_{X} \gt M$ の可能性があるので超過分を減算する

計算量は $L = \mathrm{max}(A)$ とすると $B$ の計算に $O(L)$ 、 $P_{X}$ を1回求めるために $O(N)$ 、二分探索を $O(\mathrm{log}L)$ 回、出力は $O(N)$ なので合計で $O(N\mathrm{log}L + L)$

公式解説

躓いた点

1回の握手に下限をつける発想が出なかった

1/2 AtCoder Beginner Contest 149 F - Surrounded Nodes

供養

問題

Difficulty: Undefined (記事作成時点)

解法

解法1

部分木の辺の数の期待値が求められれば部分木の頂点数の期待値が求められる。黒く塗る頂点数の期待値は $\frac{N}{2}$ なので、部分木の頂点数の期待値から引けばよい

各辺について、側、側それぞれの部分木の頂点数を求め、とする
- 適当な頂点を根としたとき、ある頂点 $v$ からその頂点を根とする部分木の頂点数 $n_{v}$ と $N - n_{v}$ が $v$ とその親 $u$ を結ぶ辺 $(v, u)$ について両端点の部分木の頂点数となる
- DFSして子の頂点数の合計+1を返すようにしていけばよい
以降の計算で使うためを法としたを計算しておく
- $2^{-1} \equiv 500000004\; (\mathrm{mod}\; p)$ 、 $2^{-k} \equiv 2^{-(k-1)} \times 2^{-1}\; (\mathrm{mod}\; p)$ で帰納的に求められる
辺の数の期待値 $E$ は各辺が含まれる確率の合計なので、 $E = \sum_{1 \le i \le N - 1}(1 - (\frac{1}{2})^{X_{i}}) \times (1 - (\frac{1}{2})^{Y_{i}})$ で求められる
i.e. $E \equiv \sum_{1 \le i \le N - 1}(1 - r_{X_{i}}) \times (1 - r_{Y_{i}})\; (\mathrm{mod} p)$
辺の数が0のときは頂点数が1のときと頂点数が0のときがあるので、頂点数0の確率を減算することで頂点数の期待値 $V$ は $V = E + 1 - (\frac{1}{2})^{N}$ で求められる
i.e. $V \equiv E + 1 - r_{N}\; (\mathrm{mod} p)$
黒く塗る頂点数の期待値を減算して $V - \frac{N}{2} \equiv V - N \times 2^{-1}\; (\mathrm{mod}\; p)$ を出力する

解法2

各頂点について、それが $S$ に含まれる白く塗った頂点である確率の合計が穴あき度の期待値となる

解法1と同様に $p = 10^{9} + 7$ を法とした $R = \lbrack r_{k} \mid r_{k} \equiv 2^{-k}\; (\mathrm{mod}\; p) \rbrack\; (1 \le k \le N)$ を計算しておく
適当な点を根としたときに、ある点 $v$ を根とする部分木の頂点数を $n_{v}$ 、 $v$ の子であるような頂点集合を $C_{v} = \lbrace c_{j} \rbrace$ とすると、 $v$ を除いたときにできる部分木の頂点数集合 $S(v)$ は $S(v) = \lbrace n_{c_{1}}, \dots, n_{c_{\mathit{deg}(v) - 1}}, N - 1 - \sum_{1 \le j \le \mathit{deg}(v) - 1}n_{c_{j}}\rbrace$ である
ある頂点 $v$ が $S$ に含まれる白く塗った頂点である確率 $E(v)$ は、 $v$ が白かつ $v$ を取り除いたときにできる部分木の2つ以上に少なくとも1点黒く塗る点がある確率であり、すなわち $v$ が黒、もしくは $v$ は白だが少なくとも1点黒く塗った部分木が高々1つしかない場合の余事象の確率であるので、以下のように求められる
$\begin{aligned} E(v) &= 1 - \frac{1}{2} - \frac{1}{2} \times \biggl( \Bigl( \frac{1}{2} \Bigr) ^{N - 1} + \sum_{s \in S(v)} \Bigl( 1 - \Bigl( \frac{1}{2} \Bigr) ^{s} \Bigr) \times \Bigl( \frac{1}{2} \Bigr) ^{N - 1 - s} \biggr)\\ &= \frac{1}{2} - \Bigl( \frac{1}{2} \Bigr) ^{N} - \sum_{s \in S(v)} \Bigl( 1 - \Bigl( \frac{1}{2} \Bigr) ^{s} \Bigr) \times \Bigl( \frac{1}{2} \Bigr) ^{N - s} \\ &= \frac{1}{2} + \bigl(\mathit{deg}(v) - 1 \bigr) \times \Bigl( \frac{1}{2} \Bigr) ^{N} - \sum_{s \in S(v)} \Bigl( \frac{1}{2} \Bigr) ^{N - s} \end{aligned}$ i.e. $E(v) \equiv 2^{-1} + \bigl(\mathit{deg}(v) - 1 \bigr) \times r_{N} - \sum_{s \in S(v)}r_{N - s}\; (\mathrm{mod}\; p)$
$\sum_{v \in V}E(v)\; (\mathrm{mod}\; p)$ を出力する

計算量はどちらの解法でも $O(N)$

公式解説

躓いた点

解法2で計算を整理しきれずにTLE

1/3 AtCoder Regular Contest 042 C - おやつ

供養

問題

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

解法

おやつを価格に対して降順にソートしたものを $\lbrack (A_{k}, B_{k}) \mid \forall \; i, j. \; i \le j \Rightarrow A_{i} \ge A_{j} \rbrack$ とする
長さ $P + \mathrm{max}(A_{k}) + 1 = P + A_{0} + 1$ のDP表を作り、すべて0で初期化する
について、選ぶおやつの最低価格をとしたとき、についてとDP表を更新していく
- 合計価格が $P + A_{k}$ 以下ならば、選択した任意のおやつ $(A_{i}, B_{i})\; (i \le k)$ について $A_{i} \ge A_{k}$ なので、 $P + A_{k} - A_{i} \le P$ となる
DP表の最大値を出力する

計算量はソートとDP表の計算で $O(N\mathrm{log}N + PN)$

公式解説

躓いた点

ソートせずにDPしてWA&TLE
ソートして貪欲法が使えないか考えたが、（当然）アイディアがなかった

1/4 AtCoder Regular Contest 027 C - 最高のトッピングにしような

供養

問題

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

解法

トッピングを $i\; (1 \le i \le N)$ 種類まで選べるときに、実際に選択したトッピングが $j\; (0 \le j \le X)$ 種類、利用できるすべてのチケットの枚数が $k\; (0 \le k \le X + Y)$ 枚であるとしてDPをする
DP表の更新は
となる
- DP表は3次元である必要はなく、 $i = 1, \dots, N$ について、まず $j = \mathrm{min}(X, i), \dots, 1,\; k = X + Y - j, \dots, t_{i} - 1$ と降順で $\mathit{DP} \lbrack j \rbrack \lbrack k \rbrack = \mathrm{max}(\mathit{DP} \lbrack j - 1 \rbrack \lbrack k - t_{i} + 1 \rbrack + h_{i}, \mathit{DP} \lbrack j \rbrack \lbrack k \rbrack)$ を計算し、その後 $j = 1, \dots, X,\; k = 1, \dots, X + Y$ と昇順で $\mathit{DP} \lbrack j \rbrack \lbrack k \rbrack = \mathrm{max}(\mathit{DP} \lbrack j - 1 \rbrack \lbrack k \rbrack, \mathit{DP} \lbrack j \rbrack \lbrack k - 1 \rbrack, \mathit{DP} \lbrack j \rbrack \lbrack k \rbrack)$ を計算して更新していくことでメモリ使用量を節約できる
$\mathit{DP} \lbrack N \rbrack \lbrack X \rbrack \lbrack X + Y \rbrack$ （もしくは $\mathit{DP} \lbrack X \rbrack \lbrack X + Y \rbrack$ ）を出力する

計算量は $O(NX(X + Y))$

公式解説

躓いた点

部分点解法（公式解説参照）である、軸が選択可能なトッピング、スペシャルチケットの使用枚数、一般チケットの使用枚数である $O(NXY(X + Y))$ のDPしか出てこなかった
3次元DP表を作ったら珍しくMLE

1/5 エクサウィザーズ 2019 D - Modulo Operations

供養

問題

Difficulty: 2039 (記事作成時点)

解法

任意の操作結果の合計は、操作結果の期待値を $N!$ 倍すれば得ることができる
$S = \lbrack s_{1}\, \dots, s_{N} \rbrack$ を狭義単調減少列とすると、ある操作列 $S^{'}$ において $s_{i}$ が元の順番よりも後ろに位置した場合、少なくとも1回は自身より小さい数で事前にmodをとられているので、 $X$ の減少には寄与しない
そのため、がに影響を与えられる（可能性のある）確率はより前にが登場していない確率である
- $\lbrace s_{i}, \dots, s_{N} \rbrace$ のみに注目したときに $s_{i}$ が最初に登場する確率とも言えるので、 $P_{i} = \frac{1}{N + 1 - i}$
$x_{0} = X, x_{1}, \dots, x_{N}$ に対し確率 $P_{i}$ で $x_{i}\ = x_{i - 1}\; \mathrm{mod}\; s_{i}$ と変化させる場合の $x_{N}$ の期待値をDPで求める

実装としては

$F = \lbrack f_{k} \mid f_{k} \equiv k!\; (\mathrm{mod}\; p) \rbrack, R = \lbrack r_{k} \mid r_{k} \equiv k^{-1}\; (\mathrm{mod}\; p) \rbrack$ を計算しておく
$0 \le i \le N, 0 \le j \le X$ について、 $\mathit{DP} \lbrack i \rbrack \lbrack j \rbrack = 0$ に初期化する
とし、について、以下のようにDP表を更新していく
- 確率 $P_{i}$ で変化させる場合
  $\begin{aligned} \mathit{DP} \lbrack i \rbrack \lbrack j\; \mathrm{mod}\; s_{i} \rbrack &\equiv \mathit{DP} \lbrack i \rbrack \lbrack j\; \mathrm{mod}\; s_{i} \rbrack + \mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack \times \frac{1}{N + 1 - i}\\ &\equiv \mathit{DP} \lbrack i \rbrack \lbrack j\; \mathrm{mod}\; s_{i} \rbrack + \mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack \times r_{N + 1 - i} \end{aligned}$
- 変化させない場合
  $\begin{aligned} \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack &\equiv \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack + \mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack \times \frac{N - i}{N + 1 - i}\\ &\equiv \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack + \mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack \times (N - i) \times r_{N + 1 - i} \end{aligned}$
$x_{N}$ の期待値 $E$ を $E \equiv \sum_{0 \le j \le X}j \times \mathit{DP} \lbrack N \rbrack \lbrack j \rbrack$ と求める
期待値に $N!$ を乗算して $E \times N! \equiv E \times f_{N}$ を出力する

計算量はソートとDPの計算で $O(N\mathrm{log}N + NX)$

公式解説

躓いた点

期待値を $N!$ すれば合計値という発想がなかった
期待値の計算ができてない

1/6 AtCoder Beginner Contest 145 F - Laminate

供養

問題

Difficulty: 2044 (記事作成時点)

解法

高さを変化させるということはその列を無視することに等しい
ある集合 $\lbrack H_{1}, \dots, H_{k} \rbrack$ の右側に高さ $h$ の列を追加すると、操作回数は $\mathrm{max}(h - H_{k}, 0)$ 回増える

以上より、高さを変化させていない列の数と、そのときの一番右の列を固定するDPを行う

$i = 0, \dots, N - K, j = 0, \dots, N$ について $\mathit{DP} \lbrack i \rbrack \lbrack j \rbrack$ を十分大きな値で初期化する
$\mathit{DP} \lbrack 0 \rbrack \lbrack 0 \rbrack = 0$ とする
についてで更新していく
- $H_{0} = 0$ とする
$\mathrm{min}(\mathit{DP}\lbrack N - K \rbrack)$ を出力する

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

公式解説

躓いた点

DPで固定するパラメータを使用した列と無視した列の数にしてWA

1/7 AtCoder Beginner Contest 139 F - Engines

供養

問題

Difficulty: 2058 (記事作成時点)

解法

各エンジン $(x_{i}, y_{i})$ について、推力のベクトルとx軸 $(1, 0)$ との偏角を $\theta_{i}$ としたとき、任意の角度 $\theta$ の方向へ最も遠く行くためには $\theta - 90 \le \theta_{i} \le \theta + 90$ であるようなエンジンをすべて使えばよい

各エンジンのとの偏角を求める
- $(0, 0)$ は除外する
- $\mathrm{cos}\theta_{i} = \frac{x_{i}}{\sqrt{x_{i}^{2} + y_{i}^{2}}}$ を用いて以下のように求められる
  $\theta_{i} = \left\{ \begin{array}{ll} \mathrm{a}\mathrm{cos} ( \mathrm{cos} \theta_{i} ) & ( y_{i} \ge 0 ) \\ 360 - \mathrm{a}\mathrm{cos} ( \mathrm{cos} \theta_{i} ) & ( y_{i} \lt 0 ) \end{array} \right.$
$E = \lbrack (x_{i}, y_{i}, \theta_{i}) \mid x_{i} \neq 0 \lor y_{i} \neq 0 \rbrack$ とする
各 $(x_{i}, y_{i}, \theta_{i}) \in E$ について、 $(x_{i}, y_{i}, \theta_{i} + 360), (0, 0, \theta_{i} - 180), (0, 0, \theta_{i} + 180), (0, 0, \theta_{i} + 540)$ を $E$ に追加する
をについて昇順にソートしとする
- 偏角ソートは幾何問題の頻出テクニックらしい
について、を合成したベクトルの原点からの距離をとする
- $(x_{i}, y_{i}, \theta_{i} + 360)$ は $180 \lt \theta^{'}_{j} \lt 360$ のときに $\theta_{i} \lt 180$ であるような $(x_{i}, y_{i}, \theta_{i})$ を集合に含めるときのために用意
- $(0, 0, \theta_{i} - 180)$ は $(x_{i}, y_{i}, \theta_{i})$ を含まない集合を作るためのダミーとして用意
- $(0, 0, \theta_{i} + 180)$ は $(x_{i}, y_{i}, \theta_{i} + 360)$ を含まない集合を作るためのダミーとして用意
- は番兵なので境界条件を上手いことやれば追加の必要はない
  - $x^{'}_{j} \neq 0 \land y^{'}_{j} \neq 0$ であるような $(x^{'}_{j}, y^{'}_{j}, \theta^{'}_{j})$ を起点とする計算を $|E|$ 回実施したら終了する、など
$\mathrm{max}(d_{j})$ を出力する