AtCoder Regular Contest 112 感想

#総合結果
* [Score] 700 pts
* [Time] 77:02 + <font color="red"> 05:00 $\times$ 0 </font> = 77:02
* [Ranking] 1544 th [Rated内: 1518 th]
* [Performance] <font color=#008000> 1196　</font>
* [Rating] <font color=#0000FF> 1899 </font> → <font color=#0000FF> 1845 </font> (-54)

##各問題ごとの詳細, 提出コード
|Question|Time/Result|Penalty|During Contest|After Contest|
|:--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|10:02|<font color="red">  </font>|[■](https://atcoder.jp/contests/arc112/submissions/20144274)||
|<font color=#008000> B問題 </font>|77:02|<font color="red">  </font>|[■](https://atcoder.jp/contests/arc112/submissions/20155932)||
|<font color=#0000FF> C問題 </font>||<font color="red">  </font>||[■](https://atcoder.jp/contests/arc112/submissions/20198317)|
|<font color=#C0C000> D問題 </font>||<font color="red">  </font>|||
|<font color=#FF8000> E問題 </font>||<font color="red">  </font>|||
|<font color=#B87333> F問題 </font>||<font color="red"> </font>|||

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff: 108) </font> [-B=C](https://atcoder.jp/contests/arc112/tasks/arc112_a)
$A-B=C \iff A=B+C$ より, まず $A$ を固定したときの$(B,C)$ の個数を数える. $(L-R+1)^2$ 個の要素
$$(L,L), (L,L+1), \dots, (L,R), (L+1,R), \dots , (R,R)$$
の組のうち, $x+y=A$ なる組 $(x,y)$  の個数を $E_A$ とする. このとき,
$$E_A=\begin{cases} A-(2L-1) & (2L \leq A \leq L+R) \\\\
(2R+1)-A & (L+R \leq A \leq 2R) \\\\
0 & ({\rm otherwise})\end{cases}$$
である.  求めるべきは $\sum_{A=L}^R E_A$ である. しかし, $R \leq L+R$ なので,
$$\sum_{A=L}^R E_A=\begin{cases} \dfrac{1}{2}(R-2L+1)(R-2L+2) & (2L \leq R) \\\\
0 & (2L>R) \end{cases}$$
である. よって, $O(1)$ で計算できた.

##<font color=#008000> B問題 (400pts, diff: 822) </font> [-- - B](https://atcoder.jp/contests/arc112/tasks/arc112_b)
$C=1$ のとき, 作れる整数は $\pm B$ に限る. よって, $B \neq 0$ ならば答えは $2$ で, $B=0$ ならば答えは $1$ である.

以下, $C \geq 2$ とする. ここで, 整数 $B$ から整数 $B'$ を作ろうとした際, 払うお金を少なくするためには, 以下のように行動しなければならない.
$$( \times -1 をする/しない) \to (-1 を必要な回数) \to (\times -1 をする/しない)$$

これは以下のようにして示すことができる. ただし, $P,Q$ をそれぞれ $\times 1, -1$ する操作とする.

* 様々な操作において, $P \to P$ と $Q \to P \to Q$ を含む操作はそれぞれ「なにもしない」, 「$P$」 という操作に置き換えることができる. よって, この2つを含むような操作を考える必要はない.
* $P \to P$ が禁止されるということは $P$ が連続しないことを表し, $Q \to P \to Q$ が禁止されるということは, $P$ は最初または最後にしなければならないことを表す.
* 以上から, 考える必要がある操作は最初と最後に $P$ をするかどうかと, 間に $Q$ を何回するかどうかのみを考えればよく, これは上に対応する.
 
こうして得られた4つのパターンについて$C$ 円以下で作れる整数を考える. ただし, $\alpha_k:=\lfloor \frac{C-k}{2} \rfloor$ とする.

* する $\to$ するの場合 $\cdots$ これで作れる整数は $B$ 以上 $B+\alpha_2$ 以下の全ての整数である.
* する $\to$ しないの場合 $\cdots$ これで作れる整数は $-B-\alpha_1$ 以上 $-B$ 以下の全ての整数である.
* しない $\to$ するの場合 $\cdots$ これで作れる整数は $-B$ 以上 $B+\alpha_1$ 以下の全ての整数である.
* しない $\to$ しないの場合 $\cdots$ これで作れる整数は $B-\alpha_0$ 以上 $B$ 以下の全ての整数である.

1番目と4番目, 2番目と3番目をまとめると, $C$ 円以下で作れる整数は
$$([B-\alpha_0,B+\alpha_2] \cup [B-\alpha_1,B+\alpha_1]) \cap \mathbb{Z}$$
であるので, 最後にこの集合の濃度を求める.

$X=[p,q] \cap \mathbb{Z}, Y=[r,s] \cap \mathbb{Z}$ は $p \leq r$ を満たすとする. このとき, $r \leq q$ ならば, $X \cup Y=[p,s]$ であり, $r>q$ ならば, $X \cap Y=\emptyset$ である. よって,
$$|X \cup Y|=\begin{cases} s-p+1 & (r \leq p) \\\\ (q-p+1)+(s-r+1) & (r>q) \end{cases}$$
である.

##<font color=#0000FF> C問題 (500pts, diff: 1913) </font> [DFS Game](https://atcoder.jp/contests/arc112/tasks/arc112_c)
(2021/02/15 加筆)
与えられた木を $T$ とし, 頂点 $v$ を根とする部分木を $S_v$ とする. コマの動きが深さ優先探索の動きなので, コマが1度頂点 $v$ に到達したら, $S_v$ 上のコインをすべてとるまでコマは $S_v$ を抜けることはない. また, $S_v$ を抜けた後は二度とコマは $S_v$ には入らない. このことから, 木DPを用いて解くことができると考えることができる.

$X_v$ を $S_v$ に制限したゲームで(先手が獲得するコインの枚数) $-$ (後手が獲得するコインの枚数) とする. ここで, $S_1=T$ で, $T$ には $N$ 個の頂点があることから, 求めるべき解答は $\dfrac{N+X_1}{2}$ であることがわかる.

ここから $X_v$ を求めていく. まず, 先手は頂点 $v$ のコインを獲得し, 後手が $v$ の子から1つの頂点 $w$ を選び, その頂点にコマを進め, $S_w$ 上のゲームを行った後, $w$ から $v$ にコマは戻る. ここで, 再び $v$ に戻った後に動かすプレイヤーが変わっている可能性があるので, これについて考える.

$S_v$ にある頂点数を $M_v$ とする. $v$ から $w$ に進み, 再び $v$ に戻るまでにはそれぞれ以下の行動を何回とるかを考える.

* $v$ から $w$ にコマを進める.
* $M_w$ 回コインを取る.
* $M_w-1$ 回コマを子に進める.
* $M_w-1$ 回コマを親に戻す.
* $w$ から $v$ にコマを戻す.

以上の行動の合計回数は $3M_w$ 回なので, $M_w$ が奇数だと先手後手が入れ替わり, $M_w$ が偶数だと, 先手後手がそのままである. このことを利用すると, $v$ のコインをとった後に後手はどのように行動するべきかがわかる.

* $X_w \leq 0$ かつ $M_w$ が偶数のとき, $w$ のコインを取るのは相手なので, $S_w$ 内でのゲームで自分は相手が獲得したコインの枚数以上に獲得することができ, 再び新たな $w'$ を選ぶ権利を得ることができるので, 存在するならば積極的に選ぶべきである.

* $X_w > 0$ かつ $M_w$ が偶数のとき, $w$ のコインを取るのは相手なので, $S_w$ 内でのゲームで自分は相手が獲得したコインの枚数を下回る. しかし, 再び新たな $w'$ を選ぶ権利を得ることができるので, 無理に選ぶ必要はない.

* $M_w$ が奇数のとき, 新たな $w'$ を選ぶのは相手になる. このことから最善な行動をするとするならば, $M_w$ が奇数である子 $w$ のうち, $X_w$ が最小となるような $w$ を選ぶべきである.

よって, $v$ の子のうち, $M_\bullet$ が偶数になるものを $a_1, \dots, a_p, b_1, \dots, b_q$, 奇数になるものを $c_1, \dots, c_r$ とする. ただし, 以下を満たすように並び変える.
$$X_{a_1}, \dots X_{a_p} \leq 0, \quad X_{b_1}, \dots, X_{b_q} > 0, \quad X_{c_1} \leq \dots \leq X_{c_r}$$
このとき,
$$X_v=1+\sum_{i=1}^p X_{a_i}+\sum_{j=1}^r (-1)^{j-1} X_{c_j}+(-1)^r \sum_{k=1}^q X_{b_k}$$
である.

このようにすると, $c_1, \dots, c_r$ におけるソートがネックになり, 計算量は $O(N \log N)$ となる.

##<font color=#C0C000> D問題 (600pts, diff: 2028) </font> [Skate](https://atcoder.jp/contests/arc112/tasks/arc112_d)
(未着手)

##<font color=#FF8000> E問題 (700pts, diff: 2659) </font> [Cigar Box](https://atcoder.jp/contests/arc112/tasks/arc112_e)
(未着手)

##<font color=#B87333> F問題 (900pts, diff: 3432) </font> [Die Siedler](https://atcoder.jp/contests/arc112/tasks/arc112_f)
(未着手)

#感想

##反省点
* <font color=#008000> B問題 </font> がとんでもなく遅い

#記録
* ARC B問題のACまでの時間 (ワースト) : $42:32 \to 77:02$
* 減少Rating : $-29 \to -54$
* Performance ワースト5