AtCoder Beginner Contest 210 感想

#総合結果
* [Score] 1500 pts
* [Time] 56:43 + <font color="red"> 05:00 $\times$ 1 </font> = 61:43
* [Ranking] 221 st [Rated内: 109 th]
* [Performance] <font color=#C0C000> 2142　</font>
* [Rating] <font color=#0000FF> 1916 </font> → <font color=#0000FF> 1941 </font> (+25)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:43|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc210/submissions/24276976)||
|<font color=#808080> B問題 </font>|200 pts|02:56|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc210/submissions/24279770)||
|<font color=#808080> C問題 </font>|300 pts|08:31|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc210/submissions/24289855)||
|<font color=#00C0C0> D問題 </font>|400 pts|48:05|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc210/submissions/24312025)|[■](https://atcoder.jp/contests/abc210/submissions/24331784)<br>辞書式小さい地点に限定|
|<font color=#0000FF> E問題 </font>|500 pts|<b>56:43</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc210/submissions/24314984)||
|<font color=#FF8000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>0 pts</b>|<b>56:43</b>|<b><font color="red"> 1 Penalty </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 19) </font> [Cabbages](https://atcoder.jp/contests/abc210/tasks/abc210_a)

問題文から, 素直に以下の整数を出力すれば良い.

$$\begin{cases} NX & (N \leq A) \\\\ AX+(N-A)Y & (N>A) \end{cases}$$

なお, 場合分けしなくても, $\min(N,A)X+\max(N-A,0)Y$ とでも表せる.

##<font color=#808080> B問題 (200pts, diff: 22) </font> [Bouzu Mekuri](https://atcoder.jp/contests/abc210/tasks/abc210_b)

文字列 $S$ を左から見ていき, 最初に現れる ${\tt 1}$ が $k$ 文字目 (1-index) だったとき, $k$ が奇数ならば, 髙橋君の負け, $k$ が偶数だったら青木君の負けである.

##<font color=#808080> C問題 (300pts, diff: 359) </font> [Colorful Candies](https://atcoder.jp/contests/abc210/tasks/abc210_c)

$R_i:=\\{i,i+1,\dots,i+K-1\\}$ とする. この $R_i$ は取るキャンディのうち一番左端が左から $i$ 番目のキャンディであるときに取る $K$ 個のキャンディ全体の集合である.

$R_i$ と $R_{i+1}$ の間の関係性について調べてみると,
$$R_{i+1}=(R_i \setminus \\{i\\}) \cup \\{i+K\\}$$

になる. これは, $R_i$ から $i$ を除き, $i+K$ を加えると $R_{i+1}$ になることを意味している. このことを参考にすると, 以下のような手順で答えができる.

* $D$ を $0$ で初期化した辞書 (連想配列) とする. この $D$ にはある区間におけるキャンディ $i$ の個数を記録させる.
* $i=1,2,\dots, K$ の順に　$D[c_i]$ を $1$ 増やす.
* $D$ の非ゼロ成分の個数を $Y_1$ とする (この $Y_1$ は $R_1$ におけるキャンディの種類数である).
* $i=1,2,\dots,N-K$ の順に以下を行う.
    * $Y_{i+1}=Y_i$ とする.
    * $D[c_i]$ を $1$ 減らす (キャンディ $i$ を取り除くことに対応する).
    * $D[c_i]=0$ ならば, $Y_{i+1}$ を $1$ 減らす (色 $c_i$ のキャンディがなくなることに対応する).
    * $D[c_{i+K}]$ を $1$ 増やす (キャンディ $i+K$ を加えることに対応する).
    * $D[c_{i+K}]=1$ ならば, $Y_{i+1}$ を $1$ 増やす (色 $c_{i+K}$ のキャンディが新たに加わることに対応する).
    * (この $Y_{i+1}$ は $R_{i+1}$ におけるキャンディの種類数になる)
* $\max(Y_1, \dots, Y_{N-K+1})$ が答えである.

計算量は $O(N)$ である.

##<font color=#00C0C0> D問題 (400pts, diff: 1507) </font> [National Railway](https://atcoder.jp/contests/abc210/tasks/abc210_d)
$f((i,j),(i',j')):=A_{i,j}+A_{i',j'}+C(|i-i'|+|j-j'|)$ とする. ここで, 絶対値が現れているので, $i-i', j-j'$ の正負で場合分けをする.

