AtCoder Beginner Contest 191 感想

##総合結果
* [Score] 1600 pts
* [Time] 76:20+<font color="red"> 05:00 $\times$ 0 </font>=76:20
* [Ranking] 192 nd [Rated内: 71st]
* [Performance] <font color=#C0C000> 2278　</font>
* [Rating] <font color=#0000FF> 1847 </font> → <font color=#0000FF> 1899 </font> (+52)

##各問題ごとの詳細
|Question|Time/Result|Penalty|
|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|01:14|<font color="red">  </font>
|<font color=#808080> B問題 </font>|02:23|<font color="red">  </font>
|<font color=#008000> C問題 </font>|20:24|<font color="red">  </font>
|<font color=#0000FF> D問題 </font>|76:20|<font color="red">  </font>
|<font color=#00C0C0> E問題 </font>|35:37|<font color="red">  </font>
|<font color=#C0C000> F問題 </font>|<font color="red"> WA </font> <font color="red"> WA </font>|

##提出コード
|Question|During Contest|After Contest|
|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|[■](https://atcoder.jp/contests/abc191/submissions/19952567)||
|<font color=#808080> B問題 </font>|[■](https://atcoder.jp/contests/abc191/submissions/19953977)|[■](https://atcoder.jp/contests/abc191/submissions/20014543)|
|<font color=#008000> C問題 </font>|[■](https://atcoder.jp/contests/abc191/submissions/19971452)(辺はいくつ?)|[■](https://atcoder.jp/contests/abc191/submissions/20014202)(頂点はいくつ?)|
|<font color=#0000FF> D問題 </font>|[■](https://atcoder.jp/contests/abc191/submissions/19992678)|[■](https://atcoder.jp/contests/abc191/submissions/20017653)(高速化)|
|<font color=#00C0C0> E問題 </font>|[■](https://atcoder.jp/contests/abc191/submissions/19977631)||
|<font color=#C0C000> F問題 </font>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 25) </font> [Vanishing Pitch](https://atcoder.jp/contests/abc191/tasks/abc191_a)
高橋君が投げた魔球が消えるのは投げた位置から $VT$ m 以上 $VS$ m 以下の所なので, 青木君がボールを打てるための必要十分条件は
$$[D<VT ~または~ VS<D] \iff [(VT \leq D \leq VS) ではない]$$
である.

##<font color=#808080> B問題 (200pts, diff: 20) </font> [Remove It](https://atcoder.jp/contests/abc191/tasks/abc191_b)
実装問題である. 問題文のようにして実際に数列の各要素に対して, $X$ と等しくなければ新たな数列の後ろにその項をつけていくことを繰り返していけば良い.

##<font color=#008000> C問題 (300pts, diff: 1063) </font> [Digital Graffiti](https://atcoder.jp/contests/abc191/tasks/abc191_c)

与えられた図形を $A$ とする. ここで, $A$ が最小で $N$ 角形であることと, $A$ の辺が $N$ 本であることは必要十分である. よって, $A$ に何本の辺があるかを考える.[^C1]

横に伸びる辺に注目する. 縦に伸びる辺についても同様にして計算できる. ここで, 横に伸びる2つの辺上の2点について, その2点の $y$ 座標が異なっていたとき, この2つの点が乗っている2つの辺は必ず異なる.

$i=1, \dots, H-1, j=1, \dots, W$ に対して, マス $(i,j)$ とマス $(i+1,j)$ を共有する辺が $A$ の辺にとして含むかどうかという小問題を考える. この小問題の答えはマス $(i,j)$ とマス $(i+1,j)$ に塗られている色が異なるということが必要十分になる.

ここで, 長さ $W$ の列 $L^{(i)}=\left(L^{(i)}_j \right)\_{j=1}^W$ を
$$L^{(i)}_j=\begin{cases} 1 \& マス(i,j) とマス(i+1,j) を共有する辺がAの辺に含まれる\\\\
0 & マス(i,j) とマス(i+1,j) を共有する辺がAの辺に含まれない \end{cases}$$

と定める. この列において, $1$ が連続して現れる回数を$T_i$ とする. なお, この $T_i$ は今回の制約上, $L^{(i)}\_1=L^{(i)}\_W=0$ であることから, $L^{(i)}$ の長さ2の部分列で $(0,1)$ となるものの個数と同じである.

よって, $L$ の横に伸びる辺の本数は
$$\sum_{i=1}^{H-1} T_i$$
で求めることができた. 計算量は横,縦に伸びる辺の計算が共に $O(HW)$ であることから, 全体でも $O(HW)$ で計算できた.
[^C1]: 公式解説では, 頂点の個数に注目している. 

##<font color=#0000FF> D問題 (400pts, diff: 1953) </font> [Circle Lattice Points](https://atcoder.jp/contests/abc191/tasks/abc191_d)

中心 $(X,Y)$, 半径 $R$ の円盤を $D$ とする. $\pi_x:\mathbb{R}^2 \to \mathbb{R}$ を $x$ 軸への射影[^D1] とすると, $\pi_x(D)=[X-R, X+R]$ である. よって, 円盤 $D$ は $X-R \leq x \leq X+R$ の範囲にあることがわかる.

$x \in [X-R, X+R] \cap \mathbb{Z}$ を固定する. このとき, $y \in \mathbb{Z}$ に対して,
$$(x,y) \in D \iff (x-X)^2+(y-Y)^2 \leq R^2 \iff (y-Y)^2 \leq R^2-(x-X)^2$$
がである. ここで, 以下の事実が成り立つことがわかる.
$$s \leq s' \leq Y, (x,s) \in D \Rightarrow (x,s') \in D \\\\
Y \leq t' \leq t, (x,t) \in D \Rightarrow (x,t') \in D$$
このことから, $\pi_x^{-1}(\\{x\\})=\\{x\\} \times [\alpha_x, \beta_x]$ となる $\alpha_x,\beta_x \in \mathbb{R}$ が存在する. 従って, 格子点に制限すると, 存在するならば
$$\pi_x^{-1}(\\{x\\}) \cap \mathbb{Z}^2=\\{x\\} \times \\{n \in \mathbb{Z}|s_x \leq n \leq t_x\\}$$
となる整数 $s_x, t_x \in \mathbb{Z}$ が存在する.
この $s_x, t_x$ は上で述べた性質から二部探索によって求めることができる. よって, $x$ 座標が $x$ である格子点の個数を $A(x)$ とすると, 
$$A(x)=\begin{cases} t_x-s_x+1 & (x座標がxの格子点が存在する) \\\\
0 & (x座標がxの格子点が存在しない) \end{cases}$$
となる. よって, 求めるべき答えは
$$\sum_{x=-\infty}^{\infty} A(x)$$
である. ここで, $A(x)$ は有限個の $x$ を除いて $0$ になるので, 上の値は有限である.

