AtCoder Beginner Contest 211 感想

#総合結果
* [Score] 1500 pts
* [Time] 51:06 + <font color="red"> 05:00 $\times$ 0 </font> = 51:06
* [Ranking] 214 th [Rated内: 87 th]
* [Performance] <font color=#C0C000> 2201　</font>
* [Rating] <font color=#0000FF> 1928 </font> → <font color=#0000FF> 1958 </font> (+30)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|00:56|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc211/submissions/24478874)||
|<font color=#808080> B問題 </font>|200 pts|01:57|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc211/submissions/24481579)||
|<font color=#804000> C問題 </font>|300 pts|07:16|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc211/submissions/24489929)||
|<font color=#804000> D問題 </font>|400 pts|14:40|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc211/submissions/24495344)||
|<font color=#0000FF> E問題 </font>|500 pts|<b>51:06</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc211/submissions/24506705)||
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1500 pts</b>|<b>51:06</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの感想
##<font color=#808080> A問題 (100pts, diff: 6) </font> [Blood Pressure](https://atcoder.jp/contests/abc211/tasks/abc211_a)
収縮期血圧 が $A$, 拡張期血圧 が $B$ のときの平均血圧 $C$ は
$$C=\dfrac{A-B}{3}+B$$
と与えられているので, この式の通りに求めれば良い. ただし, 整数同士の除算の型がどうなるかは各言語ごとに異なるので, 注意すること.

##<font color=#808080> B問題 (200pts, diff: 17) </font> [Cycle Hit](https://atcoder.jp/contests/abc211/tasks/abc211_b)
集合 $X$ を $X:=\\{S_1, S_2, S_3, S_4\\}$ とする. ここで, 制約より, $X$ の中に <code>H</code>, <code>2B</code>, <code>3B</code>, <code>HR</code> が一つずつあることと, $|X|=4$ は同値である.

##<font color=#804000> C問題 (300pts, diff: 559) </font> [chokudai](https://atcoder.jp/contests/abc211/tasks/abc211_c)
$N=|S|, T={\tt chokudai}$ とする. 動的計画法という手法で求める. $i=0,1,2,\dots, N$ と $j=0,1,\dots, 8$ に対して, ${\rm DP}[i,j]$ $S$ の $1$ 文字目から, $i$ 文字目までに制限したとき, ちょうど $j$ 文字だけ下線を引き, ${\tt chokudai}$ の先頭 $j$ 文字と一致する下線の引き方の数とする.

* ${\rm DP}[0,j]=\begin{cases} 1 & (j=0) \\\\ 0 & {\rm otherwise} \end{cases}$ である.
* $1 \leq i \leq N$ のとき<br>
    * $S$ の $i$ 文字目を下線を引かないとき: このパターンは $S$ の $i-1$ 文字目まで, 先頭 $j$ 文字一致の問題と等しい.
    * $S$ の $i$ 文字目に下線を引くとき: このパターンは, $S[j] \neq T[j]$ ならばこの瞬間不成立確定, $S[j]=T[j]$ ならば, $S$ の $i-1$ 文字目まで, 先頭 $j-1$ 文字目まで一致の問題と等しくなる.計算量は $O(|S||T|)=O(|S|) \quad (\because |T|=8)$ である

このことから,
$${\rm DP}[i,j]=\begin{cases} {\rm DP}[i-1,j] & (S[i] \neq T[j])  \\\\ {\rm DP}[i-1,j]+{\rm DP}[i-1,j-1] & (S[i]=T[j]) \end{cases}$$
である[^c1].

[^c1]: $T[0]$ は定義されていないが, 適当に 英小文字のどれとも一致しない文字 ${\tt *}$ を形式的に用いて, $T[0]={\tt *}$ とすればよい. 

##<font color=#804000> D問題 (400pts, diff: 755) </font> [Number of Shortest paths](https://atcoder.jp/contests/abc211/tasks/abc211_d)
与えられたグラフ $G=(V,E)$ に対し, 2つの頂点 $v,w \in V$ における最短距離を $\operatorname{dist}(u,v)$ とかく (ただし, $v,w$ -パスが存在しない場合, $\operatorname{dist}(u,v)=\infty$ とする). このとき, 頂点 $1$ から頂点 $N$ へのあるパスを $1=u_0,u_1,u_2, \dots, u_m=N$ としたとき, 以下の2つは同値である.

* $1=u_0, u_1, \dots, u_m=N$ は頂点 $1$ から頂点 $N$ への最短パスである.
* 任意の $i=0,1,\dots,m$ に対して, $\operatorname{dist}(1,u_i)=i$

よって, 動的計画法で, ${\rm DP}[v]$ を頂点 $1$ から頂点 $N$ への最短パスの数としたとき, 以下のような関係式が得られる. ただし, 各頂点 $v \in V$ に対して, $B(v) \subset V$ で頂点 $v$ の近傍全体の集合とする.

$${\rm DP}[v]=\begin{cases} 1 & (v=1) \\\\ \displaystyle \sum_{\substack{w \in B(v) \\\\ \operatorname{dist}(1,w)=\operatorname{dist}(1,v)-1}} {\rm DP}[w] & (v 
 \neq 1) \end{cases}$$

よって, 頂点 $v \in V$ に対して, $\operatorname{dist}(1,v)$ が小さい順に求めることによって, ${\rm DP}[N]$ が答えになる.

計算量は $\operatorname{dist}(1,v)$ を求めるための BFS がボトルネックになり, $O(N+M)$ になる.

##<font color=#0000FF> E問題 (500pts, diff: 1823) </font> [Red Polyomino](https://atcoder.jp/contests/abc211/tasks/abc211_e)

まず, 答えの上限を見つける. ここで, サンプル3に注目すると, このケースが最大ケースであることがわかり, このケースの答えが 64678 であることから, この問題の答えは "ある程度は小さい" ということがわかる. また, $K$ が大きくなると, 答えは指数的になる ( $K$ が $1$ 増えると, 答えは約 $3$ 倍になる) という感覚から, 以下のようなアルゴリズムで答えを出すことができる.

* 集合 $\mathcal{A}_1:=\\{\\{T\\} \mid T: 白マス \\}$ とする.
* $k=2,3,\dots, K$ に対して, 以下を実行する.
    * $\mathcal{A}_k:=\emptyset$ とする.
    * 全ての $A \in \mathcal{A}_{k-1}$ に対して, 以下を実行する.
        * 全ての白マス $X$ において, 以下を実行する.
            * $X$ の上のマス $U$ が存在して, $U \in A$ ならば, $A \cup \\{X\\}$ を $\mathcal{A}_k$ に加える.
            * $X$ の下のマス $D$ が存在して, $D \in A$ ならば, $A \cup \\{X\\}$ を $\mathcal{A}_k$ に加える.
            * $X$ の左のマス $L$ が存在して, $L \in A$ ならば, $A \cup \\{X\\}$ を $\mathcal{A}_k$ に加える.
            * $X$ の右のマス $R$ が存在して, $R \in A$ ならば, $A \cup \\{X\\}$ を $\mathcal{A}_k$ に加える.
* $|A_K|$ が答えである.

計算量は $|A_k|=O(N^2 3^k)$ であることから, $O(N^2 3^K)$ になる (意見募集).

##<font color=#C0C000> F問題 (600pts, diff: 2350) </font>[Rectilinear Polygons](https://atcoder.jp/contests/abc211/tasks/abc211_f)

(正解でき次第更新予定)