AtCoder Beginner Contest 209 感想

#総合結果
* [Score] 1000 pts
* [Time] 09:53 + <font color="red"> 05:00 $\times$ 0 </font> = 09:53
* [Ranking] 364 th [Rated内: 205 th]
* [Performance] <font color=#0000FF> 1961　</font>
* [Rating] <font color=#0000FF> 1911 </font> → <font color=#0000FF> 1916 </font> (+5)

##各問題ごとの詳細, 提出コード
|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/abc209/submissions/24102347)||
|<font color=#808080> B問題 </font>|200 pts|02:50|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc209/submissions/24102347)||
|<font color=#808080> C問題 </font>|300 pts|05:30|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc209/submissions/24102347)||
|<font color=#804000> D問題 </font>|400 pts|<b>09:53</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc209/submissions/24118067)||
|<font color=#C0C000> E問題 </font>|0 pts|--:--|<font color="red"> (3 Penalties) </font>||[■](https://atcoder.jp/contests/abc209/submissions/24188744)|
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1000 pts</b>|<b>09:53</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの感想
##<font color=#808080> A問題 (100pts, diff: 5) </font> [Counting](https://atcoder.jp/contests/abc209/tasks/abc209_a)

正解 $X$ は以下である.
$$X=\begin{cases} B-A+1 & (A \leq B) \\\\ 0 & ({\rm otherwise}) \end{cases}$$
ただし, 上のように条件分岐を行なわくても, $X=\max(0, B-A+1)$ である.

##<font color=#808080> B問題 (200pts, diff: 13) </font> [Can you buy them all?](https://atcoder.jp/contests/abc209/tasks/abc209_b)

$i$ 番目の商品の売値を $B_i$ とすると,
$$B_i=\begin{cases} A_i-1 & (i: 偶数) \\\\ A_i & (i: 奇数) \end{cases}$$
であり, $B_1+\dots+B_N \leq X$ かどうかを判定すれば良い.

なお, $1, \dots, N$ の中にある偶数は $\lfloor N/2 \rfloor$ 個なので, 

$$B_1+\dots+B_N=A_1+\dots+A_N-\left \lfloor \dfrac{N}{2} \right \rfloor$$

である.

##<font color=#804000> C問題 (300pts, diff: 285) </font> [Not Equal](https://atcoder.jp/contests/abc204/tasks/abc204_c)

必要ならば, $C$ を昇順ソートすることによって, 以下を仮定しても良い.

$$C_1 \leq \dots \leq C_N$$

このとき, 以下がわかる.

* $A_1$ として可能なのは, $1, \dots, C_1$ の $C_1$ 個である.
* $A_2$ として可能なのは, $1, \dots, C_2$ の $A_1$ 以外の要素である. ここで, $A_1 \leq C_1 \leq C_2$ より, $1, \dots, C_2$ の中に $A_1$ はあることから, 候補は $\max(C_2-1, 0)$ 個である.
* $\vdots$
* $A_N$ として可能なのは, $1, \dots, C_N$ の $A_1, \dots, A_{N-1}$ 以外の要素である. ここで, 各 $i<N$ について, $A_i \leq C_i \leq C_N$ より, $1, \dots, C_2$ の中に $A_1, \dots, A_{N-1}$ はあり, これらは相異なることから, 候補は $\max(C_N-(N-1), 0)$ 個である.

以上から, 求めるべき答えは
$$\prod_{i=1}^N \max(C_i-(i-1),0)$$

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

##<font color=#804000> D問題 (400pts, diff: 686) </font> [Collision](https://atcoder.jp/contests/abc209/tasks/abc209_d)
与えられたグラフ $T$ は $N$ 頂点 $N-1$ 辺で, 連結なので, 木である. また, 各辺の長さを $1$ とする.

### 方針I (根付き木と距離に関する性質を利用)

$T$ を適当な頂点 ${\rm root}$ を根とする根付き木とする. ここで, 頂点 $v$ の深さを $\operatorname{depth}(v)$ と書き, 2つの頂点 $v,w$ の最小共通祖先を $\operatorname{lca}(v,w)$, $v,w$ 間の距離を $\operatorname{dist}(v,w)$ と書くことにすると, 以下が成り立つ.

> 性質A <br>$\operatorname{dist}(v,w)=\operatorname{depth}(v)+\operatorname{depth}(w)-2\operatorname{depth}(\operatorname{lca}(v,w))$

そして, この問題において $c_i, d_i$ -最短経路の一意性から, 以下のようにして正解が定まる.
$$\begin{cases} \operatorname{dist}(v,w): 奇数 & \iff 正解は {\tt Road} \\\\
\operatorname{dist}(v,w): 偶数 & \iff 正解は {\tt Town} \\\\ \end{cases}$$

なお, 性質A により, $\operatorname{dist}(v,w) \equiv \operatorname{depth}(v)+\operatorname{depth}(w) \pmod{2}$ なので, $\operatorname{dist}(v,w)$ の偶奇判定は, $\operatorname{depth}(v), \operatorname{depth}(w)$ の偶奇が一致するかどうかでも判定できる.

---
### 方針II (木にサイクルがないことを利用)

木について, 以下の性質 (人によっては定義) がある.

> 性質B: 木にはサイクルがない.

ここで, 木は二部グラフである. それには以下のような必要十分条件があるからである.

> 性質C: グラフが二部グラフであることと, グラフに長さ奇数の閉路が存在しないことは同値である.?

よって, 木 $T$ を二部グラフに分割できる. 以下, 部集合を $A, B$ とする. なお, 二分グラフの分け方において, 以下の性質がある.

> 性質D: 連結二分グラフ $G$ における部集合の分割は名付け方の違いを除いて一意に定まる.

