AtCoder Beginner Contest 194 感想

#総合結果
* [Score] 1500 pts
* [Time] 56:31 + <font color="red"> 05:00 $\times$ 3 </font> = 71:31
* [Ranking] 897 th [Rated内: 703 rd]
* [Performance] <font color=#00C0C0> 1541　</font>
* [Rating] <font color=#0000FF> 1918 </font> → <font color=#0000FF> 1885 </font> (-33 (歴代 Worst 2))

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|02:34|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc194/submissions/20689120)||
|<font color=#808080> B問題 </font>|200 pts|05:39|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc194/submissions/20693424)||
|<font color=#808080> C問題 </font>|300 pts|14:37|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc194/submissions/20700056)<br>(シグマの性質)|[■](https://atcoder.jp/contests/abc194/submissions/20739716)<br>(度数分布)|
|<font color=#008000> D問題 </font>|400 pts|24:01|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc194/submissions/20705108)||
|<font color=#008000> E問題 </font>|500 pts|<b>56:31</b>|<font color="red"> 3 Penalties </font>|[■](https://atcoder.jp/contests/abc194/submissions/20717946)<br>(集合)|[■](https://atcoder.jp/contests/abc194/submissions/20738445)<br>(Segment Tree)|
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc194/submissions/20739807)|
|<b>Total</b>|<b>1500 pts</b>|<b>56:31</b>|<b><font color="red"> 3 Penalties</font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 15) </font> [I Scream](https://atcoder.jp/contests/abc194/tasks/abc194_a)
字面に注意して, 問題文にかいてある定義と出力方法を読んで, 実装すれば良い. 以下は実際に提出したコードである.

```A.py
A,B=map(int,input().split())

if A+B>=15 and B>=8:
    print(1)
elif A+B>=10 and B>=3:
    print(2)
elif A+B>=3:
    print(3)
else:
    print(4)
```

ここで, ${\tt elif}$ の後に出てくる条件は, 前の ${\tt if}$ や, ${\tt elif}$ での条件が全て満たされないという前提があることに注意する.

##<font color=#808080> B問題 (200pts, diff: 104) </font> [Job Assignment](https://atcoder.jp/contests/abc194/tasks/abc194_b)
仕事の振り分け方は, 仕事 $A$ で $N$ 通り, 仕事 $B$ で $N$ 通りであることから, $N^2$ 通りであり, $N \leq 1000$ という制約から, 全ての仕事の振り分け方を調べれば良い.

##<font color=#808080> C問題 (300pts, diff: 386) </font> [Squared Error](https://atcoder.jp/contests/abc194/tasks/abc194_c)

$\displaystyle X:=\sum_{i=2}^N \sum_{j=1}^{i-1} (A_i-A_j)^2=\sum_{1 \leq j<i \leq N} (A_i-A_j)^2$ とする.
###解法1 シグマの性質を用いた変形をする.
$(A_i-A_j)^2=(A_j-A_i)^2$ であり, 対称性から
$$X=\dfrac{1}{2} \left(\sum_{i,j=1}^N (A_i-A_j)^2-\sum_{k=1}^N (A_k-A_k)^2 \right)$$
となる. ここで, 第2項は $(A_k-A_k)^2=0$ であることと, 第1項を展開することによって,

```math
\begin{align*}
X
&=\dfrac{1}{2} \left(\sum_{i,j=1}^N (A_i^2-2A_i A_j+A_j^2) \right) \\
&=\dfrac{1}{2} \left(\sum_{i,j=1}^N A_i^2-2\sum_{i,j=1}^N A_i A_j+\sum_{i,j=1}^N A_j^2 \right) \\
&=\dfrac{1}{2} \left(\sum_{j=1}^N \sum_{i=1}^N A_i^2-2 \left(\sum_{i=1}^N A_i \right) \left(\sum_{j=1}^N A_j \right)+\sum_{i=1}^N \sum_{j=1}^N A_j^2 \right) \\
&=\dfrac{1}{2} \left(N \sum_{l=1}^N A_l^2-2 \left(\sum_{i=1}^N A_i \right)^2 +N \sum_{l=1}^N A_l^2 \right) \\
&=\dfrac{1}{2} \left(2N \sum_{l=1}^N A_l^2-2 \left(\sum_{i=1}^N A_i \right)^2\right) \\
&=N \sum_{l=1}^N A_l^2-\left(\sum_{i=1}^N A_i \right)^2
\end{align*}
```

より, 数列 $A$ の和と平方和を求めることで, $O(N)$ で求めることができた.

###解法2 度数分布を利用する.

$\displaystyle |\\!|A|\\!|\_{\infty}:=\max\_{i=1, \dots, N} |A_i|$ とする. $-|\\!|A|\\!|\_{\infty} \leq k \leq |\\!|A|\\!|\_{\infty}$ に対して, $\chi_k$ で 数列 $A$ にある $k$ の個数とする. このとき,
$$X=\sum_{x=-|\\!|A|\\!|\_{\infty}}^{|\\!|A|\\!|\_{\infty}} \sum_{y=x+1}^{|\\!|A|\\!|\_{\infty}} \chi_x \chi_y (x-y)^2$$
となり, これは $O(N+|\\!|A|\\!|\_{\infty}^2)$ で求めることができる.

##<font color=#008000> D問題 (400pts, diff: 1078) </font> [Journey](https://atcoder.jp/contests/abc194/tasks/abc194_d)
以下の事実がわかる.

* 頂点 $v$ と頂点 $1$ が同じ連結成分にあるための必要十分条件は $v=1$ または, 少なくとも1回は $v$ が選ばれることである.
* 1回も選ばれていない頂点 $w$ (つまり, 頂点 $1$ と同じ連結成分にない頂点) は孤立点である.

この事実から, 各操作で増える頂点 $1$ の属する連結成分のサイズは操作前と同じが, 1増えるに限る.

よって, $X_i$ を頂点 $1$ の属する連結成分のサイズが $i$ であるとき, 残りの操作回数の期待値とする.

まず, ベースケースとして, $X_N=0$ である.

以下, 頂点 $1$ の属する連結成分の集合 $T$ と書くことにする.
$1 \leq k <N$ に対して, $|T|=k$ であるとき, 選んだ頂点 $w$ が, $w \in T$ であるとき, $|T|$ は $k$ のままで, $w \not \in T$ であるときは操作後, $|T|=k+1$ になる. ここで, 各頂点は一様に選ばれることから, $w \in T$ となる確率は $k/N$ で, $w \not \in T$ となる確率は $1-k/N$ である. よって, 
$$X_k=\dfrac{k}{N} X_k+\left(1-\dfrac{k}{N} \right) X_{k+1}+1$$
であり, この方程式を解くと, $X_k=X_{k+1}+\dfrac{N}{N-k}$ となる.

以上から, 求めるべき期待値は $X_1$ であり,

```math
\begin{align*}
X_1
&=X_2+\dfrac{N}{N-1} \\
&=X_3+\dfrac{N}{N-2}+\dfrac{N}{N-1} \\
&=\vdots \\
&=X_{N-1}+\dfrac{N}{N-(N-2)}+\dots+\dfrac{N}{N-2}+\dfrac{N}{N-1} \\
&=X_N+\dfrac{N}{N-(N-1)}+\dfrac{N}{N-(N-2)}+\dots+\dfrac{N}{N-(N-2)}+\dfrac{N}{N-(N-1)} \\
&=\dfrac{N}{N-(N-1)}+\dfrac{N}{N-(N-2)}+\dots+\dfrac{N}{N-2}+\dfrac{N}{N-1}\\
&=N \sum_{k=1}^{N-1} \dfrac{1}{N-k}
\end{align*}
```
であり, これは計算量 $O(N)$ で求めることができる.

##<font color=#008000> E問題 (500pts, diff: 1088) </font> [Mex Min](https://atcoder.jp/contests/abc194/tasks/abc194_e)

$N-M+1$ 個の $A$ の部分列 $B_i~(i=0,1, \dots, N-M)$ を $B_i:=(A_{i+1}, \dots, A_{i+M})$ とし, $E_i:={\rm mex} (A_{i+1}, \dots, A_{i+M})$ とする. ここで, 各数列 $B_i$ は $M$ 項なので, 最小除外数の性質から, $0 \leq \min (E_0, \dots, E_{M-N}) \leq M$ でなくてはならない.

ここで, $\min (E_0, \dots, E_{M-N})=a$ であることと, 以下2つが成り立つことは同値である.
$$\begin{cases} \forall i \in \\{0,1,\dots,M-N\\};~ a \leq E_i \\\\
\exists j \in \\{0,1, \dots, M-N \\} {\rm ~s.t.~} a=E_j \end{cases}$$

さて, $a$ は整数であることから, 以下とも同値である.
$$\begin{cases} \forall i \in \\{0,1,\dots,M-N\\};~ a \leq E_i \\\\
\exists j \in \\{0,1, \dots, M-N \\} {\rm ~s.t.~} a+1>E_j \end{cases}$$
ここで, $P(a):=\forall i \in \\{0,1,\dots,M-N\\};~ a \leq E_i$ とすると, 上で述べてきた条件は, $P(a)$ かつ $\lnot P(a+1)$ であることがわかる.

整数 $k$ に対して, $P(k)$ が保証されているとき, $P(k+1)$ であるかを調べたい.
$P(k)$ が保証されていることから, 任意の $i \in \\{0,1,\dots,M-N\\}$ で $k \leq E_i$ が成り立つ. よって, 最小除外数の定義から, $B_i$ には $k$ 個の整数 $0,1, \dots,k-1$ が含まれている. 従って, この状況下で, $P(k+1)$ を調べるためには, 任意の $i \in \\{0,1,\dots,M-N\\}$ に対して, $B_i$ に $k$ が含まれているかどうかを調べれば良い.

数列 $A$ の中に $k$ が $r_k$ 個あり, それは $A_{j_1}, \dots, A_{j_{r_k}}$ であるとする. このとき, 各 $A_{j_l}$ に対して, 数列 $A$ の第 $j_l$ 項目は, $B_{\max(0,j_l-M+1)}, \dots, B_{\min(j_l,N-M) }$ に現れる.

よって, $r_k$ の集合 $\\{\max(0,j_l-M+1), \dots, \min(j_l,N-M) \\}$ の和集合が $\\{0,1, \dots, N-M\\}$ に一致すれば, $P(k+1)$ も真であることがわかる.

この方法によって, 計算量はセグメントツリーを用いて計算すれば $O(N \log (N-M+1))=O(N \log N)$ で計算できる.

なお, 和集合を求める部分で, セグメントツリーを使わなくても計算量 $O(N \log N)$ で全てを覆うかどうかは判定できる.

##<font color=#C0C000> F問題 (600pts, diff: 2197) </font>[Digits Paradise in Hexadecimal](https://atcoder.jp/contests/abc194/tasks/abc194_f)

$\sigma:=16$ -進数表記での整数に対して, 上から $i$ 桁目の文字が表す整数のことを, 以下では上から $i$ 桁目の整数といい, それを $n_i$ で書く.

$N \leq 16^{2 \times 10^5}$ という制約から, 解法は桁DPに限られる.

ここで, $0$ について, leading-zero とそれ以外 $0$ では区別しなくてはならないことから, 桁DPの配列を以下の様に設定する.
$${\rm DP}[i][c][k]:=1 以上 N 以下の整数で状況が c (後述) であるものうち, \textrm{leading - zero} を除いてちょうど k種類の数字を用いているものの個数$$
なお, $c$ は以下の3つである.

* $F$: 上から $i$ 桁が完全に一致している.
* $T_0$ : 上から $i$ 桁までで, $N$ 以下であることが確定するが, $i$ 桁全てが $0$ であるとき.
* $T_1$ : 上から $i$ 桁までで, $N$ 以下であることが確定するし, しかも, $i$ 桁のうち, $0$ 以外が登場するとき.

例えば, $N=12345, i=3$ のとき, $123??$ は $F$ であり, $000??$ は $T_0$ であり, $001??$ などは $T_1$ である. これは一般的な桁DPにおける未満フラグの True を更に細分したものである.

まず, $i=1$ のときを考える. このとき, $N$ の先頭は $0$ でないという制約から, 以下のようになることがわかる.
$${\rm DP}[1][c][k]=\begin{cases} 1 & (c=F, k=1) \\\\
1 & (c=T_0, k=0)\\\\
n_1-1 & (c=T_1, k=1) \\\\
0 & ({\rm otherwise} \end{cases}$$

このようになる理由として, 1桁目が取りうる整数は $0,1, \dots, n_1$ の $n_1+1$ 通りであるが, $0$ とすると, $c=T_0, k=0$ になり, $n_1$ とすると, $c=F, k=1$ になり, それ以外では $c=T_1, k=1$ となるためである.

$i \geq 2$ とする. $i-1$ 桁目から, $i$ 桁目への推移を考える. 以下の表を用いて考える.

|$i-1$ \ $i$|$F$|$T_0$|$T_1$|
|:--:|:--:|:--:|:--:|
|$F$ (未満不確定)|(1)|(2)|(4)|
|$T_0$ (0オンリー)|$\times$|(3)|(5)|
|$T_1$ (未満,正が共に確定)|$\times$|$\times$|(6)|

$\times$ と付いているものについてはありえない遷移なので, 考えなくても良い.

* ${\rm DP}[i][F][k]$ について
 * (1) の遷移<br>
 $F$ であるから, 上から $i$ 桁は $n_1, \dots, n_i$ に確定する. $n_1 \neq 0$ という制約から, $n_1, \dots, n_i$ にある整数の種類数を $m_i$ とすると,
 $${\rm DP}[i][F][k]=[k=m_i]=\begin{cases} 1 & (k=m_i) \\\\ 0 & (k \neq m_i) \end{cases}$$
 であることがわかる.
* ${\rm DP}[i][T_0][k]$ について
 * (2) の遷移<br>
 $F$ から $T_0$ へどのようなときに遷移するかを考えると, 実は $i \geq 2$ では不可能なことがわかる. これは $n_1 \neq 0$ であることから, 上から $i-1$ 桁目まで $N$ と等しいとすると, $1$ 桁目が $n_1$ に等しいことになり, $0$ だけであるということに矛盾するからである.
 * (3) の遷移<br>
 $T_0$ は上から $i$ 桁目が $0$ であり, これは leading-zero になるので,
 $${\rm DP}[i][T_0][k]=[k=0]=\begin{cases} 1 & (k=0) \\\\ 0 & (k \neq 0) \end{cases}$$
 となる.
* ${\rm DP}[i][T_1][k]$ について
 * (4) の遷移<br>
 上から $i-1$ 桁までが $F$ で, 上から $i$ 桁までが $T_1$ になるということは, 上から $i-1$ 桁は $n_1, \dots, n_{i-1}$ で確定し, 上から $i$ 桁目は $1,\dots, n_i-1$ のどれかである. よって, $i-1$ 個の整数 $n_1, \dots, n_{i-1}$ の種類数を $t$, $p=0,1, \dots, n_i-1$ において, $i$ 個の整数 $n_1, \dots, n_{i-1}, p$ の種類数を $t_p$ とすると, ${\rm DP}[i][T_1][t_p]$ へ, ${\rm DP}[i-1][F][t]$ だけ寄与することがわかる.
 * (5) の遷移<br>
 $T_0$ の時点で $N$ 未満が確定しているので, $i$ 桁目で $T_1$ にするには $i$ 桁目が $1,2, \dots, \sigma-1$ のいずれかであればよい. また, $i$ 桁目を加えたことによって, leading-zero を除いた種類数は $1$ にしかなり得ないことから, ${\rm DP}[i][T_1][1]$ に $\sigma-1=15$ だけ寄与することがわかる.
 * (6) の遷移<br>
 $T_0$ の時点で $N$ 未満が確定していて, leading-zero の処理も終わっているので, $0,1, \dots, \sigma-1$ の全てに可能性がある. ここで, ${\rm DP}[i-1][T_0][k]$ の寄与先を考える. $0,1, \dots, \sigma-1$ のうち, もともとある $k$ 種類の整数を加えても種類数は増えず, もともとはなかった $N-k$ 種類の整数を加えると, 種類数は1 だけ増える. このことから, ${\rm DP}[i][T_1][k]$ へ $k {\rm DP}[i-1][T_1][k]$ だけ寄与し, ${\rm DP}[i][T_1][k+1]$ へ $(\sigma-k) {\rm DP}[i][T_1][k]$ だけ寄与することがわかった.

以上の遷移を $N$ の桁数を $d$ としたとき, $i=2, \dots, d$ と計算すると, 求めるべき答えは
$${\rm DP}[d][F][K]+{\rm DP}[d][T_1][K]$$
である. なお, ${\rm DP}[d][T_1][K]$ は $0$ における結果を表しているので, 除外しなければならない. 計算量は $O((\sigma+K) \log N)$ である.

#感想

##総評
今回は<font color=#008000>E問題</font> が非常に簡単だったので, <font color=#C0C000> F問題 </font> が解けないとなると, 速く解かなくては行けなかった. しかし, 思いついていたことも実装しなければそれは思いついていないことと同等であり, 正しい行いをしなければ<font color=#C0C000>黄色</font> になることはできないであろう.

##反省点
- 全体的に遅い
- <font color=#808080>C問題</font>, <font color=#008000>D問題</font>での計算, 立式ミス
- <font color=#FF0000>Penalties</font> の理由
    - <font color=#008000>E問題</font>
        - 1st: 答えが $N$ の時を無視 (RE) , Segment Treeの無駄 (TLE)
        - 2nd: 答えが $N$ の時を無視 (RE) , Segment Treeの無駄 (TLE)
        - 3rd: 答えが $N$ の時を無視 (WA)
- <font color=#008000>E問題</font> で正解になる軽量化を考えていたのにしなかった.