さて, 今回の問題では $X,Y,R$ が小数点以下第4位まで与えられる. よって普通に扱うと小数を扱うことになる. しかし, 計算機上での小数の計算には2進法である. 我々が日常生活で用いているのは10進法である. よって, 我々が使っている10進法の値を計算機では正確に計算できないという問題が発生する. 実際にこの問題で何の注意もなく小数を扱うと不正解になる.

そこで, $X,Y,R$ が小数点以下第4位まで与えられるという制約から以下のような工夫をして整数上での計算にする. 整数上での加減乗と整数商については誤差が発生しない.

* 座標空間 $\mathbb{R}^2$ 上の全単射 $\varphi:\mathbb{R}^2 \to \mathbb{R}^2$ を $\varphi(x,y):=(10^4x,10^4y)$ とする.
*  $\varphi$ は全単射なので, $\varphi(\mathbb{R}^2)=\mathbb{R}^2$ が成り立つが, $\varphi(\mathbb{R}^2)$ 上での世界での問題として考える.
*  $a,b \in \mathbb{R}$ に対して, $(a,b) \in \mathbb{R}^2$ が格子点であることと, $\varphi(a,b) \in \varphi(\mathbb{R}^2)$ の $x,y$ 座標がともに $10^4$ の倍数であることは同値である. ここで, $\varphi(\mathbb{Z}^2)$ の各元を "($\varphi(\mathbb{R}^2)$ における)真の格子点" と呼ぶことにする. 
*  このとき, $\varphi(D)$ は中心 $(10^4X,10^4Y)$, 半径 $10^4 R$ の円盤になるが, この円盤は中心が真の格子点で, 半径が整数である.
*  この $\varphi(D)$ に対して, 真の格子点はいくつか? という問題を解く. ここで, $\alpha_x, \beta_x$ を通常の意味での整数に制限すると, 誤差が発生しない.

[^D1]: $(a, b) \in \mathbb{R}^2$ に対して, $\pi_x(a, b):=a$ とする. 


##<font color=#00C0C0> E問題 (500pts, diff: 1323) </font> [Come Back Quickly](https://atcoder.jp/contests/abc191/tasks/abc191_e)

