AtCoder Beginner Contest 196 感想

#総合結果
* [Score] 1500 pts
* [Time] 78:12 + <font color="red"> 05:00 $\times$ 2 </font> = 88:12
* [Ranking] 439 th [Rated内: 276 th]
* [Performance] <font color=#0000FF> 1879　</font>
* [Rating] <font color=#0000FF> 1874 </font> → <font color=#0000FF> 1874 </font> (± 0)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:
|<font color=#808080> A問題 </font>|100 pts|01:29|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc196/submissions/21061564)<br>(計算量 $O(1)$)|[■](https://atcoder.jp/contests/abc196/submissions/21116474)<br>(全探索)|
|<font color=#808080> B問題 </font>|200 pts|03:11|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc196/submissions/21065709)||
|<font color=#808080> C問題 </font>|300 pts|05:00|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc196/submissions/21068918)<br>($O(\sqrt{N})$)|[■](https://atcoder.jp/contests/abc196/submissions/21116048)<br>($O(\log N)$)<br>[■](https://atcoder.jp/contests/abc196/submissions/21116119)<br>($O(1)$)|
|<font color=#00C0C0> D問題 </font>|400 pts|<b>78:12</b>|<font color="red"> </font>|[■]()||
|<font color=#0000FF> E問題 </font>|500 pts|59:08|<font color="red"> 2 Penalties </font>|[■](https://atcoder.jp/contests/abc196/submissions/21093432)<br>(二部探索)|[■](https://atcoder.jp/contests/abc196/submissions/21113932)<br>(直接)|
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc196/submissions/21115974)<br>(畳み込みは数論変換を利用している)|
|<b>Total</b>|<b>1500 pts</b>|<b>88:12</b>|<b><font color="red"> 2 Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 9) </font> [Difference Max](https://atcoder.jp/contests/abc196/tasks/abc196_a)

$a \leq x \leq b, c \leq y \leq d$ のとき, $-d \leq -y \leq -c$ であることから, $a-d \leq x-y \leq b-c$ である. また, $(x,y)=(b,c)$ とすると, $x-y=b-c$ となることから,
$$\max_{\substack{a \leq x \leq b \\\\ c \leq y \leq d}} (x-y)=b-c$$
である.

なお, この問題では, $|a|,|b|,|c|,|d| \leq 100$ と制約が小さいことから, $a \leq x \leq b, c \leq y \leq d$ を満たす整数の組 $(x,y)$ を全探索しても求めることができる (計算量: $O(\max \\{|a|,|b|,|c|,|d|\\}^2)$)

##<font color=#808080> B問題 (200pts, diff: 39) </font> [Round Down](https://atcoder.jp/contests/abc196/tasks/abc196_b)

$X$ を文字列として持つ, $X$ が $"{\tt .}"$ を持っていなければ, $X$ は整数なので, そのまま出力する. もし, $"{\tt .}"$ を持っていれば, $X$ の切り捨ては, $X$ の $"{\tt .}$ より左側のみを抽出した文字列を整数とみなしたときの値と, $X$ の切り捨ては一致する.

##<font color=#808080> C問題 (300pts, diff: 244) </font> [Doubled](https://atcoder.jp/contests/abc196/tasks/abc196_c)

正の整数 $t$ に対して, $f(t)$ で $t$ を2つつなげてまとめて1つの整数と見た時の整数とする.[^c1] ここで, $f(t)$ について, 以下の性質がある.

* $t$ が $d$ 桁の整数のとき, $f(t)$ は $2d$ 桁の整数である.
* $f(t)$ は単調増加である.

よって, $N \leq 10^{12}$ という制約から, $t<10^6$ が明らかになる. $f$ が単調増加なので,
$$f(p) \leq N < f(p+1)$$
となる $p$ を ${\tt while}$ 文で求め, この $p$ がそのまま答えである. なお, 計算量は $O(10^{d/2})=O(\sqrt{N})$ である.

なお, $f$ が単調増加という性質から, 2分探索でも求めることができ, この場合, 計算量は $O(\log N)$ になる.

そして, 実は $O(1)$ でも解くことができる.

[^c1]: 例えば, $f(4)=44, f(35)=3535, f(12345)=1234512345$ 

##<font color=#00C0C0> D問題 (400pts, diff: 1277) </font> [Hanjo](https://atcoder.jp/contests/abc196/tasks/abc196_d)

$2 \times 1$ の $A$ 枚の畳の埋め方を決めれば, 残りの $1 \times 1$ の $B$ 枚の畳の埋め方は一意に定まることから, $2 \times 1$ の $A$ 枚の畳の埋め方を考える. これは深さ優先探索を実装することによって, 可能になる. ただし, 同じ形の畳は区別しないことから, 例として, $AABB$ と $BBAA$ は同一視しなければいけないことに注意せよ.

##<font color=#0000FF> E問題 (500pts, diff: 1650) </font> [Filters](https://atcoder.jp/contests/abc196/tasks/abc196_e)

$p_a(x), q_a(x), r_a(x):\mathbb{R} \to \mathbb{R}$ をそれぞれ
$$p_a(x):=x+a, \quad q_a(x):=\max(x,a), \quad r_a(x):=\min(x,a)$$
とする.

$\mathcal{F}:=\\{p_a|a \in \mathbb{R}\\} \cup \\{q_a|a \in \mathbb{R}\\} \cup \\{r_a|a \in \mathbb{R}\\}$ とし,
$$\mathfrak{M}:=\\{f^k \circ \dots \circ f^1~|~k \in \mathbb{N}, f^1, \dots, f^k \in \mathcal{F}\\}$$
とする. このとき, $\mathfrak{M}$ の性質を調べる. ここで, $-\infty \leq \alpha \leq \beta \leq \infty$ に対して, $\[\alpha,\beta\]:\mathbb{R} \to \mathbb{R}$ を,
$$ \[\alpha, \beta\](x):=\begin{cases} \alpha & (x<\alpha) \\\\ x & (\alpha \leq x \leq \beta) \\\\ \beta & (\beta<x) \end{cases}$$
とすると, 任意の $g \in \mathfrak{M}$ に対して, $g(x)=\[\alpha, \beta \](x)+s~(\forall x \in \mathbb{R})$ なる $-\infty \leq \alpha \leq \beta \leq \infty, s \in \mathbb{R}$ が存在する. このことを示す.

* ${\rm id}_{\mathbb{R}}(x)=\[-\infty,\infty\](x)+0$ より成立する.
* $g=\[\alpha, \beta\](x)+s \in \mathfrak{M}$ と, $f \in \mathcal{F}$ に対して, $f \circ g$ を調べる. 
 * $f=p_a$ のとき: $(p_a \circ g)(x)=\[\alpha, \beta]\(x)+(s+a)$ である.
 * $f=q_a$ のとき:
 $$(f \circ g)(x)
=f(g(x))
=q_a(\[\alpha, \beta\](x)+s)
=\max(a,\[\alpha, \beta\](x)+s)
=\begin{cases} \[\alpha, \beta\](x)+s & (\[\alpha, \beta\](x)+s \geq a) \\\\
 a & ({\rm otherwise}) \end{cases}$$
である. ここで,
 $$\[\alpha, \beta\](x)+s \geq a \iff
 \begin{cases}
 {\rm True} & (a-s \leq \alpha)\\\\
 a-s \leq x & (\alpha < a-s \leq \beta) \\\\
 {\rm False} & (\beta < a-s) 
 \end{cases}$$
 となることから,
 $$f \circ g=\begin{cases}
 \[\alpha, \beta\](x)+s & (a-s \leq \alpha) \\\\
 \begin{cases} \[\alpha, \beta\](x)+s & (x \geq a-s) \\\\ a  & (x<a-s) \end{cases} 
 & (\alpha<a-s \leq \beta) \\\\
 a & (\beta<a+s)
 \end{cases}$$
 である. ここで, $\alpha<a-s \leq \beta$ のとき,
 $$\begin{cases} \[\alpha,\beta \](x)+s & (x \geq a-s) \\\\
 a & (x<a-s)\end{cases}=\[a-s,\beta](x)+s$$
 であり, $a=\[a,a\](x)+0$ になることに注意すると,
 $$f \circ g=\begin{cases}
 \[\alpha, \beta\](x)+s & (a-s \leq \alpha) \\\\
 \[a-s, \beta\](x)+s & (\alpha < a-s \leq \beta) \\\\
 \[a, a\](x)+0 & (\beta<a-s)
 \end{cases}$$
 である.

 * $f=r_a$ のとき: 上と同様にして
 $$(f \circ g)(x)=\begin{cases} \[a,a\](x)+0 & (a-s \leq \alpha) \\\\
 \[\alpha, a-s \](x)+s & (\alpha < a-s \leq \beta) \\\\
 \[\alpha, \beta\](x)+s & (\beta<a-s) \end{cases}$$
となる.

以上のことから, 任意の $g \in \mathfrak{M}$ に対して, $g(x)=\[\alpha, \beta\](x)+s$ なる $-\infty \leq \alpha \leq \beta \leq \infty, s \in \mathbb{R}$ が存在する. よって, $g:=(f_N \circ \dots \circ f_1)(x)=\[\alpha, \beta\](x)+s$ は $O(N)$ で求めることができ, 1クエリあたり $g(x)$ は $O(1)$ で計算できることから, 全体で $O(N+Q)$ で求めることができた.

なお, $\mathcal{F}$ の元が単調増加であることから, $\mathfrak{M}$ の元も単調増加であることから, $\alpha, \beta$ については, $c_\pm:=\displaystyle \lim_{x \to \pm \infty} f(x)$ を求め, $c_+=f(x)$ を満たす最大の実数が $\alpha$, $c_-=f(x)$ を満たす最小の実数が $\beta$ であり, $\alpha \leq x \leq \beta$ なる実数 $x$ を1つ固定すると, $g(x)=\[\alpha, \beta\](x)+s=x+s$ より, $s$ も求めることができる. ここで, $\alpha, \beta$ は今回の制約では存在すれば整数になることが証明ことに注意し, 二分探索で求めることができる. そして, $c_{\pm}$ が有限でないとき, $\alpha, \beta$ となる実数は存在しないので, そこに関する実装には注意すること.

##<font color=#C0C000> F問題 (600pts, diff: 2274) </font>[Substring 2](https://atcoder.jp/contests/abc196/tasks/abc196_f)
(2020/03/21 加筆)
文字列 $S,T$ を, $0,1$ からなる長さ $|S|,|T|$ の列と同一視する. また, $N:=|S|, M:=|T|$ とする. そして, 以下から列はすべて 0-indexed とする.

まず, 部分列の位置の候補として, 初項が $S_0, \dots, S_{N-M}$ の $N-M+1$ 通りに限られる. ここで, $S$ の部分列 $(S_i,S_{i+1}, \dots, S_{i+M-1})$ と $T$ の間の Hamming 距離を $A_i$ とすると, 求めるべき答えは $\displaystyle \min_{0 \leq i \leq N-M} A_i$ が答えである.

次に, 各 $A_i$ について考えると, Hamming距離は
$$A_i=\sum_{k=0}^{M-1} [S_{i+k} \neq T_k]$$
で求めることができる.

ここで, $S,T$ の各項は $0,1$ からなっていることから, 以下の等式が成り立つことに気づかなければならない. ただし,$a,b \in \\{0,1\\}$ とし, $\oplus$ で排他的論理和とする.
$$[a \neq b]=a \oplus b=a(b-1)+(a-1)b$$
よって,
$$A_i=\sum_{k=0}^{M-1} (S_{i+k} \oplus T_k)$$
である.

次に, 今後の理論展開のため, 長さ $U$ の列を $T$ の反転とする. つまり, $U_k:=T_{M-1-k}$ である. このとき, $T_k=U_{M-1-k}$ であり,
$$A_i=\sum_{k=0}^{M-1} (S_{i+k} \oplus U_{M-1-k})$$

ここで, シグマのなかの式に着目する. すると, $S,U$ の添字について, 2つの添字の和が $M+i-1$ と一定なことに気がつく. よって, 上の式を前に述べた $\oplus$ の性質を用いると, 
$$A_i=\sum_{\substack{p+q=M+i-1\\\\ 0 \leq p<N \\\\ 0 \leq q< M}} (S_p \oplus U_q)=\sum_{\substack{p+q=M+i-1\\\\ 0 \leq p<N \\\\ 0 \leq q< M}} S_p(1-U_q)+\sum_{\substack{p+q=M+i-1\\\\ 0 \leq p<N \\\\ 0 \leq q< M}} (1-S_p)U_q$$
となる.

以下, $\displaystyle B_i:=\sum_{\substack{p+q=M+i-1\\\\ 0 \leq p<N \\\\ 0 \leq q< M}} S_p(1-U_q)$ とする. $V_q:=1-U_q$ と置くと,
$$B_i=\sum_{\substack{p+q=M+i-1\\\\ 0 \leq p<N \\\\ 0 \leq q< M}} S_p V_q$$
となる. このように, 添字の和が一定であるような添字の組み合わせ全てにおける積和を求めることを畳み込みという. 愚直に実装すると, 畳み込みには $O(NM)$ かかり, 間に合わない. しかし, 高速 Fourier 変換を用いることにより, $B_0, \dots, B_{N-M}$ をまとめて $O(L \log L)$ で求めることができる. ただし, $L:=N+M$ とする.

同様に, $\displaystyle C_i:=\sum_{\substack{p+q=M+i-1\\\\ 0 \leq p<N \\\\ 0 \leq q< M}} (1-S_p)U_q$ もまとめて $O(L \log L)$ で求めることができ, $A_i=B_i+C_i$ から, $\min A_i$ を求めることができる.

以上の仮定により, 計算量 $O(L \log L)$ で求めることができた.