AtCoder Beginer Contest 220 感想

#総合結果
* [Score] 1500 pts
* [Time] 44:37 + <font color="red"> 05:00 $\times$ 0 </font> = 44:37
* [Ranking] 805 th [Rated内: 622 nd]
* [Performance] <font color=#00C0C0> 1587　</font>
* [Rating] <font color=#0000FF> 1946 </font> → <font color=#0000FF> 1914 </font> (-32)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:08|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc220/submissions/26120171)||
|<font color=#808080> B問題 </font>|200 pts|02:47|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc220/submissions/26122962)||
|<font color=#808080> C問題 </font>|300 pts|05:49|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc220/submissions/26126794)||
|<font color=#804000> D問題 </font>|400 pts|09:45|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc220/submissions/26131241)||
|<font color=#00C0C0> E問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc220/submissions/26171326)|
|<font color=#00C0C0> F問題 </font>|500 pts|<b>44:37</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc220/submissions/26151996)||
|<font color=#FF8000> G問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#FF0000> H問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1500 pts</b>|<b>44:37</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの感想
##<font color=#808080> A問題 (100pts, diff: 14) </font> [Find Multiple](https://atcoder.jp/contests/abc220/tasks/abc220_a)
$A$ 以上 $B$ 以下の $C$ の倍数を見つけるためには, いくつかの方法がある.

* $C \left \lceil \dfrac{A}{C} \right \rceil=C \left \lfloor \dfrac{A+C-1}{C} \right \rfloor$ が $A$ 以上の最小の $C$ の倍数である.
* $C \left \lfloor \dfrac{B}{C} \right \rfloor$ が $B$ 以上の最大の $C$ の倍数である.
* $x=A,A+1, \dots, B$ それぞれが $C$ の倍数かどうかを判定する. 

##<font color=#808080> B問題 (200pts, diff: 58) </font> [Base K](https://atcoder.jp/contests/abc220/tasks/abc220_b)

$K$ 進表記で表された $x_0 \dots x_m$ が表す値 $X$ は以下のようにして求められる.

* $X \gets 0$
* $i=0,1, \dots, m$ の順に以下を実行する.
    * $X \gets LX+x_i$
* $X$ を出力する.

##<font color=#808080> C問題 (300pts, diff: 119) </font> [Long Sequence](https://atcoder.jp/contests/abc220/tasks/abc220_c)

数列 $B$ の連続する $N$ 項の和は, $\alpha:=\sum_{i=1}^N A_i$ であることから, $q:=\left \lfloor \dfrac{X}{\alpha} \right \rfloor$ とすると, 答え $K$ は $qN < K \leq (q+1)N$ を満たすことがわかる. よって, $N \leq 10^5$ なので, $\beta \gets q \alpha$ として, $\beta$ に $A_i$ を足しながら, $qN+i$ が答えかどうかを順々にみれば, 計算量 $O(N)$ で求められる.

##<font color=#804000> D問題 (400pts, diff: 644) </font> [FG operation](https://atcoder.jp/contests/abc220/tasks/abc220_d)

動的計画法で求める. ${\rm DP}[i][a]$ で, $i$ 回操作した結果, 先頭の項が $a$ であるような操作の数とする. このとき, ${\rm DP}[N-1][K]~(K=0, \dots, 9)$ が求めるべき解である.

* $i=0$ のとき, 操作はしないので, 結果は元の列に一致する. よって,

$${\rm DP}[0][a]=\begin{cases} 1 & (a=A_1) \\\\ 0 & (a \neq A_1) \end{cases}$$

* $1 \leq i \leq N-1$ のとき, $i-1$ 回の操作で, 先頭の項が $b$ になったとする. このとき,  操作 $F$ , 操作 $G$ それぞれを考えることにより,

$${\rm DP}[i][(b+A_{i+1}) \bmod{10}] \quad (\because F), \quad {\rm DP}[i][(bA_{i+1})] \bmod{10}] \quad (\because G)$$

に ${\rm DP}[i-1][b]$ を足すことになる.

この動的計画法により, 計算量 $O(N)$ で求めることができる.

##<font color=#00C0C0> E問題 (500pts, diff: 1593) </font> [Distance on Large Perfect Binary Tree](https://atcoder.jp/contests/abc220/tasks/abc220_e)

※制約上ありえないが, $D=0$ のときも言及する (答えは $2^N-1$ であるが) .

まず, $T_n$ で深さが $n$ の完全二分木とする. このとき, 以下のような特徴がある.

* $T_n$ にある深さ $k~(0 \leq k \leq n)$ の頂点のは $2^k$ 個ある.
* $T_n$ は2つの $T_{n-1}$ の根を共に新たな頂点で結んだ木である.

ここで, $T_{N-1}$ 上での2点間の距離の最大値は $2(N-1)$ なので, $2(N-1)<D$ のときは直ちに解答を $0$ と求められる. 以下 $2(N-1) \leq D$ とする.

全ての頂点対を最小共通先祖 (LCA) で場合分けする. このとき, 対称性から, ある深さ $k$ の頂点において, その頂点を根とする部分木に制限したときの距離 $D$ の点対の個数を $X_k$ とすると, 求めるべき答えは

$$\sum_{k=0}^{N-1} 2^k X_k$$

である. 以下, $X_k$ を求める.

$X_k$ は $T_{N-1-k}$ に同型である. 今, 最小共通先祖が根なので, 選べる頂点の対 $(u,v)$ は以下のうちのどれかが成立するような選ぶ方になる.

