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

1/8: AtCoder Beginner Contest 140 F - Many Slimes

供養

問題

Difficulty: 2066 (記事作成時点)

解法

以下の条件を満たす完全二分木を考える
- 葉に $S$ の各要素の値を重複なく持つ
- 葉以外の各頂点について、2つの子のうち大きい方を持つ
上記のような木が存在する場合、根から深さの頂点集合が秒後のスライムの集合を表す
- （葉以外の）各頂点で表現されるスライムが自身の子で表現されるスライムに分裂することを意味する

上記のような木を構成するための適切な葉の配置の条件は、任意の部分木について、部分木の葉集合の最大値を持つ葉が1つであることである

$S$ を降順にソートする
$\mathit{CC} = \lbrace 2^{N} \rbrace$ とする
とし、とする
- $S$ の先頭から $|S_{0}|$ 個取り除く
$|\mathit{CC}| \lt |S_{0}|$ ならば No を出力して終了
から要素の大きい順に個取り出したものをとし、とする
- $\mathit{CC}$ をPriority-Queueで表現し、 $|S_{0}|$ 回Popすればよい
各 $c_{i} \in C$ について、 $\lbrace 1, \dots, 2^{j}, \dots, \frac{c_{i}}{2} \rbrace$ を $\mathit{CC}$ に追加する
上記を $S$ が空になるまで繰り返せたら Yes を出力する

計算量は $O(|S|\mathrm{log}|S|) = O(N2^{N})$

公式解説

躓いた点

同値のものをまとめて計算する発想がなく、都度分割できる連結成分を探していてTLE

1/9: AtCoder Regular Contest 077 E - guruguru

供養

問題

Difficulty: 2075 (記事作成時点)

解法

お気に入りの明るさ $x$ を $k$ から $k + 1$ に変化させたときに、それぞれの区間についてボタンを押す回数がどのように増減するか考え、帰納的に求めていく

$a_{i} \lt k \lt a_{i + 1}$ のときはお気に入りボタンを1回押してから順送りボタンで $a_{i + 1}$ に到達するまで押すので、 $x = k$ を $x = k + 1$ にするとボタンを押す回数が1回減る
$a_{i + 1} = k$ のときはお気に入りボタンを1回押すだけでよかったものが全部順送りボタンで操作しないといけなくなるためボタンを押す回数が $a_{i + 1} - a_{i} - 1$ 回増える
$a_{i + 1} \lt k \ge a_{i}$ のときは順送りボタンだけで操作すればよいので変化なし

上記操作はループの処理を省略しているので、実装としては

