AtCoder Beginner Contest 198 感想

#総合結果
* [Score] 1500 pts
* [Time] 40:02 + <font color="red"> 05:00 $\times$ 2 </font> = 50:02
* [Ranking] 193 rd [Rated内: 95 th]
* [Performance] <font color=#C0C000> 2146 </font>
* [Rating] <font color=#0000FF> 1887 </font> → <font color=#0000FF> 1915 </font> (+28)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|00:46|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc198/submissions/21634384)||
|<font color=#808080> B問題 </font>|200 pts|03:02|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc198/submissions/21638481)<br>(方針1)|[■](https://atcoder.jp/contests/abc198/submissions/21698849)<br>(方針2)|
|<font color=#804000> C問題 </font>|300 pts|<b>40:02</b>|<font color="red"> <font color="red"> 2 Penalties </font>  </font>|[■](https://atcoder.jp/contests/abc198/submissions/21667063)||
|<font color=#00C0C0> D問題 </font>|400 pts|24:49|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc198/submissions/21657812)|[■](https://atcoder.jp/contests/abc198/submissions/21701911)<br>(高速化)|
|<font color=#008000> E問題 </font>|500 pts|34:31|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc198/submissions/21664051)||
|<font color=#FF8000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1500 pts</b>|<b>40:02</b>|<b><font color="red"> 2 Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 10) </font>[Div](https://atcoder.jp/contests/abc198/tasks/abc198_a)

A君の分前を $x$ 個, B君の分前を $y$ 個とする. このとき, $x, y$ が満たすべき条件は,
$$x,y \in \mathbb{Z},\quad x,y \geq 1,\quad x+y=N$$
である. ここで, $y=N-x \geq 1$ から, $x$ の範囲は $1 \leq x \leq N-1$ である. これを満たす整数 $x$ 全てについて, $y=N-x$ とすると, $y \in \mathbb{Z}, y \geq 1, x+y=N$ とすべて満たす. よって, $(x,y)$ として可能なのは
$$(x,y)=(1, N-1), (2, N-2), \dots, (N-1, 1)$$
の $N-1$ 個である.

##<font color=#808080> B問題 (200pts, diff: 58) </font>[Palindrome with leading zeros](https://atcoder.jp/contests/abc198/tasks/abc198_b)

この問題には2つの方針がある.
### 方針1
$N=0$ のときはそのまま回分になるので除外する. 以下, $N \geq 1$ とする.

$N \leq 10^9$ より, $N$ は高々 $10$ 桁である. また, $M_k$ で $N$ の先頭に $k$ 個の $0$ を付け加えた文字列とする. このとき, 条件を満たす $k$ が存在するかどうかは, $M_0, \dots, M_9$ の $10$ 個の文字列について見れば良い.

$k \geq 10$ に対して, $M_k$ が回分にならないことを示す. もし, $M_k$ が回分だったとすると, 元の $N$ の末尾にも $k$ 個の $0$ が連続していることになる. 特に, $k \geq 10$ から, $N$ は $10^{10}$ の倍数ということになるが, 今 $N \geq 1$ という仮定と $N \leq 10^9$ という制約から, $1 \leq N \leq 10^9$ となるが, この中に $10^{10}$ の倍数は存在しないので, $M_k$ が回分になることはない.

この方針によって, $M_0, \dots, M_9$ が回分かどうかを判定すればよく, $N=0$ のときも $M_0$ の判定に含めることができる. これによって問題を解くことができた. 計算量は $O((\log N)^2)$ である.

### 方針2
以下, $N$ を文字列とみなす. このとき, $N$ が条件をみたすことと, 以下は同値である: $N$ の末尾に連続してる $0$ を全て取り除き, 残った文字列 $N^*$ が回分になっている[^b1].

* 十分条件: 先頭に $k$ 個の $0$ を付け加えたとする (操作後の文字列を $M$ とする). これは回分になるので, 元の $N$ の末尾にはちょうど $k$ 個の $0$ が連続している. $M$ の先頭と末尾には $k$ 個の $0$ があるので, 両端からその合計 $2k$ 個の $0$ を取り除いた文字列も回分になっており, この文字列は $N^*$ と一致する.

* 必要条件: $N$ の末尾に $k$ 個の $0$ が連続しているとする. このとき, $N$ の先頭に $k$ 個の $0$ を加えると, 十分条件の証明と同じ理由で回分になる.

よって, $N$ の末尾に連続してある $0$ を全て取り除き, 残った文字列が回分になるかどうかで判定できる. 計算量は $O(\log N)$ である.

[^b1]: 例: $12340000 \to 1234, \quad 1000000 \to  1,\quad 123456 \to 123456, \quad 1000100 \to 10001$

##<font color=#804000> C問題 (300pts, diff: 413) </font>[Compass Walking](https://atcoder.jp/contests/abc198/tasks/abc198_c)

