AtCoder Beginner Contest 197（Sponsored by Panasonic）感想

#総合結果
* [Score] 1500 pts
* [Time] 43:44 + <font color="red"> 05:00 $\times$ 0 </font> = 43:44
* [Ranking] 411 st [Rated内: 236 th]
* [Performance] <font color=#0000FF> 1900　</font>
* [Rating] <font color=#0000FF> 1885 </font> → <font color=#0000FF> 1887 </font> (+2)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:03|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc197/submissions/21291120)||
|<font color=#808080> B問題 </font>|200 pts|05:07|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc197/submissions/21295727)||
|<font color=#008000> C問題 </font>|300 pts|11:15|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc197/submissions/21299051)||
|<font color=#008000> D問題 </font>|400 pts|18:27|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc197/submissions/21302105)||
|<font color=#00C0C0> E問題 </font>|500 pts|<b>43:44</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc197/submissions/21310122)||
|<font color=#0000FF> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc197/submissions/21333740)|
|<b>Total</b>|<b>1500 pts</b>|<b>43:44</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 6) </font> [Rotate](https://atcoder.jp/contests/abc197/tasks/abc197_a)
実装問題である. 問題文のように, $S$ の 1文字目, 2文字目, 3文字目を取得し, 2文字目, 3文字目, 1文字目の順にスペースをつけずに出力すれば良い.

##<font color=#808080> B問題 (200pts, diff: 96) </font> [Visibility](https://atcoder.jp/contests/abc197/tasks/abc197_b)
マス $(X,Y)$ から上下左右各向きにどの程度見えるかを ${\tt while}$ 文で愚直に探索すれば良い. ただし, マス $(X,Y)$ に関するカウントや, 範囲外参照に注意すること.

##<font color=#008000> C問題 (300pts, diff: 809) </font> [ORXOR](https://atcoder.jp/contests/abc197/tasks/abc197_c)
長さ $N$ の数列を1つ以上の空でない連続した区間に分ける方法を考える. これは $N$ 個の数列にある $N-1$ 個の間それぞれに境界線を入れるかどうかに対応し, 実際これらは1対1に対応する.

例えば, $A=(1,2,3,4,5,6)$ を $(1,2), (3,4,5), (6)$ については, $2$ と $3$, $5$ と $6$ の間それぞれに境界線を入れることに対応する.

この言い換えにより, 区間を分ける方法は $2^{N-1}$ であることがわかり, この区間の分け方は bit 全探索を用いることで, 計算量 $O(N 2^{N-1})=O(N 2^N)$ [^c1] で求めることが可能である.

[^c1]: $2^{N-1}=2^N \cdot \frac{1}{2}$ であることからこのようになる.

##<font color=#008000> D問題 (400pts, diff: 831) </font> [Opposite](https://atcoder.jp/contests/abc197/tasks/abc197_d)

以下の事実たちにより, 求めるべき $p_1$ がわかる.

* 正 $N$ 角形が外接する円が唯一存在する.
* 座標平面乗の円は中心の座標と半径から一意に定まる.

この事実たちから, 以下の様にして正解を導ける. なお, 座標と原点に関する位置ベクトルを同一視している.

* (外接円を求める) $p_0, p_{N/2}$ は正 $N$ 角形の対面同士の頂点なので, この2点の中点が外接円の中心になる. その中心を $m$ とすると, 半径 $r$ は $r=|m-p_0|$ で求めることができる.
* (偏角を求める) 外接円上にある点 $p_0$ について, 中心から $x$ 軸正の方向に伸ばした半直線に関する偏角 $\theta$ を求める.
* (角1つ分だけ移動させる) 正 $N$ 角形の各頂点と中心を結ぶ $N$ 本の線分は, 中心の角度を等しく分割することから, 上で求めた $\theta$ を用いて, 偏角が $\theta+\frac{2\pi}{N}$ に対応する頂点が答えである.

これらに出てきた文字は以下の様にして求めることができる.

* $m=\dfrac{1}{2}(p_0+p_{N/2})$
* $v=p_0-m$ として, $r=|v|$
* $v=(x,y)$ とすると, $\theta={\rm arctan}(x,y)$
* 正解の座標を $(X,Y)$ は, $m=(m_x,m_y)$ とすると, $X=m_x+r \cos \left(\theta+\frac{2\pi}{N} \right), Y=m_y+r \sin \left(\theta+\frac{2\pi}{N} \right)$ である.



##<font color=#00C0C0> E問題 (500pts, diff: 1379) </font> [Traveler](https://atcoder.jp/contests/abc197/tasks/abc197_e)

この問題を解くに当たって, 必要ならば色を書き換えることによって, 以下を仮定しても良い.

* 色 $1$, $\dots,$ 色 $M$ が少なくとも1つ存在する.
* 座標 $0$ には色 $0$, 色 $M+1$ の玉が両方置かれている.

このように仮定して問題を解く. ここで, 同じ色の玉をどの様にして取るかが問題になってくる.  結論から言うと, 最後に取るべき玉は, 各色について座標が最小か, 最大になっている玉である.

もし, 座標が最小でも最大でもない玉を最後に取ったとする. このとき, (最大)→(最小)→(最後) の順に取ったとすると, (最小) $\leq$ (最後) $\leq$ (最大) が成り立つので, (最大)→(元の最後)→(最小) としたほうが真に小さくなる. もう一方のパターンも同様である.

この証明において, 特に最初の座標を仮定してないことに注意せよ.

この仮定を元にして, 動的計画法で解く. $i=0, \dots, M+1$ に対して, ${\rm DP}[i][m]~(m \in \\{ {\rm max}, {\rm min}\\})$ を色 $i$ までの玉を全て取るとり方で, 最後に取る玉が色 $i$ のうち, 座標が (最大, 最小) であるもののなかでの最短時間とする.

このとき, 更新式は色 $i$ の玉の座標において, 最小を $A_i$, 最大を $B_i$ とすると,
$${\rm DP}[i][{\rm min}]=\min \Bigl({\rm DP}[i-1][{\rm min}]+|A_{i-1}-B_i|+|B_i-A_i|, {\rm DP}[i-1][{\rm max}]+|B_{i-1}-B_i|+|B_i-A_i| \Bigr)$$
$${\rm DP}[i][{\rm max}]=\min \Bigl({\rm DP}[i-1][{\rm min}]+|A_{i-1}-A_i|+|A_i-B_i|, {\rm DP}[i-1][{\rm max}]+|B_{i-1}-A_i|+|A_i-B_i| \Bigr)$$
となり, 求めるべき答えは, ${\rm DP}[M+1][{\rm min}]$ である.

自明な場合 ${\rm DP}[0][{\rm min}]={\rm DP}[0][{\rm max}]=0$ と合わせて計算量 $O(M+N)=O(N)$ [^e1] で求めることができる.

[^e1]: $M \leq N$ であるので, $O(M+N) \leq O(2N)=O(N)$ である.

##<font color=#0000FF> F問題 (600pts, diff: 1945) </font>[ Construct a Palindrome](https://atcoder.jp/contests/abc197/tasks/abc197_f)
(2021/04/03:加筆)

回分を考えるためには, 「両端から」または「中心から」考えれば良い. 今回は「両端から」考える.

ここで, 以下のように考える: 最初, 頂点 $1$ に赤いコメを, 頂点 $N$ に青いコマを置く. そして, この2つのコマを同じ文字が書かれた辺を使って隣接する頂点へ動かす操作を繰り返す. このとき, 2つのコマが同じ頂点上に置かれているならば, 赤いコマがたどった文字の履歴, 青いコマがたどった文字の履歴をそれぞれ $S,T$ とすると, $S \oplus \overline{T}$ [^f2] が回分になる. また, ある辺 $A_j B_j$ において, その辺に書かれている文字を $c$ とする. このとき, 赤いコマが頂点　$A_j$, 青いコマが $B_j$ にあるとき, $S,T$ を上と同様にしたとき, $S \oplus c \oplus \overline{T}$ は回分になっている.

よって, 与えられたグラフ $G$ の頂点集合を $V=[\\![N]\\!]$, 辺集合を $E=\\{A_1 B_1, \dots, A_M B_M\\}$ とする. このグラフから, 新たな無向グラフ $G'=(V', E')$ を作る. 頂点集合 $V'$ は $V'=V \times V$ とすればよい. $(u,v) \in V'$ において, $u$ は赤いコマの座標, $v$ は青いコマの座標に対応させる.

次に辺集合 $E'$ を考える. $(u,v)~(u',v') \in E'$ と 赤いコマを $u$ から $u'$ に, 青いコマを $v$ から $v'$ に移動可能であることと同値であるように $E'$ を構成したい. これは以下の様にして構成できる.
$$(u,v)~(u',v') \in E' \iff \exists i,j {\rm ~s.t.~} uu'=A_i B_i, vv'=A_j B_j, C_i=C_j$$

このように構成されたグラフにおいて, $|V'|=N^2$ であり, $|E'|$ についても, $|E'| \leq 4M^2$ [^f1] であり, $N,M \leq 1000$ という制約から, 陽にグラフを構築できる.

このグラフ $G'$ において, $X_{(u,v)}$ で頂点 $(1,N) \in V'$ と頂点 $(u,v)$ 間の距離とする. このとき, 条件を満たすようなパターンは2つある. ここで, 1回の操作で文字が2つ生成されることに注意すること.

* $u=v$ となるとき: このときに完成する回分の長さは $2X_{(u,v)}$ である.
* $uv \in E$ となるとき: このときに完成する回分の長さは, $uv$ 辺にある文字が中心になるので, $2X_{(u,v)}+1$ である.

以上から, 求めるべき答えは
$$\min \left(\min_{v \in V} 2 X_{(v,v)}, \min_{uv \in E} \biggl(\min \Bigl(2X_{(u,v)}+1, 2X_{(v,u)}+1 \Bigr) \biggr) \right)$$
である.　計算量は $O(N^2+M^2)$ である.

なお, 今回与えられるグラフ $G$ は無向グラフであるが,  $(u,v) \neq (v,u)$ であることから, 実装に注意しなければならない (特に, 辺 $A_j B_j$ において, 無向グラフにおいて $A_j B_j$ と $B_j A_j$ は同じであるが, 何箇所かは区別しなくてはならないところがある).

このように, グラフの問題でも, 与えられたグラフを使わずに, 別のグラフを自分で作らなくてはいけない場合がある.

[^f1]: $C_1=\dots=C_M$ が最大ケースであり, このとき 辺 $e=A_i B_i, e'=A_j B_j$ と辺 $(A_i,A_j)~(B_i, B_j)$ を対応付けることができる.
[^f2]: 文字列 $P,Q$ に対して, $\overline{Q}$ で $Q$ を反転させた文字列, $P \oplus Q$ で $P,Q$ をこの順で連結させた文字列とする.