以下, $(a,b), (c,d)$ に対して, $(a,b) \sqsubset (c,d)$ を $(a,b)$ は $(c,d)$ より辞書式順序の意味で<b>真</b>に小さいとする. つまり,

$$(a,b) \sqsubset (c,d) \iff (a<c) {\rm ~or~} (a=c {\rm ~and~} b<d)$$

である.　

以降では, マス $(i,j)$ とマス $(i',j')$ に駅を建てると考え, 対称性から $(i',j') \sqsubset (i,j)$ としてもよく, 特に, $i' \leq i$ である. そして, マス $(i,j)$ を固定し, $(i',j') \sqsubset (i,j)$ の範囲で $(i', j')$ を動くことを考える.

* $j' \leq j$ のとき<br>

```math
\begin{align*}
f((i,j),(i',j'))
&=A_{i,j}+A_{i',j'}+C((i-i')+(j-j')) \\\\
&=A_{i,j}+C(i+j)+A_{i',j'}-C(i'+j')
\end{align*}
```

ここで, $(i,j)$ は固定していることから, $A_{i,j}+C(i+j)$ は定数と見なせることから, $A_{i',j'}-C(i'+j')$ の最小化を目指すことになる. よって, $P_{i',j'}:=A_{i',j'}-C(i'+j')$ とすると,

$$\min_{\substack{(i',j') \sqsubset (i,j) \\\\ j' \leq j}} f((i,j),(i',j'))=A_{i,j}+C(i+j)+\min_{\substack{(i',j') \sqsubset (i,j) \\\\ j' \leq j}} P_{i',j'}$$

が成り立つ.

ここで, $\min_{\substack{(i',j') \sqsubset (i,j) \\\\ j' \leq j}} P_{i',j'}$ について考察する. $L_{i,j}:=\min_{\substack{(i',j') \sqsubset (i,j) \\\\ j' \leq j}} P_{i',j'}$ とする. ここで, 最小値について, 以下の性質が成り立つ. ただし, $x,y,z$ を実数とする.

* $\min(x,y)=\min(y,x)$
* $\min(x,y,z)=\min(x,\min(y,z))=\min((x,y),z)$

及び, $U_{i,j}:=\\{(i',j') \mid (i',j') \sqsubset (i,j) \\}$ としたとき,

$$U_{i,j}=U_{i-1,j} \cup U_{i,j-1} \cup \\{(i,j)\\}$$

であることから, 

$$L_{i,j}=\min(L_{i-1,j}, L_{i,j-1}, P_{i,j})$$

である. よって, 上での $L_{i,j}$ を用いて,

