AtCoder Beginner Contest 127
Updated:
- Review: 2020-05-16
- Review: 2020-07-04
Source codes
Solutions
A - Ferris Wheel
答えば以下で与えられる。
\[
\begin{cases}
0 & A \leq 5, \
B/2 & 6 \leq A \leq 12, \
B & A \geq 13.
\end{cases}
\]
B - Algae
漸化式にしたがって $10$ 回回す。
C - Prison
私の解答
$imos[i] = i$ 番目の鍵で開けることのできるゲートの個数
と定めると、これは累積和で求めることができる。具体的には $imos[i] = 0$ で初期化し、 $imos[L[i]] \mathbin{ {+} {+} }$, $imos[R[i] + 1] \mathbin{ {-} {-} }$ としたあと、 $i = 1, 2, \dots, M$ に対し $imos[i] {+=} imos[i - 1]$ とする。すると答えは次式で与えられる。 \[ \sharp \{ 1 \leq i \leq M \mid imos[i] = N \}. \]
解説放送の模範解答
最大値・最小値の定義より、答えの区間は、
\[ \bigcap _ {1 \leq i \leq M} [L _ i, R _ i] = \left[\max _ {1 \leq i \leq M} L _ i, \min _ {1 \leq i \leq M} R _ i \right] \]
であるから、 $\max(0, \min R _ i - \max L _ i + 1)$ が答えである。
ポイント
imos 法は overkill であった。
D - Integer Cards
私の解答
貪欲法で求めることができる。 $\{ A _ i \}$ は昇順であるとして良い。 $\{ (C _ j , B _ j) \}$ は降順であるとする。このとき今見ている $i, j$ を管理しておく。 $A _ i < C _ j$ ならば $A _ i \gets C _ j$, $B _ j \mathbin{ {-} {-} }$, $i \mathbin{ {+} {+} }$ とする。そうでないならば break; する。 $B _ j = 0$ ならば $j \mathbin{ {+} {+} }$ とする。答えは $\sum _ {1 \leq i \leq N} A[i]$ である。
解説放送の解答
最初に $A _ i$ たちが $1$ 枚ずつあり、値 $C _ j$ のカードが $B _ j$ 枚ずつあるとして、この中で $N$ 枚選んで最大値を達成するようにすると思って良い。これは貪欲に取れば良い。
ポイント
問題文の言い換えが鍵であった。これは難しい。
E - Cell Distance
私の解答
まず同じ問題を swap(M, N); して解くことにより 1 次元の問題に帰着できる。以下では $x$ 座標についてのみ考える。 $0$-indexed とする。
座標 $i < j$ に対し、 $i$ と $j$ に駒が置かれる場合の数を求める。 $(i, j)$ の駒の置き方に $y$ 座標で $N^2$ 通りある。その他の駒の置き方は $NM - 2$ マスの中から $K - 2$ 個選ぶ場合の数だけあるので、答えは次式で与えられる。
\[
\begin{align}
A &= \sum _ {0 \leq i < j < M} (j - i) N^2 \begin{pmatrix} NM - 2 \\ K - 2 \end{pmatrix} \
&= N^2 \begin{pmatrix} NM - 2 \\ K - 2 \end{pmatrix} \sum _ {0 \leq i < j < M} (j - i) \
&= N^2 \begin{pmatrix} NM - 2 \\ K - 2 \end{pmatrix} \sum _ {0 \leq i < M} \frac{(M - i)(M - 1 - i)}{2}. \tag{D.1}
\end{align}
\]
最初の式で計算すると $O(N ^ 2 + M ^ 2)$ となる。これは TLE をする。一方で最後の式で計算すると $O(N + M)$ となる。これは間に合う。
さらに計算すると…
要するに (D.1) 式をさらに変形すればよろしい。
\[
\begin{align}
& (i - M)(i - M + 1) \\
= & \frac{1}{3} \left( (i - M)(i - M + 1)(i - M + 2) - (i - M - 1)(i - M)(i - M + 1) \right)
\end{align}
\]
であるから、
\[
\begin{align}
B = & \sum _ {i = 0}^ {M - 1} (i - M)(i - M + 1) \
= & \frac{1}{3} (M - 1 - M)(M - 1 - M + 1)(M - 1 - M + 2)
- \frac{1}{3} (- M - 1)(- M)(- M + 1) \
= & \frac{1}{3} (M + 1)M(M - 1).
\end{align}
\]
以上より、 (D.1) 式は次式に変形される。
\[
\begin{align}
A &= \frac{N^2}{2} \begin{pmatrix} NM - 2 \\ K - 2 \end{pmatrix} B \
&= \frac{N^2}{6} \begin{pmatrix} NM - 2 \\ K - 2 \end{pmatrix} (M - 1) M (M + 1).
\end{align}
\]
ポイント
割と高速に実装できた。
F - Absolute Minima
最小点の求め方
まず最小点は、 $a$ たちの中央値である。これははみ出しけずり論法で分かる。ただし中央値が $2$ つある場合は、それらを端点とする閉区間全体で $f$ は最小値をとる。
これを動的に求める方法は、 priority_queue を $2$ つ使うのが一般的である。
$L = $ 中央値の左半分を降順で持っておいた priority_queue,
$R = $ 中央値の右半分を昇順で持っておいた priority_queue
ここで重要なのは priority_queue を $2$ つ作ることだけでなく、 $a$ を $2$ 回追加する ことである。こうすることでかなりわかりやすくなる。どういうことかというと、追加して右半分と左半分が正しい順序で並んでいると仮定すると、 $L$ の top と $R$ の top が一致するときは中央値が $1$ つしかない場合に相当する。 $L$ の top $l$ と $R$ の top $r$ が一致しない場合は最小点は区間 $[l, r]$ の任意の点である(この場合規約により $l$ を出力する)。こう対応している。
最小値の求め方
まず $b$ の寄与は素直に $B$ に持っておくことにし、以下では無視する。 $a$ の寄与は $A$ に追加するとする。答えは $A + B$ を出力する。厳密には分けて管理する必要はないが、わかりやすさのためにこうする。
ここで $l \leq r$ は上の通りに定めておく。新しい $a$ について、以下の場合分けをする。
$a \in [l, r]$ の場合は、最小点は $a$ となり、最小値 $A$ には変化がない。 $a$ が新たな中央値となるからである。 $a$ で新たな最小値をとる。つまり $L, R \gets a$ と追加してよろしい。
$a \not \in [l, r]$ の場合は、 $a < l$ または $a > r$ である。まず $a < l$ の場合を考える。この場合は新しく最小値をとる点は $l$ である。ただし、実際は区間になっていて右端になっているかもしれない。しかし何れにしても $x = l$ で最小値をとるのは間違いがない。そして今回の $A$ への寄与は $\lvert l - a \rvert$ である。
次に $a > r$ の場合を考える。この場合同様に $x = r$ で最小値をとる。そして今回の増加の寄与は $\lvert r - a \rvert$ である。
まとめると以下の通りである。
- $a \in [l, r]$ の場合： $l = r = a$ となり、 $A$ はそのまま。
- $a < l$ の場合： $x = l$ で最小値をとり、 $A \mathbin{ {+} {=} } \lvert l - a \rvert$ となる。
- $a > r$ の場合： $x = r$ で最小値をとり、 $A \mathbin{ {+} {=} } \lvert r - a \rvert$ となる。
これらの場合分けをせず、同時に行うことが可能である。具体的には以下のようにする。まず $a \to L, R$ とする。 $l’ = L.top()$, $r’ = R.top()$ とする。このとき $l’ \leq r’$ が成立するならば、以上の場合分けのうち 1. が成立していることが逆算で言える。ゆえにこの場合は変化なしで良い。仮に $l’ > r’$ である場合は、 2. か 3. が起きている。 2. の場合 $l’ = l$, $r’ = a$ が成立する。 3. の場合 $r’ = r$, $l’ = a$ が成立する。しかしいずれの場合も $\lvert l’ - r’ \rvert$ が $A$ への増加の寄与である。さらにこれらを入れ替えれば、それだけで $L, R$ の整合性が保たれることも分かる。入れ替えたということは、つまり「正しい方」に $a$ を $2$ 回追加し、バランスをとったことに相当するからである(場合分けは省略)。つまり以下のようにまとめられる。
- $a \to L, R$ とする。 $l’ = L.top()$, $r’ = R.top()$ とする。 $A \mathbin{ {+} {=} } \lvert l’ - r’ \rvert$ とする。
- $l’ \leq r’$ の場合：そのまま。
- $l’ > r’$ の場合： $l’, r’$ を入れ替える(
swapはできないので愚直に取り出して入れ替える)。
以上で最小値も動的に管理できる。
計算量は $O(Q \log Q)$ である。
別解：最小値の求め方 (Segment Tree)
まず $a$ の座標圧縮 map を $M[a]$ とする。
$sum[i] = $ 今までの $a$ に対し、座標 $M[a]$ に $a$ を足した segment tree,
$cnt[i] = $ 今までの $a$ に対し、座標 $M[a]$ に $1$ を足した segment tree.
と定める。 merge では上の更新を行う。 flush では次式を出力する。 $p$ を中央値とすると、最小値は、 \[ p \times cnt(0, M[p]) - sum(0, M[p]) + sum(M[p] + 1, Size) - p \times cnt(M[p] + 1, Size). \] これは絶対値を外して和をとっただけである。
ポイント
まず、
- 中央値を動的に管理するには priority_queue を $2$ つ用意すればいい
のは定跡である。その上で発想の鍵となるのは
- priority_queue に同じ値を $2$ 個入れて swap して整合性をとる
ということである。このことに気がつくには、 \[ \left( \lvert x - a \rvert \right)’’ = 2 \delta _ a \text{ in } \mathcal{S}’(\mathbb{R}) \] の事実に目を向けると良い。これによって $2$ 個追加するという発想が得られる。
Others
F が解けずに終わった。