AtCoder Beginner Contest 215 解説

##各問題ごとの詳細, 提出コード
|Question|After Contest|
|:--:|:--:|
|<font color=#808080> A問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25250928)|
|<font color=#808080> B問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25250950)|
|<font color=#808080> C問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25250993)|
|<font color=#804000> D問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25251071)|
|<font color=#00C0C0> E問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25252038)|
|<font color=#0000FF> F問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25253127)|
|<font color=#C0C000> G問題 </font>|[■](https://atcoder.jp/contests/abc215/submissions/25260832)|
|<font color=#FF0000> H問題 </font>||

#問題ごとの感想
##<font color=#808080> A問題 (100pts, diff: 7) </font> [Your First Judge](https://atcoder.jp/contests/abc215/tasks/abc215_a)
与えられた文字列をなんかしらの変数に保存し, その変数が ${\tt Hello,World!}$ と一致するかどうかを判定し, それぞれの結果に対する文字列を出力すればよい.

##<font color=#808080> B問題 (200pts, diff: 68) </font> [log2(N)](https://atcoder.jp/contests/abc215/tasks/abc215_b)
$2^k$ は単調増加であり, $2^{60}>10^{18}$ であることから, 答えは $0 \leq k <60$ の範囲にある. このことから, $k=0,1,\dots,59$ の順に $2^k \leq N$ かどうかを判定し, 最後に $2^k \leq N$ を満たした $k$ の整数が答えである.

なお, $k=\lfloor \log_2 N \rfloor$ であるが, これをそのまま実装すると, 計算機による計算由来の誤差が発生し, 正解が得られない可能性がある.

##<font color=#808080> C問題 (300pts, diff: 178) </font> [One More aab aba baa](https://atcoder.jp/contests/abc215/tasks/abc215_c)
区別のつく $N$ 個の要素の並び替えは重複も区別すると, $N!$ 通りである. 今回の問題の制約では, $N \leq 8$ であり, $8!=40320$ であることから, 以下の方法でも十分に間に合う. ただし, $S$ の $i$ 文字目を $S[i]$ とする.

* 全ての $\sigma \in \mathfrak{S}_N$ に対して, 文字列 $S^\sigma:=S[\sigma(1)] \dots S[\sigma(N)]$ を生成する.
* $S^\sigma$ から重複を除き, その結果をリスト $L$ に保存する.
* $L$ を辞書式昇順に並べ, その結果の $K$ 番目を出力する.

##<font color=#804000> D問題 (400pts, diff: 736) </font> [Coprime 2](https://atcoder.jp/contests/abc215/tasks/abc215_d)
2つの整数 $x,y$ に対して, $\gcd(x,y)=1$ であることと, $x,y$ が互いに素であることは同値であるが, 実は以下のことが同値であることが成り立つ.

* $\gcd(x,y)=1$
* 全ての素数 $p$ について以下が成り立つ: $x,y$ が共に $p$ の倍数であることはない.

$1 \leq x \leq M$ とする. 各 $A_i$ の素因数分解を $A_i=p_{i,1}^{e_{i,1}} \times \dots \times p_{i,k_i}^{e_{i,k_i}}$ とする ($p_{i,j}$ は素数, $e_{i,j}>0$).

このとき, 各素数 $p_{i,j}$ について, 上での同値性から, $p_{i,j}$ の倍数であるような $x$ は条件を満たさないことがわかる. このことから, Eratosthenes の篩のようにして, $p_{i,j}$ の倍数をふるい落とすことを $i=1, \dots, N$ における $1 \leq j \leq k_i$ 全てに対して行えば良い.

ただし, 一度ある素因数 $p$ が出てきた後, 再び素因数 $p$ が登場した場合, 既に $p$ に対するふるい落としは終了しているので, ふるい落としを再び行わないようにしなければならない.

このことにより, 計算量は素因数分解のパートがボトルネックになり, $O(N \sqrt{\max A})$ で求まる.

(キラーケース: $N=10^5, M=10^5, A=(2,2,\dots)$ )

##<font color=#00C0C0> E問題 (500pts, diff: 1413) </font> [Chain Contestant](https://atcoder.jp/contests/abc215/tasks/abc215_e)
動的計画法で解く. ${\rm DP}[{\rm time}][{\rm participated}][{\rm last}]$ を

* ${\rm time}$ 回目のコンテスト終了時, 参加したことのあるコンテストの種類が ${\rm participated}$ であり, 最後に参加したコンテストが ${\rm last}$ であるような参加の方法の場合の数

とする.

ここで, ${\rm participated}$ は集合で表すとする. このとき, ${\rm DP}[i][T][x]$ への寄与は以下の様になる.

* $S[i] \neq x$ のとき
    * 参加しないという選択をした場合, ${\rm DP}[i][T][x]$ に ${\rm DP}[i-1][T][x]$ を加算する.
    * 参加するという選択をした場合, $y \in T, y \neq x$ なる全ての $y$ に対して, ${\rm DP}[i][T][x]$ に ${\rm DP}[i-1][T \setminus \\{x\\}][y]$ を加算する.
* $S[i]=x$ のとき
    * 参加するしないに関わらず, $T,x$ の状況は変わらないので, ${\rm DP}[i][T][x]$ に $2 {\rm DP}[i-1][T][x]$ を加算する.
* コンテスト初参加の場合を考慮して, ${\rm DP}[i][\\{x\\}][x]$ に $1$ を加算する.

##<font color=#0000FF> F問題 (500pts, diff: 1853) </font>[Dist Max 2](https://atcoder.jp/contests/abc215/tasks/abc215_f)
求めるべき値は「最小値の最大値」なので, 以下を満たす最大の $D$ が答えになる.