$$\alpha_{i,j}:=\min_{\substack{(i',j') \sqsubset (i,j) \\\\ j' \leq j}} f((i,j),(i',j'))=A_{i,j}+C(i+j)+L_{i-1,j}$$

であることがわかった. 

ここで, $L_{i,j}$ を求める計算量について, 各 $P_{i,j}$ は $O(1)$ で求めることができ, $L_{i,j}$ の更新も $O(1)$ でできることから, $L_{i,j}$ の全ては $O(HW)$ で求めることができる.

* $j' \leq j$ のとき<br>上のときと同様にすると,

```math
\begin{align*}
f((i,j),(i',j'))
&=A_{i,j}+A_{i',j'}+C((i-i')+(j'-j)) \\\\
&=A_{i,j}+C(i-j)+A_{i',j'}-C(i'-j')
\end{align*}
``` 

である. よって, $j' \leq j$ のときと同様に, $\beta_{i,j}$ を求めることができる.

* $Q_{i',j'}:=A_{i',j'}-C(i'-j')$ 
* $K_{i,j}:=\min_{\substack{(i',j') \sqsubset (i,j) \\\\ j' \geq j}} Q_{i',j'}$
* (更新式): $K_{i,j}=\min(K_{i-1,j}, K_{i,j+1}, Q_{i,j})$
* $\beta_{i,j}:=A_{i,j}+C(i-j)+K_{i,j-1}$

このようにして求めた, $\alpha_{i,j}, \beta_{i,j}$ を用いて, 答えは
$$\min(\min_{i,j} \alpha_{i,j}, \min_{i,j} \beta_{i,j})$$
であり, 計算量は $O(HW)$ である.

---
### 補足

$L_{i,j}$ はマス $(i,j)$ よりも左上にある $(i',j')$ における $P_{i',j'}$ の最小値で, $K_{i,j}$ はマス $(i,j)$ よりも左下にある $(i',j')$ における $Q_{i',j'}$ の最小値である.

##<font color=#0000FF> E問題 (500pts, diff: 1618) </font> [Ring MST](https://atcoder.jp/contests/abc210/tasks/abc210_e)

この問題は, あるグラフが与えられるので, 最小全域木を求めよという問題である. 一般的な重み付きグラフ $G=(V,E,C:E \to \mathbb{R})$ における最小全域木は以下のようにして求めることができる (Kruskal).

* $T=(V, F)$ を頂点集合が $V$ の空グラフとする. つまり, $F=\emptyset$
* $E$ を $E=\\{e_1, \dots, e_m \\}$ とする. ただし, $C(e_1) \leq \dots \leq C(e_m)$ とする.
* $e=e_1, \dots, e_m$ の順に以下を実行する.
    * 辺 $e$ の2つの端点を $u,v$ としたとき, $T$ における $u,v$ が別の連結成分だった場合, $F$ に $e$ を加える.
    * $u,v$ が同じ連結成分だった場合, 何もしない.
* $T=(V,F)$ が最小全域木になる.

この Kruskal 法を参考にして, 解法を述べる.

$(a_1, c_1), \dots, (a_M, c_M)$ を $c_1 \leq \dots \leq c_M$ となるように並び替える.

ここで, 空グラフ $G=([\\![N]\\!], \emptyset)$ と $(a_1, c_1)$ における考察をする. $G$ において, サイクルを生み出さずに, $(a_1, c_1)$ をできるだけ行うと, どのようなことが起こるかを考える. すると, 操作後, 以下のような結論が得られる.

> $\gamma_1=\gcd(N,a_1)$ とすると, $G$ は $\gamma_1$ 個の連結成分からなり, 各連結成分は $N/\gamma_1$ 頂点の木になる.
> 例: $N=12, a_1=3$ のとき, $G$ にできるだけ $(a_1, c_1)$ を行うと, $G$ は $3=\gcd(3,12)$ 個の連結成分からなり, 各連結成分は頂点集合を $\\{0,3,6,9\\}, \\{1,4,7,10\\}, \\{2,5,8,11\\}$ とする $4(=12/3)$ 頂点の木である.

このとき, $(a_1, c_1)$ による寄与は各 $N/\gamma_1$ 頂点の木を生成するために, $N/\gamma_1-1$ 本の辺が必要なことに注意すると, 全部で $\gamma_1(N/\gamma_1-1)=N-\gamma_1$  本 [^e1] であることから, $c_1 (N-\gamma_1)$ である.

ここで, $(a_1, c_1)$ を終えた後の連結成分に着目すると, $N$ 頂点は頂点の番号を $\gamma_1$ で割った余りが等しい頂点同士が同じ連結成分にあり, 逆も成り立つ. このことから, 各連結成分を $0,1,\dots, \gamma_1$ に代表させると, この問題は $\gamma_1$ 頂点で操作が $(a_2,c_2), \dots, (a_M,c_M)$ の場合に帰着でき, 問題の"サイズ" が小さくなった.

これを $(a_2, c_2), \dots, (a_M, c_M)$ の場合について見ていき, 最後に帰着されたグラフの頂点数が $1$ ならば全域木であり, そうでなければ全域木ではない.

以下が擬似コードである.

* $(a_1, c_1), \dots, (a_M, c_M)$ を $c_i$ の昇順に並べる.
* $X \gets 0$
* $i=1, \dots, M$ の順に以下を実行する. 
    * $\gamma_i \gets \gcd(N,a_i)$
    * $X \gets X+c_i(X-\gamma_i)$
    * $N \gets \gamma_i$
* $N=1$ ならば, $X$ を出力, そうでなければ, $-1$ を出力.

計算量は, 最初のソートがボトルネックになり, $O(M \log M)$ である.

[^e1]: $N$ 頂点で $\gamma_1$ 個の連結成分がある森 (各連結成分が木) の辺の数が $N-\gamma_1$ であるという理由でも良い.

##<font color=#FF8000> F問題 (600pts, diff: 2632) </font>[Coprime Solitaire](https://atcoder.jp/contests/abc210/tasks/abc210_f)
(正解でき次第加筆予定) Key Word: 2-SAT

#感想

##反省点
<font color="red">WA</font> 理由
* <font color=#00C0C0>D 問題 </font> 1箇所 $W$ とすべきところを $H$ にしていた.