AtCoder Regular Contest 119 感想

#総合結果
* [Score] 800 pts
* [Time] 40:15 + <font color="red"> 05:00 $\times$ 0 </font> = 40:15
* [Ranking] 907 th [Rated内: 886 th]
* [Performance] <font color=#00C0C0> 1366　</font>
* [Rating] <font color=#C0C000> 2006 </font> → <font color=#0000FF> 1956 </font> (-50)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|300 pts|06:30|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc119/submissions/22662542)||
|<font color=#008000> B問題 </font>|0 pts|--:--|<font color="red"> (1 Penalty) </font>||[■](https://atcoder.jp/contests/arc119/submissions/22666444)|
|<font color=#00C0C0> C問題 </font>|500 pts|<b>40:15</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc119/submissions/22666444)||
|<font color=#FF8000> D問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#FF8000> E問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#AEB3B5> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>800 pts</b>|<b>40:15</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff: 69) </font> [119 × 2^23 + 1](https://atcoder.jp/contests/arc119/tasks/arc119_a)

非負整数 $N$ が $N=a \times 2^b+c$ を満たすとする. $a=0$ のときは, $b=0, c=N$ とすることで, $a=0$ のときの $a+b+c$ を最小にできる. 以下では $a \geq 1$ とする. このとき, $b$ の可能性はとても小さい. 実際, $a,b,c$ は非負整数なので,
$$2^b \leq a \times 2^b+c=N$$
より, $0 \leq b \leq \lfloor \log_2 N \rfloor$ であることがわかる.

ここから, $0 \leq b \leq \lfloor \log_2 N \rfloor$ なる $b$ を1つ固定する. このとき, $N=a \times 2^b+c$ を満たす $(a,c)$ の中で, $a+b+c$ を最小にするのは, $a,c$ をそれぞれ $N$ を $2^b$ で割った商と余りである.
> (証明): $q,r$ を $N$ を $2^b$ で割った商と整数とする. このとき, $N=a \times 2^b+c$ を満たす非負整数 $a,c$ はある非負整数 $k$ を用いて, $a=q-k, c=r+k \times 2^b$ と表すことが切る. このとき, $a+b+c=b+q+r+(2^b-1)k$ であるが, $b \geq 0$ より, $2^b-1 \geq 0$ なので, $k$ はできるだけ小さくするのが最適で, $k$ は非負という条件から, $k=0$ とすべきである. よって, $(a,c)=(q,r)$ であり, これは $N$ を $2^b$ で割った商と余りに一致する.

従って, $b=0,1, \dots, \lfloor \log_2 N \rfloor$ における $N$ を $2^b$ で割った商と余りを $q_b, r_b$ としたとき,
$$\min_{0 \leq b \leq \lfloor \log_2 N \rfloor} (q_b+b+r_b)$$
が答えである.


##<font color=#008000> B問題 (500pts, diff: 1196) </font> [Electric Board](https://atcoder.jp/contests/arc119/tasks/arc119_b)

まず, 操作において $0$ の個数は不変なので, $S,T$ にある $0$ の個数が異なっていれば, 不可能確定である.

$0$ の個数が等しいとき, $T$ に一致させることは可能である. ここで, $S,T$ にある $0$ について, 左から順に添字付ける. このとき, 1回の操作で $0$ を他の $0$ を超えないように自由に移動できる. よって, $S,T$ にある左から $k$ 番目の $0$ のインデックスをそれぞれ $i_k, j_k$ とすると, $i_k=j_k$ ならば $0_i$ を動かす必要はなく, $i_k \neq j_k$ ならば適切な順番で, 1回ずつ動かすことで目標を達成できる. よって, 求める正解は
$$\sum_{k} [i_k \neq j_k]$$
である.

##<font color=#00C0C0> C問題 (500pts, diff: 1354) </font> [ARC Wrecker 2](https://atcoder.jp/contests/arc119/tasks/arc119_c)

まず, 固定された数列 $B=(B_1, \dots, B_K)$ に対して, 答えが YES になるための必要十分条件を考える. ここで, 高さを減らすという操作における高さ制限は, 高さを全て増やす操作を行った後に行えば可能なときには高さ制限を気にしなくてすむ.

代数的に解く. 高さを1減らすという操作は, 高さを-1増やすと考えると, 可能なことと以下を満たす $K-1$ 個の整数 $X_i$ が存在することが同値であることがわかる.
$$X_1=B_1, \quad X_1+X_2=B_2, \quad \dots, \quad X_{j-1}+X_j=B_j, \quad, \dots, X_{K-2}+X_{K-1}=B_{K-1}, \quad X_{K-1}=B_K$$

このとき, 最後の式以外から, $X_1, \dots, X_{K-1}$ は

```math
\begin{cases}
X_1=B_1 \\\\
X_2=B_2-X_1 &=B_2-B_1 \\\\
X_3=B_3-X_2 &=B_3-B_2+B_1 \\\\
\vdots \\\\
X_{K=1}=B_{K-1}-X_{K-2} &=B_{K-1}-B_{K-2}+\dots+(-1)^{K-1} B_1
\end{cases}
```

でなくてはならない. そして最後の式から,
$$B_K=B_{K-1}-B_{K-2}+\dots+(-1)^{K-1} B_1$$
でなくてはならない. つまり,
$$\sum_{i=1}^K (-1)^{i-1} B_i=0$$
が必要十分であることがわかる.

条件を数式で表すことができたので, 次に, 条件を満たす組を数え上げる.
条件式の $(-1)^i$ の部分がなければ累積和を利用して解くことができる. これを利用してとく. $S_k$ を $S_k=A_1-A_2+\dots+(-1)^{k-1} A_k$ とする. このとき,
$$\sum_{i=l}^r (-1)^{i-1} A_i=\sum_{i=1}^r (-1)^{i-1} A_i-\sum_{i=1}^{l-1} (-1)^{i-1} A_i=S_r-S_{l-1}$$
より,
$$\sum_{i=l}^r (-1)^{i-1} A_i=0 \iff S_r=S_{l-1}$$
なので, $1 \leq l<r \leq N$ で, $S_r=S_{l-1}$ を満たすのはいくつか? という問題に帰着できた. ここで, 仮に, $r=l$ とすると, $S_r-S_{l-1}= A_r$ であり, $A_r>0$ という制約から, $1 \leq l \leq r \leq N$ としてもよい.

以上から $E_x$ で $S_i=x$ なる添字 $i$ の個数とすると, 答えは
$$\sum_x \dfrac{E_x (E_x-1)}{2}$$
である.

##<font color=#FF8000> D問題 (700pts, diff: 2713) </font> [Grid Repainting 3](https://atcoder.jp/contests/arc119/tasks/arc119_d)
(正解でき次第加筆予定)

##<font color=#FF8000> E問題 (800pts, diff: 2502) </font> [Pancakes](https://atcoder.jp/contests/arc119/tasks/arc119_e)
(正解でき次第加筆予定)

##<font color=#AEB3B5> F問題 (800pts, diff: 3671) </font> [AtCoder Express 3](https://atcoder.jp/contests/arc119/tasks/arc119_f)
(正解でき次第加筆予定)

#感想

##反省点
* <font color=#008000>B問題</font> $\cdots$ 誤読