AtCoder Beginner Contest 206 (Sponsored by Panasonic)

#総合結果
* [Score] 1500 pts
* [Time] 26:33 + <font color="red"> 05:00 $\times$ 0 </font> = 26:33
* [Ranking] 212 nd [Rated内: 75 th]
* [Performance] <font color=#C0C000> 2240　</font>
* [Rating] <font color=#0000FF> 1861 </font> → <font color=#0000FF> 1905 </font> (+44)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:20|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc206/submissions/23569708)||
|<font color=#808080> B問題 </font>|200 pts|02:47|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc206/submissions/23572151)||
|<font color=#808080> C問題 </font>|300 pts|05:01|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc206/submissions/23577285)<br>(直接)|[■](https://atcoder.jp/contests/abc206/submissions/23622589)<br>(否定を求めて引く)|
|<font color=#008000> D問題 </font>|400 pts|08:11|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc206/submissions/23582865)||
|<font color=#0000FF> E問題 </font>|500 pts|<b>26:33</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc206/submissions/23597391)|[■](https://atcoder.jp/contests/abc206/submissions/23737912)|
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc206/submissions/23624586)|
|<b>Total</b>|<b>1500 pts</b>|<b>26:33</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 5) </font> [Maxi-Buying](https://atcoder.jp/contests/abc206/tasks/abc206_a)
$M=\lfloor 1.08 N\rfloor=\left \lfloor \dfrac{108}{100} N \right \rfloor$ としたとき, $M$ と $206$ の大小を比較すればよい.

なお, $N$ が整数であることから, $M$ と $206$ の大小は, $N$ と $191$ の大小に一致する.

##<font color=#808080> B問題 (200pts, diff: 14) </font> [Savings](https://atcoder.jp/contests/abc206/tasks/abc206_b)
$S_i=1+2+\dots+i$ としたとき, 初めて $S_i \geq N$ となるような $i$ を求めればよい.
$$S_1=1, \quad S_i=S_{i-1}+i$$
という関係式を用いれば, $S_1, \dots, S_M$ をまとめて $O(M)$ で求めることができる.

ここで, $S_i=\dfrac{i(i+1)}{2}$ より, $S_i=O(i^2)$ なので, 答えとなる $i$ を $I$ とすると, $I=O(\sqrt{N})$ である.

以上から, 求めるべき $I$ を $O(\sqrt{N})$ で求めることができる.

##<font color=#808080> C問題 (300pts, diff: 171) </font> [Swappable](https://atcoder.jp/contests/abc203/tasks/abc203_c)
求めるべき答えは,
$$(1 \leq i< j \leq N なる整数 (i,j) の選び方)-(1 \leq i < j \leq N, A_i=A_j なる整数 (i,j) の選び方)$$
であることがわかる.

* $1 \leq i< j \leq N$ なる整数 $(i,j)$ の選び方 は, $\binom{N}{2}=\frac{N(N-1)}{2}$ である.
* $1 \leq i < j \leq N, A_i=A_j$ なる整数 $(i,j)$ の選び方は, $A_i=k$ となる $i$ の個数を $\beta_k$ とすると, $k$ で一致してしまうのが $\binom{\beta_k}{2}=\frac{\beta_k(\beta_k-1)}{2}$ 通りなので, 考えうる $k$ 全てについて考慮して,
$$\sum_{k} \frac{\beta_k(\beta_k-1)}{2}$$
である.

よって, 求めるべき答えは,
$$\dfrac{N(N-1)}{2}-\sum_k \dfrac{\beta_k(\beta_k-1)}{2}$$
である. 各 $\beta_k$ を求めるために, 辞書を用いることで, 計算量 $O(N)$ で求めることができる.

##<font color=#008000> D問題 (400pts, diff: 879) </font> [KAIBUNsyo](https://atcoder.jp/contests/abc206/tasks/abc206_d)

$M=2 \times 10^5$ とする. 無向グラフ $G=([\\![M]\\!]:=\\{1, \dots, M\\}, E)$ を
$$E=\\{A_i A_{N+1-i} \mid i=1, \dots, N\\}$$
とする.

このとき, $A$ にある全ての $x$ を $y$ に変えるという操作はグラフ $G$ を縮約 $G/\\{x,y\\}$ に置き換えるという操作に対応している.

$A$ が回分であることと, $G$ が空グラフ[^d]であることは同値である.

$G$ の各連結成分 $C$ において, $C$ の頂点数を $k$ としたとき, $C$ に存在する部分木にの各辺に対して縮約を行うことによって, $k-1$ 回で空連結成分[^d]にすることができる. 逆に, $k-1$ 回未満で空連結成分にすることができない.

よって, $G$ の連結成分 $C_1, \dots, C_L$ の頂点数を $k_1, \dots, k_L$ としたとき, 答えは
$$\sum_{i=1}^L (k_i-1)=\sum_{i=1}^L k_i-L=M-L$$
である.

[^d]: 辺が存在しないという意味


##<font color=#0000FF> E問題 (500pts, diff: 1745) </font> [Divide Both](https://atcoder.jp/contests/abc206/tasks/abc206_e)

まず, 与えられた条件を言い換える. $g=\operatorname{gcd}(x,y)$ としたとき, 以下は同値である.
$$g \neq 1, \dfrac{x}{g} \neq 1, \dfrac{y}{g} \neq 1 \iff x,y は互いに素でなく, 一方は他方の倍数ではない$$
まず, $L \leq x,y \leq R$ なる整数の組で互いに素でない組の個数を求める.

$T_g$ で $L \leq x,y \leq R$ なる整数の組のうち, $g=\operatorname{gcd}(x,y)$ となる組の個数とする.

このとき, $g=\operatorname{gcd}(x,y)$ となるための必要十分条件は, $x,y$ が共に $g$ の倍数で, $g \geq \operatorname{gcd}(x,y)$ であることである. $L$ 以上 $R$ 以下のうち, $g$ の倍数である整数の個数は $\lfloor \frac{R}{g} \rfloor-\lfloor \frac{L-1}{g} \rfloor$ である. また, $x,y$ が $g$ の倍数のとき, 最大公約数は $g$ の倍数であることから,
$$T_g=\left(\left\lfloor \frac{R}{g} \right \rfloor-\left \lfloor \frac{L-1}{g} \right \rfloor \right)^2-\sum_{\substack{2 \leq k \\\\ kg \leq R}} T_{kg}$$
である. $T_1, \dots, T_R$ を求めるために, 各 $g$ での計算量が $O\left(\dfrac{R}{g} \right)$ であることに注意すると, 全体では $O(R \log R)$ で求まる.

よって, 互いに素であるような組の個数は $(R-L+1)^2-T_1$ であることがわかった.

次に, "一方は他方の倍数ではない" を処理する. $L \leq x,y \leq R$ で, $y$ が $x$ の倍数であるような組の個数は, $\lfloor \frac{R}{x} \rfloor-\lfloor \frac{L-1}{x} \rfloor$ である. $x$ と $y$ を入れ替えた場合も考慮する. そして, これにおけるダブルカウント ($x=y$ のとき) に注意する. また, $L=1$ のときは $x=1$ も範囲内だが, $x=1$ のときは $x,y$ は互いに素になることから, $L=1$ は計算してはいけない.

以上のことに注意すると, 答えは
$$(R-L+1)^2-T_1-\sum_{x=\max(2,L)}^R \left(2\left( \left\lfloor \frac{R}{g} \right \rfloor-\left \lfloor \frac{L-1}{g} \right \rfloor \right)-1 \right)$$
である.

##<font color=#C0C000> F問題 (600pts, diff: 2221) </font>[Interval Game 2](https://atcoder.jp/contests/abc206/tasks/abc206_f)
まず, このゲームについて, 以下の事がわかる.

* 運に左右されない
* ゲームに必要な全ての情報が公開されている.
* あり得る盤面の状況が有限である (高々 $2^N$ 通り).
*  一方が勝つと, もう一方は負ける.
* 1回の操作で選択可能な区間が1つ以上減る. つまり, ゲームはいつか必ず終わる.
*  盤面が同じならば, 操作の候補は操作をする人から影響を受けない.

このことから, このゲームは公平ゲームであることがわかる. 公平ゲームには Grundy 数という量を計算することで, 簡単に勝敗判定ができる.

以下, 区間 $[X,Y)$ 上のゲームを, 区間 $[X,Y)$ に完全に含まれる区間のみを選べる部分ゲームのことと定義する.

ここで, 区間 $[X,Y)$ 上のゲームで区間 $[a,b)$ が選べる時にこの区間を選ぶとどのようなことがおこるかを考える. このとき, ゲームは区間 $[X,a)$ 上のゲームと区間 $[b,Y)$ 上のゲームに分割され, この2つのゲームは互いに影響を与えない. このことから, $g(X,Y)$ で区間 $[X,Y)$ 上のゲームにおける Grundy 数としたとき, $g(X,Y)$ は
$$g(X,Y)=\operatorname{mex} \\{g(X,a) \oplus g(b,Y) ; [a,b) \in \mathcal{I}, X \leq a < b \leq Y \\}$$
である. ただし, $\mathcal{I}$ は最初に与えられている区間全体の集合, $a \oplus b$ で非負整数 $a,b$ の排他的論理和, $S \subsetneq \mathbb{N}$ に対して, $\operatorname{mex} S$ を
$$\operatorname{mex} S:=\min (\mathbb{N} \setminus S)$$
で定義する.

このとき, 制約から, スタート時は区間 $[0,100)$ 上のゲームであることから, $g(0,100)=0$ ならば, Bob の勝利, $g(0,100) \neq 0$ ならば, Alice の勝利である.

ここで, $g(X,Y)$ を求めるために, $(X,Y)$ として可能なのは高々 $100^2/2=5000$ 通りで, $|\mathcal{I}|=N$ であることから, $L=100$ として, 1テストケースあたり $O(L^2 N)$ , 1テストファイルあたり $O(TL^2N)$ で求めることができる.