* 答えは $D$ 以上である.

この条件は $D$ について単調減少なので, 二分探索で求めることができる.

以下では, 答えが $D$ 以上であるかどうかを判定する.

```math
\begin{align*}
\max_{i,j} \min (|x_i-x_j|, |y_i-y_j|) \geq D
&\iff \exists i,j ~{\rm s.t.}~ \min (|x_i-x_j|, |y_i-y_j|) \geq D \\
&\iff \exists i,j ~{\rm s.t.}~ |x_i-x_j| \geq D \land|y_i-y_j| \geq D \cdots \circledast \\
\end{align*}
```

である. ここで, 点の添え次について, $x$ 座標の昇順になるように並べかえる. つまり, $x_1 \leq \dots \leq x_N$ とする. このとき,

$$\circledast \iff \exists i,j ~{\rm s.t.}~ i<j \land x_i \leq x_j-D \land |y_i-y_j| \geq D$$

である. 以下では $j=J$ として固定する. このとき, $x_1, \dots, x_N$ は昇順だったので, $x_I \leq x_J-D$ を見たす最大の $I$ に対して, 

* $y^{\max}_I:=\max(y_1, \dots, y_I)$
* $y^{\min}_I:=\min(y_1, \dots, y_I)$

としたとき, $\max(|y^{\max}_I-y_j|,|y^{\min}_I-y_j|) \geq D$ であるならば, 判定問題は肯定的解決をする.

逆に, $1 \leq J \leq N$ なる全ての $J$ に対して条件を満たさないならば, 判定問題は否定的解決になる.

ここで, $y^{\max}_I,y^{\min}_I$ は $I$ にのみ依存しているので, 前計算として累積最大値 (最小値) を計算しておくことにより, $I$ は尺取り法を用いて見つけることにより, 判定問題パートを計算量 $O(N)$ で求めることができる.

最後に, 二分探索を用いるための初期値 $L,R$ を決定する.

答えは明らかに $0$ 以上なので, $L=0$ とすればよい. また, $R$ についても,

$$\max_{i,j} \min (|x_i-x_j|, |y_i-y_j|) \leq \max_{i,j} \max (|x_i-x_j|, |y_i-y_j|) \leq \max (\max_i x_i-\min_j x_j, \max_i y_i-\min_j y_j)$$

であることから, 最右辺の値を $R$ に設定すれば良い.

このことから, 解答を $O(N \log R)$ で求めることができた.

##<font color=#C0C000> G問題 (600pts, diff: 2276) </font>[Colorful Candies 2](https://atcoder.jp/contests/abc215/tasks/abc215_g)

まず, $K$ を固定した場合の答え $E_K$ を求める. なお, 以下では $C=10^9$ とする.

確率変数 $X_i$ を飴を $K$ 個選んだときに色 $i$ が含まれていれば $1$, そうでなければ $0$ であるような確率変数とする. このとき, 確率変数 $V$ に対して, $E[V]$ で $V$ の期待値をあらわすことにすると,

$$E_K=E \left[\sum_{i=1}^C X_i \right]$$

であるが, 期待値の線形性から

$$E_K=\sum_{i=1}^C E[X_i]$$

になる. ここで, $X_i \in \\{0,1\\}$ であることから, $E[X_i]$ は $X_i=1$ であるような確率である. よって, $K$ 個選んだときに色 $i$ の飴が1個以上含まれている確率を求めれば良い.

「色 $i$ の飴が1個以上含まれている」の否定は「色 $i$ の飴が全く含まれていない」である. このことから, 色 $i$ の飴の個数を $m_i$ とすると,

$$E[X_i]=1-\dfrac{\binom{N-m_i}{K}}{\binom{N}{K}}$$

であることから, 

$$E_K=\sum_{i=1}^C \left(1-\dfrac{\binom{N-m_i}{K}}{\binom{N}{K}} \right)=\dfrac{1}{\binom{N}{K}} \sum_{i=1}^C \left(\binom{N}{K}-\binom{N-m_i}{K} \right)$$

である. よって, $m_i=0$ であるような $i$ についてはシグマ計算の対象にしないことにすると, $K$ を固定したときには $\Theta(N)$ で求めることができることが分かった.

しかし, これだと, $K=1, \dots, N$ 全てを求めるために $\Theta(N^2)$ だけかかってしまうが, シグマ計算において, $m_i$ にのみ依存していることに注意すると, $m_i=x$ であるような $i$ の個数を $a_x$ と書くことにすると,

$$E_K=\dfrac{1}{\binom{N}{K}} \sum_{x=1}^N a_x \left(\binom{N}{K}-\binom{N-x}{K} \right)$$

である. ここで, $a_x \neq 0$ であるような $x$ の個数について考える. $a_x \neq 0$ であるような $x$ を $x_1, \dots, x_M~(x_1<\dots<x_M)$ とすると, 

$$N=1 a_1+2 a_2+\dots+N a_N=x_1 a_{x_1}+\dots+x_M a_{x_M} \geq x_1+\dots+x_M \geq 1+\dots+M=O(M^2)$$

なので, $M=O(\sqrt{N})$ なので,

$$E_K=\dfrac{1}{\binom{N}{K}} \sum_{j=1}^M a_{x_j} \left(\binom{N}{K}-\binom{N-{x_j}}{K} \right) $$

を求めることで, $E_1, \dots, E_N$ を $O(NM)=O(N \sqrt{N})$ で求めることができた.

##<font color=#FF0000> H問題 (600pts, diff: 3101) </font>[Cabbage Master](https://atcoder.jp/contests/abc215/tasks/abc215_h)

(正解でき次第加筆予定)