* $u,v$ のうち, 少なくとも一方が根
* 根が結ぶ2つの部分木をそれぞれ左, 右と呼ぶことにすると, $u$ は左, $v$ は右の頂点 (またはその逆).

場合分けする. ここで, $\mu:=N-1-k$ とし, $\mu$ は頂点が深さの最大値である.

* $u$ が根のとき, $0 \leq D \leq \mu$ ならば, $v$ として深さが $D$ となる頂点を選ぶことで最小共通先祖が根で, $\operatorname{dis}(u,v)=D$ になることができる. $\mu < D$ のときはこの条件下では$\operatorname{dis}(u,v)=D$ にすることができない. 深さ $D$ の頂点は $2^D$ 個あり, $v$ が根のときも合わせて, このパターンでは

$$\begin{cases} 1 & (D=0) \\\\ 2 \times 2^D & (1 \leq D \leq \mu) \\\\ 0 & (\mu < D) \end{cases}$$

となる.

* $u$ が右, $v$ が左のとき, $T_\mu$ における $u,v$ の深さの和と $\operatorname{dis}(u,v)$ は一致する.
    * $u \neq v$ が確定しているので, このパターンで $D=0$ とはならない.
    * $1 \leq D \leq \mu$ のとき, $u,v$ の深さの組として可能なのは, $(1,D-1), \dots, (D-1, 1)$ の $D-1$ 通りである.
    * $\mu < D \leq 2\mu$ のとき, $u,v$ の深さの組として可能なのは, $(D-\mu,\mu), \dots, (\mu, D-\mu)$ の $2\mu-D+1$ 通りである.
    * $T_\mu$ における $u,v$ の深さは $\mu$ 以下なので, $2\mu <D$ とはなりえない.

ここで, 右左の区別があり, 2つの深さの組が $i,j$ となるような頂点の選び方は $2^{i-1} \times 2^{j-1}=2^{i+j-2}$ であり, 今 $i+j=D$ となるようにしているので, $2^{D-2}$ 通りである. 

このことから, $u,v$ の頂点の役割を交換することも考慮して, このパターンでは,

$$\begin{cases}  0 & (D=0) \\\\ 2 \times 2^D (D-1) & (0 < D \leq \mu) \\\\ 2 \times 2^{D-2} & (2 \mu-D+1) \\\\ 0 & (2 \mu <D) \end{cases}$$

である. 以上の2パターンを合わせることにより, $\mu_k:=N-1-k$ として,

$$X_k=\begin{cases} 1 & (D=0) \\\\ 2 \times (2^{D-2}(D-1)+2^D) & (0 < D \leq \mu) \\\\ 2 \times 2^{D-2}(2 \mu-D+1) & (\mu < D \leq 2\mu) \\\\ 0 & (2 \mu < D) \end{cases}$$

となる.

よって, $k=0,1,\dots, 2(N-1)$ に対して, $2^k$ を前計算すことにより, 各 $X_k$ を $O(1)$ で求められので, $\displaystyle \sum_{k=0}^{N-1} 2^k X_k$ を $O(N)$ で求めることができる.

##<font color=#00C0C0> F問題 (500pts, diff: 1304) </font>[Distance Sums 2](https://atcoder.jp/contests/abc220/tasks/abc220_f)

$X_i:=\sum_{j=1}^N \operatorname{dis}(i,j)$ とする. ここで, 与えられる木 $T$ を適当な頂点 ${\rm root}$ を根とする根付き木とみなす.

まず, $X_{\operatorname{root}}$ は以下のようにして求められる.

> 頂点 $v$ の $T$ における深さを $\operatorname{depth}\_T(v)$ とすると,
> $$\displaystyle X_{\rm root}=\sum_{v=1}^N \operatorname{depth}_T(v)$$
> である.

この $X_{\operatorname{root}}$ を利用して残りを求めることにする.

根でない頂点 $v$ の親を $w$ とし, $X_w$ が既に求まっているとする. このとき, $v$ の子孫の集合を $S_v$ とすると,

$$\operatorname{dis}(v,u)=\begin{cases} \operatorname{dis}(w,u)-1 & (u \in S_v) \\\\ \operatorname{dis}(w,u)+1 & (u \not \in S_v) \end{cases}$$

である. よって,

```math
\begin{align*}
X_v
&=\sum_{u=1}^N \operatorname{dis}(v,u) \\\\
&=\sum_{u \in S_v} (\operatorname{dis}(w,u)-1)+\sum_{u \not \in S_v} (\operatorname{dis}(w,u)+1) \\\\
&=\sum_{u=1}^N \operatorname{dis}(w,u)-|S_v|+(N-|S_v|) \\\\
&=X_w+N-2|S_v|
\end{align*} 
```

である. ここで, $|S_v|$ は頂点 $v$ の子孫の個数であるが, これは以下の漸化式を葉から計算することで求めることができる. ただし, ${\rm ch}(v)$ で頂点 $v$ の子とする.

$$|S_v|=\sum_{a \in {\rm ch}(v)} |S_a|+1$$

この $|S_v|$ の情報と, $X_{\rm root}$ から, 深さが小さい順に全ての $X_{\bullet}$ を求めることができる. 計算量は $O(N)$ である.


##<font color=#FF8000> G問題 (600pts, diff: 2439) </font>[Isosceles Trapezium](https://atcoder.jp/contests/abc220/tasks/abc220_g)
(正解でき次第加筆予定)

##<font color=#FF0000> H問題 (600pts, diff: 3047) </font>[Security Camera](https://atcoder.jp/contests/abc220/tasks/abc220_h)
(正解でき次第加筆予定)