与えられたグラフを頂点集合 $V$ が $V=\\{1, \dots, N\\}$ , 辺集合 $E$ が $E=\\{A_1 B_1, \dots, A_M B_M\\}$ であり, 各辺 $e \in E$ のコストが $C(e)$ であるグラフ $G=(V,E,C:E \to \mathbb{R})$ とする. このグラフ $G$ からグラフ $\overline{G}=(\overline{V}, \overline{E}, \overline{C}: \overline{E} \to \mathbb{R})$ を以下のようにして作る.[^E1]

$$\overline{V}:=V ~\amalg~ V' \quad (V':=\\{1', 2', \dots, N'\\}) \\\\
\overline{E}:=E ~\amalg~ E' \quad (E':=\\{A_k' B_k| k=1, \dots, M\\} \\\\
\overline{C} (uv):=\begin{cases} C(wv) & (u \in V' \Leftrightarrow \exists w \in V {\rm ~s.t.~} u=w' )\\\\ C(uv) & (u \in V) \end{cases}$$

実は各 $u=1, \dots, N$ に対して, グラフ $\overline{G}$ 上での 頂点 $u'$ から 頂点 $u$ への最短路の長さがそのまま求めるべき答えになる.

実際, グラフ $\overline{G}$ での作り方から, $u,v \in V$ に対して, 頂点 $u'$ から頂点 $v$ へ1回以上の移動を経て到達可能であることと, 頂点 $u$ から頂点 $v$ へ到達可能であることが必要十分条件であり, しかも 前者と後者での最短路の長さは等しくなる. また, $u,v \in V$ に対して, $G$ 上での辺を1本以上用いた $uv$ -Path と, $\overline{G}$ 上での $u'v$ -Path は1対1に対応する. よって, $\overline{G}$ 上での問題に帰着できた.

この解法によって, 計算量は各 $v \in V$ に対して $\overline{G}$ 上でのDijkstra法で $O((M+N) \log N)$ で計算できるので, 全体では $O(N(M+N) \log N)$ で計算できた.

[^E1]: $1', \dots, N'$ のように計算のために新たに加えた頂点を超頂点という.

##<font color=#C0C000> F問題 (600pts, diff: 2333) </font> [GCD or MIN](https://atcoder.jp/contests/abc191/tasks/abc191_f)
(2021/03/09 加筆)
まず, 操作を $N-1$ 回行ってどのような整数を作れるかを考える. すると, 整数 $m$ が作れることと, 以下は同値であることがわかる.
$$ m \leq \min A \land \left[\exists k \geq 1, \exists i_1, \dots, i_k \in \mathbb{N} {\rm ~s.t.~} 1 \leq i_1<\dots<i_k \leq N, m=\gcd(A_{i_1}, \dots, A_{i_k}) \right]$$

* 十分性
数学的帰納法で示す.
 * $N=1$ のときは制約外だが, 示したことが成り立っているとする.
 * $N$ 以下のときに成立するとする. $N+1$ のとき
 $(N-1)$ 回の操作のあと, 残った整数 (最後に操作する2つの整数) が $\alpha, \beta$ であるとする. このとき, $\alpha,\beta$ は帰納法の仮定から, $\alpha, \beta \leq \min A$ および,
 $$\begin{cases}
1 \leq i_1 < \dots < i_k \leq N,\quad \alpha=\gcd(A_{i_1}, \dots, A_{i_k}) \\\\
1 \leq j_1 < \dots < j_l \leq N,\quad \beta =\gcd(A_{j_1}, \dots, A_{j_l}) \\\\
\\{i_1, \dots, i_k\\} \cap \\{j_1, \dots, j_l\\}=\emptyset \\\\
\end{cases}$$
を満たす整数 $k, l$ と, $i_1, \dots, i_k, j_1, \dots, j_l$ が存在する. 最後の操作について, $\min$ を選んだとすると
$$m=\alpha=\gcd(A_{i_1}, \dots, A_{i_k}) \quad {\rm or}\quad m=\beta=\gcd(A_{j_1}, \dots, A_{j_l})$$
のうちの一方が成立し, $\gcd$ を選ぶと, $\gcd$ は結合則を満たすので,
$$m=\gcd(\alpha,\beta)=\gcd(A\_{i_1}, \dots, A\_{i_k}, A\_{j_1}, \dots, A\_{j_l})$$
となる.

 また, $m \leq \min(\alpha, \beta)$ についても, $A_t=\min A$ なる $t$ について, $A_t$ は $\alpha, \beta$ のうちのどちらか一方にのみに生成に寄与している. ここで, $\alpha$ に寄与しているとすると, 数学的帰納法の仮定から, $\alpha \leq A_t$ であり, $\min, \gcd$ のどちらの操作でも結果は引数の最小値以下になるという性質から,
$$m \leq \min (\alpha, \beta) \leq A_t=\min A$$
 となり, 所望の式が得られた.

* 必要性
まず, $k-1$ 回の操作で $A_{i_1}, \dots, A_{i_k}$ の最大公約数をとる. すると, 仮定からこの最大公約数は $m$ になる. ここで, $m \leq \min A$ という仮定から, $m$ と残りの $N-k+1$ 個の整数に対して, 最小値を取ると, $m \leq \min A$ より, $m$ が生き残る.

この必要十分条件から, 問題は $\min A$ 以下の正の整数について, $A$ のいくつかの項の最大公約数として実現可能なのはいくつか? という問題に帰着できた.

ここで, $\min A$ 以下の整数 $r$ が $A$ のいくつかの項の最大公約数として実現可能であることと, $A$ に $r$ の倍数が存在して, しかも $A$ にある $r$ の倍数<bf>全て</bf>の最大公約数が $r$ であることは必要十分条件である.

* 十分性
一般的に, 整数 $s, x_1, \dots, x_n$ に対して, $s=\gcd(x_1, \dots, x_n)$ ならば, $s|x_i~(i=1, \dots, n)$ が成り立つ. まず, $A$ の中に $r$ の倍数が存在しなければ, 今述べたことの対偶から, 最大公約数が $r$ になることはない. また, $A$ にある全ての最大公約数が $r$ の倍数ではない場合も同様の理由で, 最大公約数が $r$ になることはない.

* 必要性
$A$ にある $r$ の倍数全ての最大公約数が $r$ なので, これが条件を満たす $A$ からの抜き方である.

よって, $\min A$ 以下の整数それぞれに対して, その倍数である項全ての最大公約数を調べれば, その整数が実現可能か判定できる. しかし, この方法を愚直に実装してしまうと, 計算量が $O(N \min A \log \min A)$ となってしまい, 間に合わない. そこで,
$$A_i は r の倍数 \iff r は A_i の約数$$
という言い換えによって, 以下のように実装すれば良い.

* 長さ $\min A$ の列 $D=(D_i)\_{i=1}^{\min A}$ の各項を $0$ で初期化する.
* 各 $A_i$ の約数 $d_{i,1}, \dots, d_{i,q_i}$ 全てに対し, $D_{d_{i,j}}$ を $\gcd(D_{d_{i,j}}, A_i)$ で更新する.
* $i=1, \dots, \min A$ に対して, $D_i=i$ なる $i$ が実現可能な整数である.

なお, 実際に実装するには, $D$ を数列としてではなく, 辞書(連想配列) で実装することにより, 計算量を削減できる.

この実装方法において, $d(x)$ で $x$ 以下の正の整数の約数の個数の最大値とすると, 計算量は約数列挙が $O(N \sqrt{\max A})$, 配列操作が $O(N d(\max A))$, 最大公約数の計算が $O(N d(\max A) \log \max A)$, 実現可能判定が $O(N d(\max A))$ であり, 全体の計算量は $O(N(\sqrt{\max A}+d(\max A) \log \max A))$ となり, $d(\max A) \leq d(10^9)=1344$ となることから, 十分軽い実装をすれば実行時間制限に間に合う.

#感想
##総評
今回のコンテストは <font color=#008000> C問題 </font>, <font color=#0000FF> D問題 </font> において通常時より難しい問題が出題され, <font color=#00C0C0> E問題 </font> ではやや簡単な問題が出題されたことから, 全体のコンテストとしても立ち回りなどである意味で難しい回となった. その中でも苦戦しながらでも黄色パフォーマンスになったのは立ち回りがうまく行った証拠だと思う.

今回のコンテストで黄色まで残りレート101となり, いよいよABC卒業 (Unrated) が見えてきた. この勢いのまま到達したいと思う.

##良かった点
* 難易度が昇順になっていないという状況下で5完することができた.
* ペナルティーが多発した<font color=#008000> C問題 </font>, <font color=#0000FF> D問題 </font>を一発で通せた.

##反省点
* <font color=#0000FF> D問題 </font>でDecimalを多用して一度TLEコードになってしまった(提出はしてない).