AtCoder Beginner Contest 199 感想

#総合結果
* [Score] 1600 pts
* [Time] 97:26 + <font color="red"> 05:00 $\times$ 1 </font> = 102:26
* [Ranking] 270 th [Rated内: 111 th]
* [Performance] <font color=#C0C000> 2156 </font>
* [Rating] <font color=#0000FF> 1946 </font> → <font color=#0000FF> 1969 </font> (+23) (Highest!!)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|00:58|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc199/submissions/21991676)||
|<font color=#808080> B問題 </font>|200 pts|03:12|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc199/submissions/21997177)<br>(愚直解法)|[■](https://atcoder.jp/contests/abc199/submissions/22041281)<br>(高速解法)|
|<font color=#804000> C問題 </font>|300 pts|08:52|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc199/submissions/22003463)||
|<font color=#0000FF> D問題 </font>|400 pts|75:57|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc199/submissions/22028561)||
|<font color=#0000FF> E問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc199/submissions/22160915)<br>(最初の正解)<br>[■](https://atcoder.jp/contests/abc199/submissions/22160988)<br>(解説に合わせた実装)|
|<font color=#C0C000> F問題 </font>|600 pts|<b>97:26</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc199/submissions/22034518)||
|<b>Total</b>|<b>1600 pts</b>|<b>97:26</b>|<b><font color="red"> 1 Penalty </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 5) </font> [Square Inequality](https://atcoder.jp/contests/abc199/tasks/abc199_a)
愚直実装問題である. 3つの整数 $A,B,C$ が入力され, $A^2+B^2<C^2$ かどうかを判定し, その結果に対応する適当な文字列を出力すればよい. 以下は実際にコンテストに提出したコードである.

```python:A.py
A,B,C=map(int,input().split())
print("Yes" if A*A+B*B<C*C else "No")
```

##<font color=#808080> B問題 (200pts, diff: 37) </font> [Intersection](https://atcoder.jp/contests/abc199/tasks/abc199_b)
この問題には愚直解法と高速解法の2つがある.

### 愚直解法
$1 \leq A_i \leq B_i \leq 1000$ という制約から, 条件を満たしうる $x$ は $1 \leq x \leq 1000$ の高々 $1000$ 個である. また, 条件の個数 $N$ も $1 \leq N \leq 100$ という制約から, $X:=1000$ とし, $x=1, \dots, X$ それぞれについて条件を満たすかどうかを確かめると, 計算量 $O(XN)$ で計上できる.

### 高速解法
2つの整数 $s,t$ に対して, $[s,t]$ で $s$ 以上 $t$ 以下の整数全体を表すとする. このとき,

$$[s,t] \cap [s', t']=[\max (s,s'), \min (t,t')]$$

であるという性質を用いると,

$$[A_1, B_1] \cap \dots [A_N, B_N]=[\max A, \min B]$$

となり,
$$ \\# [\alpha, \beta]=\begin{cases}
\beta-\alpha+1 & (\alpha \leq \beta) \\\\
0 & (\alpha > \beta) \end{cases}$$
から求めることができる.

##<font color=#804000> C問題 (300pts, diff: 436) </font> [IPFL](https://atcoder.jp/contests/abc199/tasks/abc199_c)

$Q$ 個のクエリを愚直に行うと実行時間制限に間に合わない. そこで, クエリの性質を用いる. まず, 文字列 $S$ をリストと見なすと, $T=1$ の文字の入れ替えクエリは定数時間で可能である. $T=2$ のクエリは前半 $N$ 文字と後半 $N$ 文字を入れ替えるという操作はそのまま入れ替えるのではなく, 後の $T=1$ のクエリにおいて入力される $A,B$ から $N$ 文字ずれると考えれば良い.

##<font color=#0000FF> D問題 (400pts, diff: 1804) </font> [RGB Coloring 2](https://atcoder.jp/contests/abc199/tasks/abc199_d)

### 解法1
与えられたグラフの連結成分の個数を $K$ とする. 第 $i$ 連結成分における答えを $X_i$ とすると, 答えは総積 $X_1 \dots X_K$ である. 以下, グラフは連結であるとする.

連結な $N$ 頂点のグラフ $G$ には全域木 $T$ が存在し, この $T$ を適当な頂点を根とした根付き木とする. まず, $T$ における彩色を考える. 深さが小さい順に彩色する. 根は任意の色に彩色できる. 根以外の頂点に彩色可能なのは自分の親の彩色以外の2色である. この事実から, $T$ の彩色は $3 \times 2^{N-1}$ である. この彩色がグラフ $G$ において条件を満たすかどうかは $O(M)$ 時間で判定可能である. よって, 全体で $O(2^N M)$ 時間で求めることができた.

なお, 実装において, 根の色を固定し, 最後にその固定を外すことより, 求めた答えを3倍することによって解決できる.

### 解法2
グラフ $G=(V=[\\![N]\\!], E)$ に対して, $R \subset V$ を赤色で塗る頂点全体の集合とする. このとき, $R$ を決めうち, 残りの頂点が緑色または青色の2色で頂点彩色可能か? という問題を解く.

まず, $G$ の $R$ によって誘導される部分グラフ $G[R]$ に辺が存在した場合, 赤に塗った頂点同士を結ぶ辺が存在するので, この時点で彩色不能である. 次に, $G[V \setminus R]$ が二部グラフであれば, 2色で頂点彩色可能であり, 二部グラフでなければ頂点彩色不可能である. $G[V \setminus R]$ が二部グラフであるとき, $G[V \setminus R]$ の連結成分の数を $C_R$ としたとき, $G[V \setminus R]$ への2色の頂点彩色の場合の数は, 各連結成分において2通りずつなので,  全体で $2^{C_R}$ である. このことから, 求めるべき解答は

$$\sum_{R \subset [\\![N]\\!]} \begin{cases} 2^{C_R} & (G[V \setminus R]: 二部グラフ) \\\\
0 & (G[V \setminus R]: 二部グラフではない) \end{cases}$$

である.

##<font color=#0000FF> E問題 (500pts, diff: 1814) </font> [Permutation](https://atcoder.jp/contests/abc199/tasks/abc199_e)
(2021/04/30 加筆)

各条件 $(X_i, Y_i, Z_i)$ について, 重要なのは先頭 $X_i$ 項にどのような要素があるかであり, 順番は重要ではない. このようなときは Bit-DP で求めるのが良い.

$S \subset [\\![N]\\!]$ に対して, ${\rm DP}[S]$ で先頭 $|S|$ 項が $S$ からなる順列のうち, $X_j \leq |S|$ を満たす全ての $j$ に関する条件 $(X_j, Y_j, Z_j)$ を満たすようなものの総数と定める.

集合属 $\mathcal{A} \subset \mathcal{P}(X)$ を
$$\mathcal{A}:=\\{S \subset [\\![N]\\!] \mid 1 \leq \forall \leq M; X_j \leq |S| \Rightarrow (X_j, Y_j, Z_j) を満たす \\}$$
と定める. このとき, 遷移は
$${\rm DP}[S]=\sum_{\substack{a \in S \\\\ S \setminus \\{a\\} \in \mathcal{A}}} {\rm DP}[S \setminus \\{a\\}]$$
であり, 自明な場合 ${\rm DP}[\emptyset]=1$ と合わせて計算量 $O(N 2^N)$ で求めることができる.

##<font color=#C0C000> F問題 (600pts, diff: 2065) </font>[Graph Smoothing](https://atcoder.jp/contests/abc199/tasks/abc199_f)

与えられたグラフを $G=(V,E)$ とする. $X_l(u)$ で $l$ 回の操作の後に頂点 $u$ に書かれている数の期待値とする. このとき, 求めるべき値は $X_K(u)$ である.

$X_l(u)$ への遷移を考える. 辺 $e=xy$ が選ばれたとき, $e$ が $x$ に接続されていないときは $A_u$ のまま, 接続されているときは $u=x$ とすると, $\frac{A_x+A_y}{2}$ である. ここで, 頂点 $u$ の次数を $d(u)$ とすると, $X_l(u)$ は,

$$X_l(u)=\left(1-\dfrac{d(u)}{M} \right) X_{l-1}(u)+\sum_{uy\in E} \dfrac{1}{M} \left(\dfrac{X_{l-1}(u)+X_{l-1}(y)}{2} \right)=\left(1-\dfrac{d(u)}{2M} \right) X_{l-1}(u)+\sum_{y \neq u} \dfrac{[uy \in E]}{2M} X_{l-1}(y)$$

である. ここで, 係数は $l$ に依っていないことに注意すると, ${\boldsymbol v}\_l=(X_l(1), \dots, X_l(N))^T$ とすると,
$${\boldsymbol v}\_l=M {\boldsymbol v}\_{l-1}, \quad M=[m\_{i,j}]$$
となることがわかる. ただし, $M$ は行列で, 第 $(i,j)$ 成分の $m_{i,j}$ は

$$m_{i,j}=\begin{cases} 1-\frac{d(i)}{2M} & (i=j) \\\\
\frac{[ij \in E]}{2M} & (i \neq j) \end{cases}$$

である. この式から, ${\boldsymbol v}\_K=M^K {\boldsymbol v}\_0$　となり, ${\boldsymbol v}\_0=(A_1, \dots, A_N)^T$ であり, $M^K$ は行列累乗における繰り返し2乗法を利用することにより, 計算量 $O(N^3 \log K)$ で求めることができる.

#感想

##総評
今回のコンテストでは<font color=#804000>C問題</font>までと<font color=#0000FF>D問題</font>からの難易度の差が大きく, <font color=#0000FF>青色コーダー</font>にはプレッシャーのかかる戦いであった.

##良かった点

* <font color=#C0C000>F問題</font>を20分強で正解できたこと.

##反省点

* <font color=#0000FF>D問題</font>が難しかったとはいえ, 時間をかけすぎ.
* <font color="red">WA</font>の理由
    * <font color=#0000FF>D問題</font>
        * BFSの際にQueueに入れる頂点の誤り

#<font color=#C0C000> 黄色 </font>になるために
次回のコンテストのPerformanceが <font color=#C0C000>2242</font> 以上ならば, <font color=#C0C000> 黄色 </font> 達成.