AtCoder Beginner Contest 185 感想

##総合結果
* [Score] 2100 pts (★Perfect★)
* [Time] 81:48+<font color=#FF0000>05:00$\times$3</font>=96:48
* [Ranking] 796th
* [Performance] <font color="cyan">1570</font>
* [Rating] <font color="blue"> 1698 </font> → <font color="blue"> 1686 </font> (-12)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 00:47
* <font color=#808080> B問題 </font> 07:14
* <font color=#808080> C問題 </font> 11:42
* <font color=#804000> D問題 </font> 29:11 <font color=#FF0000>(+2 PENALTIES)</font>
* <font color=#00C0C0> E問題 </font> 81:48 <font color=#FF0000>(+1 PENALTY)</font>
* <font color=#008000> F問題 </font> 38:05

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff:7) </font> [ABC Preparation](https://atcoder.jp/contests/abc185/tasks/abc185_a)
答えは $\min(A_1,A_2,A_3,A_4)$ である.

##<font color=#808080> B問題 (200pts, diff:93) </font> [Smartphone Addiction](https://atcoder.jp/contests/abc185/tasks/abc185_b)
数列 $A,B$ に便宜的に $A_0,A_{M+1},B_0,B_{M+1}$ として以下の値を加える.
$$A_0=B_0=0,\quad A_M=B_M=T$$
このとき, $k$ 回目のカフェに入る瞬間のバッテリー残量 $X_k$ と, 出る瞬間のバッテリー残量 $Y_k$ は
$$X_0=Y_0=N,\quad X_k=Y_{k-1}-(A_k-B_{k-1}),\quad Y_k=\min(N,X_k+(B_k-A_k))$$
となる. このとき, $0<X_1,\dots,X_{M+1}$ かどうかを調べればよい.

##<font color=#808080> C問題 (300pts, diff:374) </font> [Duodecim Ferra](https://atcoder.jp/contests/abc185/tasks/abc185_c)
$L-1$ 個の棒の切れ目の候補に $11=12-1$ 個の切れ目を入れる場合の数なので, 答えは
$$\dbinom{L-1}{11}$$
である. なお, $f(X,N)\ (X \geq N)$ で長さ $X$ の棒を各棒の長さが全て正整数になるように $N$ 個に分割する方法とすると,
$$f(k,k)=1\ (k=0,1,\dots,N) ,\quad f(X,N)=\sum_{x=N-1}^{X-1} f(x,N-1)$$
となるので, この式において $f(L,12)$ を求めても良い.

#<font color=#804000> D問題 (400pts, diff:490) </font> [Stamp](https://atcoder.jp/contests/abc185/tasks/abc185_d)
ボードにある白マスが連続して $A_1,A_2,\dots,A_L$ 個あるとする. このとき, $k=\min(A_1,A_2,\dots,A_L)$ とすべきである. このとき, 回数は
$$\sum_{i=1}^L \left \lceil \dfrac{A_i}{k} \right \rceil$$
である.

##<font color=#00C0C0> E問題 (500pts, diff:1468)</font> [Sequence Matching](https://atcoder.jp/contests/abc185/tasks/abc185_d)
動的計画法で解く. ${\rm DP}[i,j]~(0 \leq i \leq N, 0 \leq j \leq M)$ を以下で定義する.
$${\rm DP}[i,j]=問題をA[1:i],B[1:j]に制限した時の答え$$
このとき, ベースケースとして,
$${\rm DP}[0,j]=j,\quad {\rm DP}[i,0]=i$$
をすぐに定めることができる. 次に, $1 \leq i,j$ のときの ${\rm DP}[i,j]$ を考える. このとき, 数列の要素を削除する際, 前から削除するよりも後ろから削除するほうが後々の展開を予測しやすい. このことに注意すると, 以下の3つの行動を考えることができる.

* $A[1:i]$ の $A[i]$ を削除して, $x$ に $1$ を加える. そして, $A[1:i-1],B[1:j]$ での最適な操作をする.
* $B[1:j]$ の $B[j]$ を削除して, $x$ に $1$ を加える. そして, $B[1:i],B[1:j-1]$ での最適な操作をする.
* $A[i],B[j]$ をマッチングさせ, $A[1:i-1],B[1:j-1]$ での最適な操作をする. このとき, $A[i] \neq B[j]$ ならば, $y$ に $1$ を加える.

よって,
$${\rm DP}[i,j]=\min({\rm DP}[i-1,j]+1, {\rm DP}[i,j-1]+1, {\rm DP}[i-1,j-1]+[A[i] \neq B[j]])$$
によって計算量 $O(MN)$ で解くことができた.

##<font color=#008000> F問題 (600pts, diff:1053)</font> [Range Xor Query](https://atcoder.jp/contests/abc185/tasks/abc185_f)
以下, $\mathbb{N}$ を非負整数全体の集合とする. $\oplus: \mathbb{N}^2 \to \mathbb{N}$ を $x \oplus y$ で $x,y$ の排他的論理和とする. このとき, 代数系 $(\mathbb{N},\oplus)$ は以下の性質を満たすことが分かる. ただし, $x,y,z \in \mathbb{N}$ とする.

* $x \oplus (y \oplus z)=(x \oplus y) \oplus z$
* $x \oplus 0=0 \oplus x=x$
* $x \oplus x=0$

よって, 代数系 $(\mathbb{N},\oplus)$ は群を成すことが分かる.
ここで, 2種類の Query はそれぞれ

* $A_k$ を $A_k \oplus Y$ に置き換える.
* $\bigoplus_{k=X}^Y A_k$ を求める.

と $\oplus$ に関するQueryなので, Bit木を用いて高速に処理することができる.

#感想
##良かった点
* <font color=#008000> F問題 </font> を一瞬で処理できた.

##反省点
* <font color=#808080> B問題 </font>, <font color=#804000> D問題 </font>, <font color=#00C0C0> E問題 </font> が時間かかりすぎ+無駄WAをしてしまった.