<details><summary>性質D の証明</summary><div>
名付け方の違いを除いて一意でないとする. つまり, $G$ にある2つの頂点 $x,y$ において, ある分割 $A,B$ では同じ部集合に属するが, 別の分割 $A', B'$ では別の部集合に属するような分割が存在する. ここで, $G$ は連結なので, $x,y$ -Path が存在するが, 以下のことが従う.
* $x,y$ は分割 $A,B$ において同じ部集合に属するので, 長さ<b>偶数</b>の $x,y$ -Path $P$ が存在する.
* $x,y$ は分割 $A',B'$ において別の部集合に属するので, 長さ<b>奇数</b>の $x,y$ -Path $Q$ が存在する.

この2つの Path をつなげた $P \oplus Q$ は長さ奇数の閉歩道になる. ここで, 閉歩道はいくつかの Cycle に分割できるが, この Cycle の分割の中には少なくとも長さが奇数のものがあり, これは性質Bに矛盾する. よって, 連結二分グラフ $G$ における部集合の分割は名付け方の違いを除いて一意に定まる.
</div></details>

よって, 分割 $A, B$ を用いて, 以下のようにして解答することができる.

$$\begin{cases} v,w が異なる部集合に属する &&&&& \iff 正解は {\tt Road} \\\\
v,w が同じ部集合に属する &&&&& \iff 正解は {\tt Town} \\\\ \end{cases}$$

##<font color=#C0C000> E問題 (500pts, diff: 2153) </font> [Shiritori](https://atcoder.jp/contests/abc209/tasks/abc209_e)
(2021/07/13 加筆)

まず, 与えられたゲームの問題をグラフの問題に落とし込む. 集合 $\Sigma$ でアルファベット[^e1] とする. このとき, 有向グラフ $G=(\Sigma^3, A)$ を $\alpha, \beta \in \Sigma^3$ に対して,

$$\overrightarrow{\alpha \beta} \in A \iff \alpha で始まり, \beta で終わるような s_i が存在する.$$

とする. つまり, $\alpha$ で回ってきたときに, $\beta$ で回すことができるとき, そしてそのときに限り辺を作ることにする.

ここで, 各 $\gamma \in \Sigma^3$ に対して, $d^+(\gamma)$ でグラフ $D$ の頂点 $\gamma$ の出次数[^e2], $N^+(\gamma)$ で $\gamma$ の出近傍とする. このとき, 以下のようにして勝敗判定ができる. ただし, $W,L$ でそれぞれこの頂点から始めると, <b>先攻</b>必勝 (必敗) になる頂点全体の集合とする.

* $d^+(\gamma)=0$ ならば, $\gamma \in L$ である (ここから続かないので).
* 任意の $\varphi \in N^+(\gamma)$ で, $\varphi \in W$ ならば, $\gamma \in L$ である (どう動かしても, 次の先手 (=今の後手=相手) が必勝になるので).
* ある $\psi \in N^+(\gamma)$ が存在して, $\psi \in L$ ならば, $\gamma \in L$ ($\psi$ を選ぶことで, 相手に負ける手を回せるので).
* 上の3つを全て満たさない場合, $\gamma \not \in W \cup L$ である.

これで勝敗判定ができるようになった. これを求めるためには, 後退解析というアルゴリズムによって可能である.

https://qiita.com/drken/items/4e1bcf8413af16cb62da#4-%E5%BE%8C%E9%80%80%E8%A7%A3%E6%9E%90-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E5%BC%95%E3%81%8D%E5%88%86%E3%81%91%E3%81%AE%E3%81%82%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0

この問題においては以下のようになる. ただし, $N^-(\gamma)$ で $\gamma$ 入近傍とする.

* (初期設定) Queue $Q$ を $Q=(\gamma \in \Sigma^3 \mid d^+(\gamma)=0)$ とする (この $Q$ は $\gamma \in W \cup L$ が確定した頂点を収納していく).
* (初期設定) $W=\emptyset, L=\\{\gamma \in \Sigma^3 \mid d^+(\gamma)=0 \\}$ とする.
* Q が空で無い限り以下を実行する.
    * $Q$ から頂点 $\gamma$ を dequeue する.
    * $\gamma \in W$ であるとき.
        * 全ての $\psi \in N^-(\gamma)$ について以下を実行する.
            * $\psi \not \in W \cup L$ であり, この $\psi$ が $\gamma$ の最後に出近傍の確認だった場合, 以下を実行する.
                * $\psi \in L$ とし, $\psi$ を $Q$ に enqueue する.
    * $\gamma \in L$ であるとき.
        * 全ての $\varphi \in N^-(\gamma)$ について以下を実行する.
            * $\varphi \not \in W \cup L$ であるとき, 以下を実行する.
                * $\phi \in W$ とし, $\phi$ を $Q$ に enqueue する.

このようなアルゴリズムの動きは BFS に似ていることに注意すると, 計算量は $\sigma:=|\Sigma|(=52)$ とすると, $|A|=N$ なので, $O(\sigma^3+N)$ である.

最後に, 各 $s_i$ において, $s_i$ の後ろ $3$ 文字を $\beta_i$ としたとき,

* $\beta_i \in W$ ならば (相手が必勝なので), 後手必勝である.
* $\beta_i \in L$ ならば (相手が必敗なので), 後手必敗である.
* $\beta_i \not \in L \cup W$ ならば引き分けである.
 
[^e1]: 日常生活のアルファベットの意味でも意味が通るが, 計算機科学では記号の(有限)集合として扱われる.
[^e2]: 頂点 $\gamma$ から<b>出る</b>辺の本数

##<font color=#C0C000> F問題 (600pts, diff: 2307) </font>[Deforestation](https://atcoder.jp/contests/abc209/tasks/abc209_f)
(正解でき次第加筆予定)