AtCoder Beginner Contest 189 感想

##総合結果
* [Score] 2100 pts (★Perfect★)
* [Time] 60:08+<font color="red"> 05:00 $\times$ 1 </font>=65:08
* [Ranking] 79th [Rated内: 18th]
* [Performance] <font color=#FF8000> 2400　</font>
* [Rating] <font color=#0000FF> 1787 </font> → <font color=#0000FF> 1866 </font> (+79)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 00:39
* <font color=#808080> B問題 </font> 03:21
* <font color=#804000> C問題 </font> 06:47
* <font color=#804000> D問題 </font> 13:29 
* <font color=#00C0C0> E問題 </font> 33:35 <font color="red"> (+1 PENALTY) </font>
* <font color=#C0C000> F問題 </font> 60:05

##提出コード(コンテスト後提出含む)
* <font color=#808080> A問題 </font> [■](https://atcoder.jp/contests/abc189/submissions/19582934)
* <font color=#808080> B問題 </font> [■](https://atcoder.jp/contests/abc189/submissions/19589022)
* <font color=#804000> C問題 </font> [■](https://atcoder.jp/contests/abc189/submissions/19594172)
* <font color=#804000> D問題 </font> [■](https://atcoder.jp/contests/abc189/submissions/19602129)
* <font color=#00C0C0> E問題 </font> [■](https://atcoder.jp/contests/abc189/submissions/19617713)
* <font color=#C0C000> F問題 </font> [■](https://atcoder.jp/contests/abc189/submissions/19631004) (計算量: $O(N \log N)$),  [■] (https://atcoder.jp/contests/abc189/submissions/19656304) (計算量: $O(N)$)

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 8) </font> [Slot](https://atcoder.jp/contests/abc189/tasks/abc189_a)
実装問題である. 以下に実装の例をあげる(コンテスト中提出).

```python:A.py
A,B,C=input()
if A==B==C:
    print("Won")
else:
    print("Lost")
```

##<font color=#808080> B問題 (200pts, diff: 274) </font> [Alcoholic](https://atcoder.jp/contests/abc189/tasks/abc189_b)
$i$ 番目のお酒を飲んだ後, 高橋くんが摂取した総アルコール量 $A_i$ は, $P_i$ がパーセンテージ表示であることに注意すると, $A_i=\sum_{k=1}^i V_i \times \frac{P_i}{100}$ である. よって, $X<A_i$ を満たす最小の $i$ を $i=1,\dots,N$ の順番に計算していけば良い. ここで, 計算機において, 小数を扱うとき, 誤差に十分な注意を払わなければならない. これを避けるために, 判定条件を
$$X<A_i \iff 100 X<\sum_{k=1}^i V_i P_i$$
にしておけば, 整数での計算になり, 誤差が発生しなくなり, 安心して計算できる.

##<font color=#804000> C問題 (300pts, diff: 565) </font> [Mandarin Orange](https://atcoder.jp/contests/abc189/tasks/abc189_c)
$1 \leq l \leq r \leq N$ を固定する. このとき, $x$ として可能な整数は,
$$1 \leq x \leq \min (A_l, \dots, A_r)$$
である. よって, $(l,r)$ を固定されたとき, 高橋くんはみかんを各皿 $\min (A_l, \dots, A_r)$ 個ずつ食べるべきである. よって, 求めるべき値は
$$X=\max_{1 \leq l \leq r \leq N} (r-l+1) \left(\min_{l \leq k \leq r} A_k \right)$$
であることがわかる. ここで, $X$ について式変形をすると,
$$X=\max_{l=1, \dots, N} \left(\max_{r=l, \dots,N}  (r-l+1) \left(\min_{l \leq k \leq r} A_k \right)\right)$$
になる. $l$ を固定する. $\min_{l \leq k \leq r} A_k$ について,
$$\min_{l \leq k \leq r} A_k=\begin{cases} \min \left(\min_{l \leq k \leq r-1} A_k, A_r \right) & (l<r) \\\\ A_l & (l=r) \end{cases}$$
であることを注意すると, $\max_{r=l, \dots,N}  (r-l+1) \left(\min_{l \leq k \leq r} A_k \right)$ を計算量 $O(N-l)$ で求めることができる. 従って, これを $l=1, \dots, N$ としていくと, 全体の計算量 $O(N^2)$ で求めることができ, $N \leq 10^4$ という制約から, 軽い実装をすれば十分実行時間制限に合う.

##<font color=#804000> D問題 (400pts, diff: 769) </font> [Logical Expression](https://atcoder.jp/contests/abc189/tasks/abc189_d)
真偽値のみをもつ変数 $A,B$ に対して, 以下が成立する. なお, 以下から $T,F$ でそれぞれ ${\rm True}, {\rm False}$ を表すとする. このとき,
$$A \land B=T \iff A=B=T\\\\ A \lor B=F \iff A=B=F$$
である.

動的計画法で求める. $k=0, \dots, N$ に対して, ${\rm DP}[k][X]$ で $x_0 S_1 \dots S_{k-1} x_k=X$ となる $x_0, \dots, x_k$ の割当の個数とする. ここで, ${\rm DP}[k][T]+{\rm DP}[k][F]=2^{k+1} \cdots (*)$ が成り立つことに注意する.

* $k=0$ のとき, $x_0=T$ を達成する $x_0$ への割当は $x_0=T$ のみの1通り, $x_0=F$ も同様なので, ${\rm DP}[0][T]={\rm DP}[0][F]=1$ である.
* $k \geq 1$ のとき
 * $S_k={\rm AND}$ のとき, $x_0~S_1~\dots~{\rm AND}~x_k=(x_0~S_1~\dots~S_{k-1}~x_{k-1})~{\rm AND}~x_k$ であり, 上で述べたことから, この式の結果 $T$ にするには,
 $$x_0~S_1~\dots~S_{k-1}~x_{k-1}=x_k=T$$
でなくてはならない.  よって,
 $${\rm DP}[k][T]=DP[k-1][T]$$
であることがわかる. また, $(*)$ から, ${\rm DP}[k][F]=2^{k+1}-{\rm DP}[k][T]$ も求まる.
 * $S_k={\rm OR}$ 上と同様にして, ${\rm DP}[k][F]={\rm DP}[k-1][F]$ であることがわかる. 従って, ${\rm DP}[k][T]=2^{k+1}-{\rm DP}[k][F]$ でもある.

この計算ににおける ${\rm DP}[N][T]$ が求めるべき解答である. 

##<font color=#00C0C0> E問題 (500pts, diff: 1526) </font> [Rotate and Flip](https://atcoder.jp/contests/abc189/tasks/abc189_e)
まず, 原点を中心に時計回りに90度回転させる写像を $r:\mathbb{R}^2 \to \mathbb{R^2}$, 直線 $x=p$ について対称な位置に移動させる写像を $f_p:\mathbb{R}^2 \to \mathbb{R^2}$, 直線 $y=p$ について対称な位置に移動させる写像を $g_p:\mathbb{R}^2 \to \mathbb{R^2}$ とする. このとき,

* $r(x,y)=(y,-x)$
* $f_p(x,y)=(-x+2p,y)$
* $g_p(x,y)=(x,-y+2p)$

になる. ここで, $r,f_p,g_p$ は全単射なので, $\mathfrak{S}(\mathbb{R}^2)$ を $\mathbb{R}^2$ から $\mathbb{R}^2$ への全単射全体の集合とすると, $\mathfrak{S}(\mathbb{R}^2)$ は写像の合成 $\circ$ に関して, 恒等写像 ${\rm id}$ を単位元とする群になる. そして, $H:=\langle r,f_p,g_p|p \in \mathbb{R} \rangle$ は $\mathfrak{S}(\mathbb{R}^2)$ の部分群になる.

ここで, $H$ について, 以下の性質があることを示す.
$$任意の h \in H に対して, h(x, y)=(ax+by+s, cx+dy+t) を満たす (a, b, c, d, s, t \in \mathbb{R}) が存在する.$$

* $h={\rm id}$ のとき, ${\rm id}(x,y)=(x,y)=(1x+0y+0,0x+1y+0)$ なので, $(a, b, c, d, s, t)=(1, 0, 1, 0, 0, 0)$ とすればよい.
* $h \in H$ とし, $h(x,y)=(ax+by+s, cx+dy+t)$ とする.
 * $(r \circ h)(x,y)=(cx+dy+t, -ax-by-s)$
 * $(r^{-1} \circ h)(x,y)=(-cx-dy-t, ax+by+s)$
 * $(f_p \circ h)(x,y)=(ax+by+s, -cx-dy+(2p-t))$
 * $(g_p \circ h)(x,y)=(-ax-by+(2p-s), cx+dy+t)$

 となり, またしても上での性質をみたす. なお, $f_p^{-1}=f_p, g_p^{-1}=g_p$ である.

よって, 変換の列 $h_1, \dots, h_M$ に対して, 写像の列 $H_0, \dots, H_M$ を
$$H_0={\rm id},\quad H_k=h_k \circ H_{k-1}$$
とすることによって, 与えられた点 $(X,Y)$ に対して, $A$ 回の操作直後の座標は $H_A(X,Y)$ で求めることができる.

以上から, $H_k(x,y)=(a_k x+b_k y+s_k, c_k x+d_k y+t_k)$ を満たす整数 $(a_k, b_k, c_k, d_k, s_k, t_k)$ を上での証明に用いた式から求めていくことで, 前計算 $O(M)$, 1クエリ当たり $O(1)$ となり, 全体で $O(N+M+Q)$ の計算量で求めることができた.

##<font color=#C0C000> F問題 (600pts, diff: 2154) </font> [Sugoroku2](https://atcoder.jp/contests/abc189/tasks/abc189_f)
まず, 不可能な場合として, 振り出しに戻るマスが $M$ マス連続していた場合, どのように移動しても $M$ マス連続している部分のうち少なくとも1マスを踏むことになるので, ゴールにたどり着くことが不可能である. 逆に, 振り出しに戻るマスが $M$ マス連続していない場合, ゴールにたどり着くマスの踏み方が少なくとも1つは存在するので, 期待値は有限になる.

振り出しに戻るマスが $M$ マス連続していないとする. $E_i~(i=0, \dots, N+M-1)$ をマス $i$ から始めたとき, ゴールするまでにルーレットを回す回数の期待値とする. 求めるべきは $E_0$ である. 自明な場合として,
$$E_N=\dots=E_{N+M-1}=0$$
である. $k=0, \dots, N-1$ に対して, マス $k$ が振り出しに戻るマスではない場合, ルーレットの出る目は等確率なので, 
$$E_k=\dfrac{1}{M} \sum_{i=1}^M E_{k+i}+1$$
である. では, 振り出しに戻るマス $k$ における $E_k$ はどのようになるか? 正解は $0$ 回ルーレットを回して確率 $1$ でマス $0$ に戻るとみなせるので, $E_k=E_0$ である. ここで, 以下に述べる方法によって, $k=0, \dots, M+N-1$ に対して,
$$E_k=\alpha_k E_0+\beta_k, (マス k が振り出しに戻るでなければ \alpha_k \neq 1)$$
なる実数 $\alpha_k, \beta_k$ を求めることができる. 

* $k=N, \dots, N+M-1$ のとき, $E_k=0E_0+0$ なので, $\alpha_k=\beta_k=0$ とすればよい.
* $l \geq k$ なる全ての整数 $l$ で成り立っているとする.
 * マス $k$ が振り出しに戻るであるとき, 上で述べたことから, $\alpha_k=1, \beta_k=0$ である.
 * マス $k$ が振り出しに戻るでなければ, $\alpha_k=\frac{1}{M} \sum_{i=1}^M \alpha_{k+i}, \beta=\frac{1}{M} \sum_{i=1}^M \beta_{k+i}+1$ である. ここで, 振り出しに戻るが $M$ マス連続しないという仮定から, $\alpha_k<1$ である.

以上から, 振り出しに戻るでないマス $k$ に対して, $E_k=\alpha_k E_0+\beta_k, \alpha_k \neq 1$ なる $\alpha_k, \beta_k$ が求められ, 特に, $k=0$ とすると, $E_0=\alpha_0 E_0+\beta_0, \alpha_0 \neq 1$ となる. よって, 求めるべき期待値は
$$E_0=\dfrac{\beta_0}{1-\alpha_0}$$
となる.

計算量は $\alpha_k, \beta_k$ を求める部分でBit木を用いて $O(N \log N)$ でも求まるが, $O(N)$ でも計算できる.

#感想
##良かった点
* 1時間弱で解くことができ, 初めての橙パフォーマンスを記録した.
* <font color=#00C0C0>E問題</font>, <font color=#C0C000>F問題</font> で多項式を持つという考え方を持つことができた.

##反省点
* <font color=#00C0C0>E問題</font>で<font color="red">1WA</font> (理由:実装ミス)
* <font color=#C0C000>F問題</font>でBit木の扱いに少しまごついた.

#記録
* Performance: <font color=#C0C000> 2202 </font> $\to$ <font color=#FF8000> 2400 </font>
* コンテスト中にACした最高diff: <font color=#C0C000> 2078 </font> $\to$ <font color=#C0C000> 2154 </font>
* ★Perfect★ までの時間 (<font color="red"> PENALTY </font> 含む): $76:08 \to 65:08$

#お知らせ
AtCoder Beginner Contest Tournament 第2期 C1ブロックにて優勝しました [[Twitter]](https://twitter.com/Kazun_kyopro/status/1352988321840910337).