AtCoder Beginner Contest 127

Updated:

AtCoder Beginner Contest 127

解説放送

  • 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$ である。

まとめると以下の通りである。

  1. $a \in [l, r]$ の場合: $l = r = a$ となり、 $A$ はそのまま。
  2. $a < l$ の場合: $x = l$ で最小値をとり、 $A \mathbin{ {+} {=} } \lvert l - a \rvert$ となる。
  3. $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 が解けずに終わった。