Atcoder Beginner Contest 207 感想

#総合結果
* [Score] 1000 pts
* [Time] 41:28 + <font color="red"> 05:00 $\times$ 0 </font> = 41:28
* [Ranking] 526 th [Rated内: 370 th]
* [Performance] <font color=#0000FF> 1758　</font>
* [Rating] <font color=#0000FF> 1905 </font> → <font color=#0000FF> 1891 </font> (-14)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|00:49|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc207/submissions/23754838)||
|<font color=#808080> B問題 </font>|200 pts|04:36|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc207/submissions/23760913)||
|<font color=#808080> C問題 </font>|300 pts|09:29|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc207/submissions/23765220)||
|<font color=#C0C000> D問題 </font>|400 pts|<b>41:28</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc207/submissions/23783483)<br>(※ $N=2$ のときに誤りがあり)||
|<font color=#0000FF> E問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc207/submissions/23804646)|
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>0 pts</b>|<b>41:28</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 6) </font> [Repression](https://atcoder.jp/contests/abc207/tasks/abc207_a)
出力すべき答えは, $\max(A+B, B+C, C+A)$ である. ちなみに,
$$\max(A+B, B+C, C+A)=\max((A+B+C)-C, (A+B+C)-A, (A+B+C)-B)=A+B+C-\min(A,B,C)$$
である.

##<font color=#808080> B問題 (200pts, diff: 98) </font> [Hydrate](https://atcoder.jp/contests/abc207/tasks/abc207_b)
$k$ 回操作したとき, 水色, 赤色のボールの個数は $A+kB, kC$ である. よって,
$$A+kB \leq D \cdot kC$$
となる最小の非負整数 $k^\*$ を求めなければならない. この不等式を変形させると $(CD-B)k \geq A$ となるが, $CD-B$ の正負に注意しなければならない.

* $CD-B>0$ のとき: $k \leq \dfrac{A}{CD-B}$ より, $k^\*=\left \lceil \dfrac{A}{CD-B} \right \rceil$  である.
* $CD-B=0$ のとき: 不等式は $0 \geq A$ であるが, $A \geq 1$ という制約から不等式を満たす非負整数 $k$ は存在しない.
* $CD-B<0$ のとき: $k \geq -\dfrac{A}{B-CD}$ となるが, $A \geq 1, B-CD>0$ より $-\dfrac{A}{B-CD}<0$ なので, この不等式を満たす非負整数 $k$ は存在しない.

以上から, 出力すべき答え $X$ は
$$X=\begin{cases} \left \lceil \dfrac{A}{CD-B} \right \rceil & (CD>B) \\\\ -1 & (CD \leq B) \end{cases} $$
である. ここで, $CD>B$ のとき, $CD-B$ は整数なので, $CD-B \geq 1$ より,
$$X=\left \lceil \dfrac{A}{CD-B} \right \rceil \leq A$$
なので, $k=0,1,2,\dots,A$ に対して不等式を満たすかどうかを判定しても良い.

なお, 十分大きな整数 $F$ に対して, $k=0,1,\dots,F$ の順に不等式を満たすかどうかを確認し, 満たすならば $k$ を出力して終了, $k=F$ でも満たさないならば $-1$ を出力して終了というプログラムでも正解する.

 
##<font color=#808080> C問題 (300pts, diff: 397) </font> [Many Segments](https://atcoder.jp/contests/abc207/tasks/abc207_c)

### 解法の準備
$x<y$ に対して, 以下が成立する.

* $[x,y]=[x,y]$
* $[x,y)=\bigcup_{\varepsilon'>0} [x,y-\varepsilon']$
* $(x,y]=\bigcup_{\varepsilon>0} [x+\varepsilon,y]$
* $(x,y)=\bigcup_{\varepsilon,\varepsilon'>0} [x+\varepsilon,y-\varepsilon']$

である. このとき, 共通部分をもつような2つの区間において, 開になっている部分について,  うまいこと $\varepsilon, \varepsilon'>0$ を選ぶことにより, 閉区間同士の共通部分の存在にもっていくことができる.

### ε, ε'の選び方
$\varepsilon, \varepsilon'>0$ をうまく選ぶ. この $\varepsilon, \varepsilon'$ はもしかしたら $x,y$ にも依る可能性もあるが, 今回 $x,y$ は整数という制約から, 実は $\varepsilon, \varepsilon'=0.1$ とすればよい (証明は略).

### 区間の比較
各区間において, 開となっている部分において $\pm 0.1$ にすることにより, 閉部分空間にとすることができたので, 最後は2つの区間 $[x,y], [x',y']$ に共通部分が存在するかどうかの判定だが, これは以下のようにしてできる.

$$[x,y] \cap [x', y'] \neq \emptyset \iff \max(x,x') \leq \min (y,y')$$

よって, $1 \leq i < j \leq N$ となる $(i,j)$ 全てに対して, 上での比較方法を利用することにより, 組の個数が $O(N^2)$, 判定が $O(1)$ なので, 全体では $O(N^2)$ で答えを求めることができ, $N \leq 3000$ という条件下では高速である.

##<font color=#C0C000> D問題 (400pts, diff: 2074) </font> [Congruence Points](https://atcoder.jp/contests/abc207/tasks/abc207_d)

$N=1$ のときは平行移動により, 可能であることがわかる. 以下では, $N \geq 2$ とする.

ここで, 原点中心に $\theta$ だけ回転させる変換を $R_\theta$, $x$ 軸方向に $a$, $y$ 軸方向に $b$ だけ平行移動させる変換を $M_{a,b}$ とする. このとき, $T_\theta, M_{a,b}$ について合成を演算にして生成される群を $\mathfrak{G}$ と書くことにする.

ここで, 各変換 $F \in \mathfrak{G}$ について, $F$ は等距離変換である. つまり, 2点 $P,P' \in \mathbb{R}^2$ の (Euclid) 距離を $\operatorname{dist}(P,P')$ と書くことにすると,
$$\operatorname{dist}(F(P),F(P'))=\operatorname{dist}(P,P')$$
が成り立つ.

以下の事実がある.
> $P,P', Q, Q' \in \mathbb{R}^2$ とする. このとき, $\operatorname{dist}(P,P')=\operatorname{dist}(Q,Q')>0$ ならば, $F(P)=Q, F(P')=Q'$ となる $F \in \mathfrak{G}$ が <b>一意に</b> 存在する.

証明: 以下では 座標平面上の点 $(x,y)$ と $\mathbb{R}^2$ 上のベクトル $(x,y)$ を同一視する.
このとき, $P$ から見た $Q$ の偏角を $\theta$, $P'$ から見た $Q'$ の偏角を $\theta'$ としたとき, $F=M_{P'} \circ R_{\theta'-\theta} \circ M_{-P}$ とすると,
$$F(P)=M_{P'}(R_{\theta'-\theta}(M_{-P}(P))))=M_{P'}(R_{\theta'-\theta}(0))=M_{P'}(0)=P'$$
$$F(Q)=M_{P'}(R_{\theta'-\theta}(M_{-P}(Q))))=M_{P'}(R_{\theta'-\theta}(Q-P)))=M_{P'}(Q'-P')=Q'$$
である. 一意性については略する.

$S=\\{P_1, \dots, P_N\\}, T=\\{Q_1, \dots, Q_N\\}$ とする. $F \in \mathfrak{G}$ に対して, $F(S)=T$ となるとき, $F(P_i)=Q_1, F(P_j)=Q_2$ となるような $i,j$ に着目することにして, 以下のような解法が生まれる.

> $i,j=1,\dots, N$ に対して, $i \neq j, \operatorname{dist}(P_i,P_j)=\operatorname{dist}(Q_1,Q_2)$ であり, 上での事実によって唯一存在する $F$ に対して, $F(S)=T$ となるような $i,j$ が存在するかどうかを求める.

$F$ は事実の証明での作り方によって, $O(1)$ で求めることができる. よって, 最悪計算量は $i,j$ の組の可能性が $O(N^2)$ の $F(S)=T$ の確認が $O(N)$ なので, 全体で $O(N^3)$ となり, $N \leq 100$ の制約下では十分高速である.

##<font color=#0000FF> E問題 (500pts, diff: 1820) </font> [Mod i](https://atcoder.jp/contests/abc207/tasks/abc207_e)

### 動的計画法への帰着
以下のような動的計画法を立てる.
$${\rm DP}[i,x]:=第 i 項までに制限し, しかもちょうど x 個の部分列となるような分割の方法の数$$

まず, ベースケースとして,

$${\rm DP}[0,x]=[x=0]=\begin{cases} 1 & (x=0) \\\\ 0 & (x \neq 0) \end{cases}$$

となる. 次に, 遷移式を考える. 連続部分列 $(A_{j+1}, \dots, A_i)$ を抜き出すことによって, 以下のような遷移式を導出することができる.

$${\rm DP}[i,x]=\sum_{\substack{j<i \\\\ x|(A_{j+1}+\dots+A_i)}} {\rm DP}[j,x-1]$$

このとき, 答えは $\sum_{x=1}^N {\rm DP}[N,x]$ である. しかし, これを愚直に計算すると, $O(N^4)$ になるので, $O(N^2)$ 分計算量を削減しなければならない. そこで, 以下のように計算量を削減する.

### 計算量の削減 1 (累積和)
$x|(A_{j+1}+\dots+A_i)$ について, 以下のような列を考える.

$$A^{{\rm cum}}\_0=0, \quad A^{{\rm cum}}\_i=A^{{\rm cum}}\_{i-1}+A_i$$

このとき, $A_{j+1}+\dots+A_i=A^{{\rm cum}}\_i-A^{{\rm cum}}\_j$ であることから, $A^{{\rm cum}}$ を前計算で求めることにより, $A_{j+1}+\dots+A_i$ を $O(1)$ で求めることができる. また,

$$x|(A_{j+1}+\dots+A_i)=A^{{\rm cum}}\_i-A^{{\rm cum}}\_j \iff A^{{\rm cum}}\_i \equiv A^{{\rm cum}}\_j \pmod{x}$$

であることから, 遷移式が

$${\rm DP}[i,x]=\sum_{\substack{j<i \\\\ A^{{\rm cum}}\_i \equiv A^{{\rm cum}}\_j \pmod{x}}} {\rm DP}[j,x-1]$$

になり, 計算量が $O(N^3)$ に減少した.

### 計算量の削減 2 (遷移を記録する)
集合 $S(i,x,y)$ を
$$S(i,x,y)=\\{j<i \mid A^{{\rm cum}}\_j \equiv y \pmod{x} \\}$$
とする. このとき,
$${\rm DP}[i,x]=\sum_{j \in S(i,x,A_i \bmod{x})} {\rm DP}[j,x-1]$$
である. また, 書き方として,
$$\langle S(i,x,A_i \bmod{x}) \rangle:=\sum_{j \in S(i,x,A_i \bmod{x})} {\rm DP}[j,x-1]$$
とする. このとき, ${\rm DP}[i,x]=\langle S(i,x,A_i \bmod{x}) \rangle$ である.

ここで, $\langle S(i,x,y) \rangle$ と $\langle S(i+1,x,y) \rangle$ の関係性に着目すると,

$$\langle S(i+1,x,y) \rangle=\begin{cases} \langle S(i,x,y) \rangle+{\rm DP}[i,x-1] & (A^{{\rm cum}}_i \equiv y \pmod{x}) \\\\ \langle S(i,x,y) \rangle & ({\rm otherwise}) \end{cases}$$

となる. 

このことから, $\langle S(i,x,y) \rangle$ と $\langle S(i+1,x,y) \rangle$ の違いは高々 $N$ 要素であることから, 配列を使い回すことにより, $\langle S(i,x,y) \rangle$ を $O(1)$ で求めることができる. 

よって, $O(N^2)$ にまで計算量を削減でき, $N \leq 3000$ という制約下では十分に高速である.

##<font color=#C0C000> F問題 (600pts, diff: 2398) </font>[Tree Patrolling](https://atcoder.jp/contests/abc207/tasks/abc207_f)
(正解でき次第加筆予定)