計算の都合上、についてとする
- $1 \le a_{i} \le m$ を $0 \le a^{'}_{i} \le m - 1$ にする
について、0で初期化した配列に以下の操作をする
- $B \lbrack a^{'}_{i} + 2 \rbrack$ を1増加させる
- $B \lbrack a^{'}_{i + 1} + 1 \rbrack$ を1減少させる
- $a^{'}_{i} \gt a^{'}_{i + 1} \land a^{'}_{i} \lt m - 1$ ならば $B \lbrack 0 \rbrack$ を1増加させる
- $a^{'}_{i} = m - 1$ ならば $B \lbrack 1 \rbrack$ を1増加させる
の累積和をとする
- $S \lbrack k + 1 \rbrack\; (0 \le k \lt m - 1)$ は $x$ を $k$ から $k + 1$ に変化させたときにボタンを押す回数が1回減る区間の数を表す
$i = 2, \dots, n$ について、 $X \lbrack a^{'}_{i} \rbrack$ が $i$ をもつような二次元配列 $X$ を作る
$x = 0$ のときのボタンを押す回数 $C_{0}$ を以下のように求める
$$ C_{0} = \sum_{i = 1}^{n - 1} \left \{ \begin{array}{} (a^{'}_{i + 1} + M - a^{'}_{i})\; \mathrm{mod}\; M & \mathrm{if}\; a^{'}_{i} \lt a^{'}_{i + 1} \\ a^{'}_{i + 1} & \mathrm{else} \end{array} \right. $$
$i = 1, \dots, m - 1$ について、 $C_{i} = C_{i - 1} - S \lbrack i \rbrack + \sum_{a^{'}_{j} \in X \lbrack i - 1 \rbrack}(a^{'}_{j} + M - a^{'}_{j - 1})\; \mathrm{mod}\; M$ のように求めていく
$\mathrm{min}(C_{i})$ を出力する

計算量は $O(n + m)$

公式解説

躓いた点

帰納的に求める発想が出なかった
境界条件の整理に失敗してWA大量作成

1/10: AtCoder Regular Contest 041 C - ウサギ跳び

供養

問題

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

解法

ウサギ $i = (x_{i}, d_{i})$ について、右向きの一連のウサギ集合 $R_{R} = \lbrack \dots, i \mid \forall j \in R_{R}. d_{j} = ``\mathrm{R}'' \rbrack$ と左向きの一連のウサギ集合 $R_{L} = \lbrack i + 1, \dots \mid \forall j \in R_{L}. d_{j} = ``\mathrm{L}'' \rbrack$ は衝突するが、集合の要素が大きい方が動いて小さい方に衝突していく方が合計の移動回数が多くなる

$A = 0$ とする
$P_{R} = 0, N_{R} = 0, P_{L} = L + 1, N_{L} = 0, s = 1$ とする
から順番に見ていって、最初にとなったが現れたとき、とする
- $j = s$ のとき（最初から現れた場合）は $P_{R}, N_{R}$ の更新は不要
- 最後まで現れなかった場合は $j = N$ とし、 $P_{L}$ の更新は不要
以降最初にとなるを探し、とする
- 最後まで見つからなかった場合は $t = N$ とし、 $N_{L}$ の更新は不要
$S$ を以下のように決める
$$ S = \left \{ \begin{array}{} P_{R} + 1 & \mathrm{if}\; N_{R} \lt N_{L} \\ P_{L} & \mathrm{else} \end{array} \right. $$
$k = 1, \dots, N_{R}$ について、 $S - k - x_{j - k}$ を $A$ に加算していく
$k = 1, \dots, N_{L}$ について、 $x_{j - 1 + k} - S - k$ を $A$ に加算していく
$P_{R} = 0, N_{R} = 0, P_{L} = L + 1, N_{L} = 0, s = t$ として $t = N$ となるまで3.以降を繰り返す
$A$ を出力する

計算量は $O(N)$

公式解説

躓いた点

$t$ を探すときにうっかり $P_{L}$ を更新してしまってWA

1/11: AtCoder Beginner Contest 107 D - Median of Medians

供養

問題

Difficulty: 2086 (記事作成時点)

解法

$M_{k} = | \lbrace m_{l, r} \mid m_{l, r} \le k \rbrace |$ について、 $\lfloor \frac{N(N + 1)}{4} \rfloor \lt M_{k}$ であるような最小の $k$ を求める

$i = 1, \dots, N$ について、 $b_{i}$ をある $k$ を用いて以下のように定める $$ b_{i} = \left \lbrace \begin{array}{} 1 & \mathrm{if}\; a_{i} \le k \\ -1 & \mathrm{else} \end{array} \right. $$
累積和をとする
- $B_{0} = 0$ である
- $m_{l, r} \le k$ となるためには $i = l, \dots, r$ について $| \lbrace a_{i} \mid a_{i} \le k \rbrace | \gt | k \lt \lbrace a_{i} \mid a_{i} \rbrace |$ であればよい
- $B_{l - 1} \lt B_{r}$ であれば $m_{l, r} \le k$ であることが言える
$i = 0, \dots, N$ について $\mathit{BIT} \lbrack i \rbrack = 0$ とする
について降順に安定ソートしたものの逆順に、を加算してからにする
- BITを使った転倒数を求めるアルゴリズム
- $M_{k} = \sum_{1 \le r \le N}| \lbrace B_{l} \mid B_{l} \lt B{r}\; (0 \le l \le r) \rbrace |$ を求めることになる
$k$ について二分探索し、 $\lfloor \frac{N(N + 1)}{4} \rfloor \lt M_{k}$ であるような最小の $k$ を出力する

計算量は $A = \mathrm{max}(a_{i})$ としたときに $O(N\mathrm{log}N\mathrm{log}A)$

公式解説

躓いた点

二部探索と区間和を使うアイディアはあったが、転倒数を求めるアルゴリズムが出てこなかった

1/12: AtCoder Beginner Contest 150 D - Semi Common Multiple

供養

問題

Difficulty: 1565 (記事作成時点)

解法

$a_{i}$ が偶数なので、 $X = a_{i} \times (p + 0.5) = \frac{a_{i}}{2} \times (2p + 1)$ と表現できる
$X$ はすべての $\frac{a_{i}}{2}$ の奇数倍である必要があるので、非負整数 $k_{i}, b_{i}$ を用いて $a_{i} = 2^{k_{i}} \times (2b_{i} + 1)$ としたとき、 $k_{i} \neq k_{j}$ であるような $i, j$ の組が1つでも存在するならば $X$ は存在しない
すべての $k_{i}$ が一致するとき、 $X$ は $\frac{a_{1}}{2}, \dots, \frac{a_{N}}{2}$ の最小公倍数を $\mathit{LCM}$ として、非負整数 $p$ を用いて $(2p + 1) \times \mathit{LCM}$ である

実装としては

$i = 1, \dots, N$ について $a_{i}$ を2で割り切れる回数を調べ、 $k_{i}$ とする
$i = 1, \dots, N$ について $k_{i} \neq k_{1}$ であるような $i$ があれば0を出力して終了
$\mathit{LCM} = a_{1}$ とする
についてと更新していく
- $\mathrm{GCD}(x, y)$ は $x$ と $y$ の最大公約数
$\lceil \frac{ \lfloor \frac{M}{LCM} \rfloor}{2} \rceil$ を出力する

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

公式解説

躓いた点

$\lbrace X \mid \forall k. \exists p. X = a_{k} \times (p + 0.5) \rbrace$ を求めるところを $\lbrace X \mid \exists k. \exists p. X = a_{k} \times (p + 0.5) \rbrace$ を求める問題と誤読していた

1/13: AtCoder Beginner Contest 150 F - Xor Shift

供養

問題

Difficulty: 2231 (記事作成時点)

解法

$a^{'}_{0}, \dots, a^{'}_{N - 1}$ と $b_{0}, \dots, b_{N - 1}$ が等しいという事は、 $a^{'}_{i} \oplus a^{'}_{i + 1\; \mathrm{mod}\; N}$ と $b_{i} \oplus b_{i + 1\; \mathrm{mod}\; N}$ が等しい
$a^{'}{i} = a_{i + k} \oplus x$ より、 $a^{'}_{i} \oplus a^{'}_{i + 1} = (a_{i + k\; \mathrm{mod}\; N} \oplus x) \oplus (a_{i + k + 1\; \mathrm{mod}\; N} \oplus x) = a_{i + k\; \mathrm{mod}\; N} \oplus a_{i + k + 1\; \mathrm{mod}\; N}$ なので、 $a_{k\; \mathrm{mod}\; N} \oplus a_{k + 1\; \mathrm{mod}\; N}, \dots, a_{k + N - 1\; \mathrm{mod}\; N} \oplus a_{k + N\; \mathrm{mod}\; N}$ が $b_{0} \oplus b_{1}, \dots, b_{N - 1} \oplus b_{0}$ と一致するような $k$ を選べばよい
$k$ が与えられたとき、 $x = a_{k} \oplus b_{0}$ で求められる
パターン一致探索なのでKMP法などで求められる

実装は

$i = 0, \dots, N - 1$ について、 $X = \lbrack x_{i} \mid x_{i} = a_{i} \oplus a_{i + 1\; \mathrm{mod}\; N} \rbrack, Y = \lbrack y_{i} \mid y_{i} = b_{i} \oplus b_{i + 1\; \mathrm{mod}\; N} \rbrack$ とする
を繰り返して長さの配列にする
- $X^{'} = \lbrack x_{0}, \dots, x_{N - 1}, x_{0}, \dots, x_{N - 2} \rbrack$ となる
$X^{'}$ から $Y$ のパターンを探すパターン一致探索をして、一致する先頭位置の集合を $K = \lbrack k_{i} \mid \forall 0 \le j \le N. x_{k_{i} + j} = y_{j} \rbrack$ とする
$k_{i} \in K$ について、 $x_{i} = a_{k_{i}} \oplus b_{0}$ として $(k_{i}, x_{i})$ を出力していく

計算量は $O(N)$

公式解説

躓いた点

隣の値とのXORの関係が保存されることに考えが及ばなかった

1/14: 第6回ドワンゴからの挑戦状予選 B - Fusing Slimes

供養

問題

Difficulty: 1686 (記事作成時点)

解法

$i = 2, \dots, N$ について、 $x_{i - 1}$ から $x_{i}$ までをスライム $i - k\; (1 \le k \le i - 1)$ が合体せずに通る確率を考える
スライム $i - k, \dots, i - 1$ のみに着目したとき、スライム $i - k$ が一番最後に動くとき、合体せずに通る
したがって確率は $\frac{1}{k}$
期待値 $E$ は $E = \sum_{2 \le i \le N}\sum_{1 \le k \le i - 1}\frac{1}{k}(x_{i} - x_{i - 1})$

実装は

$i = 1, \dots, N - 1$ について、 $d_{i} = x_{N} - x_{i}$ とする
$k = 1, \dots, N - 1$ について、 $F_{k} \equiv k!\; (\mathrm{mod}\; p), I_{k} \equiv k^{-1}\; (\mathrm{mod}\; p)$ を求めておく
$E = \sum_{1 \le k \le N - 1}\frac{d_{k}}{k} \equiv \sum_{1 \le k \le N - 1}d_{k} \times I_{k}$ を計算する
$$ \begin{align} \because \sum_{i = 2}^{N}\sum_{k = 1}^{i - 1}\frac{1}{k}(x_{i} - x_{i - 1}) &= \frac{1}{1}(x_{2} - x_{1}) + \dots + (\frac{1}{1} + \dots + \frac{1}{N - 1})(x_{N} - x_{N - 1}) \\ &= \frac{1}{1}(x_{2} - x{1} + \dots + x_{N} - x_{N - 1}) + \dots + \frac{1}{N - 1}(x_{N} - x_{N - 1}) \\ &= \frac{1}{1}(x_{N} - x_{1}) + \dots + \frac{1}{N - 1}(x_{N} - x_{N - 1}) \\ &= \sum_{k = 1}^{N - 1}\frac{x_{N} - x_{k}}{k} \end{align} $$
$E \times F_{N - 1}$ を出力する

計算量は $O(N)$

公式解説

躓いた点

コンテスト中はスライムごとの移動距離の期待値に拘泥して時間内に思いつかなかった

そのうち誰かの役に立つ

もしくは誰の役にも立たない

AtCoderチャレンジ供養会場(2020/01/08-2020/01/14)

1/8: AtCoder Beginner Contest 140 F - Many Slimes

問題

解法

躓いた点

1/9: AtCoder Regular Contest 077 E - guruguru

問題

解法

躓いた点

1/10: AtCoder Regular Contest 041 C - ウサギ跳び

問題

解法

躓いた点

1/11: AtCoder Beginner Contest 107 D - Median of Medians

問題

解法

躓いた点

1/12: AtCoder Beginner Contest 150 D - Semi Common Multiple

問題

解法

躓いた点

1/13: AtCoder Beginner Contest 150 F - Xor Shift

問題

解法

躓いた点

1/14: 第6回ドワンゴからの挑戦状予選 B - Fusing Slimes

問題

解法

躓いた点

1/8: AtCoder Beginner Contest 140 F - Many Slimes

問題

解法

躓いた点

1/9: AtCoder Regular Contest 077 E - guruguru

問題

解法

躓いた点

1/10: AtCoder Regular Contest 041 C - ウサギ跳び

問題

解法

躓いた点

1/11: AtCoder Beginner Contest 107 D - Median of Medians

問題

解法

躓いた点

1/12: AtCoder Beginner Contest 150 D - Semi Common Multiple

問題

解法

躓いた点

1/13: AtCoder Beginner Contest 150 F - Xor Shift

問題

解法

躓いた点

1/14: 第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes

問題

解法

躓いた点

1/14: 第6回ドワンゴからの挑戦状予選 B - Fusing Slimes