必要ならば, 盤面を回転させることで, 目標が $x$ 軸上にあると仮定して良い. つまり, 目標の座標を $A=(X,0)$ とする.

以下, 場合分けして答える. ただし, 以下の事実を認める: 座標空間上の異なる2点 $P,Q$ 間のユークリッド距離を $d$ とする.  このとき, $d \leq 2r$ ならば, $P$ からの距離と $Q$ からの距離が共に $r$ であるような点 $R$ が存在する.

* $X=R$ のとき: 明らかに答えは $1$ である.
* $X>R$ のとき: 答えは $k:=\left \lceil \frac{X}{R} \right \rceil (\geq 2)$ である. 実際, $(k-1)R<X$ より $k$ 回未満では到達不能である. また, $k-2$ 回は $x$ 軸正の方向に $R$ だけ進みその結果を $B=((k-2)R,0)$ とする. ここで, $A$ と $B$ の距離は $R$ 以下なので, 上で述べた事実から, $A$ からの距離も $B$ からの距離も $R$ であるような点 $C$ が存在する. よって, 残りの $2$ 回を $B \to C \to A$ と移動することにより, $k$ 回での移動が達成できる.
* $X < R$ のとき: $X \neq R$ なので, $1$ 回では到達不能である. しかし, $X>R$ での最後の $2$ 回の方法と同様に移動することで $2$ 回で移動できる.

以上から, 求めるべき答えは
$$\begin{cases} 2 & (X < R) \\\\
1 & (X=R) \\\\
\left \lceil \frac{X}{R} \right \rceil & (X > R) \end{cases}$$
である.

ここで, 最初に回転をしたため, これを解消しなければならない. 元々の目標の点を $E=(X,Y)$ とするとき, 原点 $O$ との距離は $\sqrt{X^2+Y^2}$ である.　ここで, $\sqrt{X^2+Y^2}$ と $R$ の大小判定には少数誤差の問題が発生するが, 両者正であることから, 2乗して, $X^2+Y^2$ と $R^2$ の大小も元の大小と同じである. しかも両者とも整数なので, 誤差も発生しない.

また, $\left \lceil \frac{\sqrt{X^2+Y^2}}{R} \right \rceil$ についても, $k-1< \left \lceil \frac{\sqrt{X^2+Y^2}}{R} \right \rceil \leq k$ より, 全てを $2$ 乗して,
$$(k-1)^2 < \frac{\sqrt{X^2+Y^2}}{R} \leq k^2 \iff (R(k-1))^2 < X^2+Y^2 \leq (Rk)^2$$
となるような整数 $k$ を探せば良い. このとき, $X,Y \leq 10^5, 1 \leq R$ なので, $k \leq 2 \times 10^5$ より, $k=1, 2, \dots$ と順に判定していけばよい.

##<font color=#00C0C0> D問題 (400pts, diff: 1224) </font>[Send More Money](https://atcoder.jp/contests/abc198/tasks/abc198_d)

$X=\\{0, 1, \dots, 9\\}$ とし, $Y$ で $S_1, S_2, S_3$ に1回でも現れる英小文字全体の集合とする. このとき, 覆面算の結果になるような写像 $f:Y \to X$ を見つけなければならない.

ここで, 3つ目の条件から, $f$ は単射でなくてはならないので, もし $|Y|>|X|$ だと鳩ノ巣原理から単射を作れなくなるので,  $|Y| \geq 11$ だった場合はただちにNoとすればよい.

以下, $|Y| \leq 10$ とする. ここで, $f:Y \to X$ が単射となるような写像の作り方は, $\_{|Y|}{\rm P}\_{|X|}$ である. 特に, $\_{|Y|}{\rm P}_{|X|} \leq |Y|! \leq  10!=3628800$ であることに注意すると, 計算量は $|S|:=|S_1|+|S_2|+|S_3|$ とすると, $O(|S| |Y|!)$ で解くことができ, 実装に注意すれば実行制限時間に間に合うことができる.

##<font color=#008000> E問題 (500pts, diff: 1161) </font>[Unique Color](https://atcoder.jp/contests/abc198/tasks/abc198_e)

$T$ を頂点 $1$ を根とする根付き木とする. このとき, 頂点 $v$ がよい頂点であることの必要十分条件は, $v$ の自分自身を除く先祖のなかに頂点 $v$ と同じ色の頂点が存在しないことである.

これは DFS で判定することができる. フラグ専用の配列とメモ用の配列を用意し, DFS の際に頂点 $u$ に入るときに, 頂点 $u$ の色にメモがなかったらその色にメモをつけ, フラグを上げる. 逆に, 頂点 $u$ から出るときに, フラグが立っていたら, その色のメモを消す. この結果フラグが立った頂点が答えるべき頂点である.

##<font color=#FF8000> F問題 (600pts, diff: 2769) </font>[Cube](https://atcoder.jp/contests/abc198/tasks/abc198_f)

(正解でき次第加筆予定)