AtCoder Beginner Contest 188 感想

##総合結果
* [Score] 2100 pts (★Perfect★)
* [Time] 81:56+<font color="red"> 05:00 $\times$ 1 </font>=86:56
* [Ranking] 271 st [Rated内: 166th]
* [Performance] <font color=#C0C000> 2045　</font>
* [Rating] <font color=#0000FF> 1779 </font> → <font color=#0000FF> 1809 </font> (+30)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 01:10
* <font color=#808080> B問題 </font> 02:45
* <font color=#808080> C問題 </font> 07:11
* <font color=#008000> D問題 </font> 28:31 
* <font color=#008000> E問題 </font> 46:32 <font color="red"> (+1 PENALTY) </font>
* <font color=#0000FF> F問題 </font> 81:56 

##提出コード(コンテスト後提出含む)
* <font color=#808080> A問題 </font> [■](https://atcoder.jp/contests/abc188/submissions/19312468)
* <font color=#808080> B問題 </font> [■](https://atcoder.jp/contests/abc188/submissions/19316782)
* <font color=#808080> C問題 </font> [■](https://atcoder.jp/contests/abc188/submissions/19323659)
* <font color=#008000> D問題 </font> [■](https://atcoder.jp/contests/abc188/submissions/19334841)
* <font color=#008000> E問題 </font> [■](https://atcoder.jp/contests/abc188/submissions/19340318)
* <font color=#0000FF> F問題 </font> [■](https://atcoder.jp/contests/abc188/submissions/19365780)

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 8) </font> [Three-Point Shot](https://atcoder.jp/contests/abc188/tasks/abc188_a)
劣勢のチームがスリーポイントシュートを決めてもう一方のチームの得点を真に上回るための必要十分条件は
$$\min(X,Y)+3 > \max(X,Y)$$
である.

##<font color=#808080> B問題 (200pts, diff: 15) </font> [Orthogonality](https://atcoder.jp/contests/abc188/tasks/abc188_b)
${\tt for}$ 文を用いて, 愚直に $\sum_{k=1}^N A_k B_k=0$ かどうかを調べれば良い. コーナーケースもない.

##<font color=#808080> C問題 (300pts, diff: 120) </font> [ABC Tournament](https://atcoder.jp/contests/abc188/tasks/abc188_c)
$m=0,1,\dots,N$ に対して, 長さ $2^m$ の数列 $X^{(m)}=\left(X^{(m)}\_i \right)\_{i=1}^{2^m}$ を以下で定義する.
$$X^{(m)}\_i:=\begin{cases} A_i & (m=N) \\\\ \max \left(X^{(m+1)}\_{2i-1},X^{(m+1)}\_{2i} \right) & (m \leq N) \end{cases} $$
このとき, $X^{(m)}$ は Round of $2^m$[^C1] に参加できる人で戦う人が条件に合うようにならんでいる. よって, $X^{(1)}\_1, X^{(1)}\_2$ の2人で決勝を行い, $X^{(0)}\_1$ の人が優勝である. よって, 求めるべき答え $k$ は
$$ A_k=\min \left(X^{(1)}_1, X^{(1)}_2 \right)$$
を満たす $1$ 以上 $2^N$ 以下の整数 $k$ である.

[^C1]: $2^m$ 人から $2^{m-1}$ 人に減るラウンド
##<font color=#008000> D問題 (400pts, diff: 933) </font> [Snuke Prime](https://atcoder.jp/contests/abc188/tasks/abc188_d)
まず, 各日について, 利用したいサービスの総料金が $C$ 円以上ならば, すぬけプライムに加入することによって, $C$ 円に抑えることができる. よって, 求めるべき答えは $i$ 日目に利用したいサービスの総料金を $p_i$ としたとき,
$$\sum_{i=1}^{10^9} \min(C,p_i)$$
が答えである. しかし, $i=1,\dots,10^9$ について, $p_i$ を求めていては間に合わない.

そこで, Imos法と座標圧縮を用いて, $p_i$ を求めていく.
$i$ 番目のサービスを利用したい日時の区間は半開区間 $[a_i,b_i+1)$ とみなせる. そこで, $X$ を $\\{a_1,b_1+1,\dots,a_N,b_N+1 \\}$ から重複を取り除いて昇順に並べた列とする. なお, 以下では $X$ の要素数は $K+1$ であるとし, 各項を $x_0 \leq \dots \leq x_K$ とする.

このとき, 開区間 $I_s$ を $I_s:=[x_{s-1}, x_s)$ とする. $x_0, \dots, x_K$ について, 以下の事がわかる.

* $1 \leq s,t \leq K$ に対して, $s \neq t$ ならば, $I_s \cap I_t =\emptyset$
* 任意の $i$ に対して, 以下を満たすような $\lambda_i, \mu_i$ が存在する.
$$[a_i, b_i+1)=\bigcup_{l=\lambda_i}^{\mu_i} I_l$$

各区間にImos法を用いて計上していく. 長さ $K+1$ の数列の各項 $(E_j)\_{j=1}^{K+1}$ を $0$ に初期化する. 次に, 各 $i$ に対して, 上でとれる $\lambda_i, \mu_i$ に対して,
$$E\_{\lambda_i} \leftarrow E\_{\lambda_i}+c_i,\quad E\_{\mu_i+1} \leftarrow E\_{\mu_i+1}-c_i$$
とし, $N$ 個の計算を終えたあと, $(F_j)\_{j=1}^K$ を
$$F_j:=\begin{cases} E_1 & (j=1) \\\\ F_{j-1}+E_j & (j>1) \end{cases}$$
とすると, 各 $F_j$ は区間 $I_j$ におけるサービス料金の総和と一致する. 従って,
$$\sum_{k=1}^K (X_k-X_{k-1}) \min (C,F_k) $$
が答えである. 計算量は $X$ を求める際のソートがボトルネックになって, $O(N \log N)$ である.

##<font color=#008000> E問題 (500pts, diff: 1170) </font> [Peddler](https://atcoder.jp/contests/abc188/tasks/abc188_e)

頂点集合 $V$ を $V:=\{1,\dots,N\}$, 辺集合 $E$ を $E:=\\{X_i \to Y_i| i=1,\dots,N\\}$ とした有向グラフ $D$ を考える. このとき, $X_i<Y_i$ という制約から, この $D$ はDAGであることがわかる. ここで, ${\rm DP}[i]~(i=1,\dots,N)$ を町 $i$ から到達可能な町での金の価格の最大値と, これを求めていく. ただし, $d^-(v)$ を頂点 $v$ における出次数とする.

$${\rm DP}[i]:=\begin{cases} &-\infty & (d^-(i)=0) \\\\ \max \\{A_j|町iから到達可能な町j\\} && (d^-(i)>0) \end{cases}$$

これを求めるためには, 以下のような手順で計算していけば良い. ただし, $N^-(i)$ で頂点 $i$ の入近傍全体の集合とする.

* $i=N, N-1, \dots, 1$ の順に以下を実行する.
 * $j \in N^-(i)$ に対して, 以下を実行する: ${\rm DP}[j]$ を $\min ({\rm DP}[j],{\rm DP[i]}, A[i])$ に更新する.

この様にして求めた ${\rm DP}$ を用いて, 正解は
$$\max\_{i=1,\dots,N} \left({\rm DP}[i]-A[i] \right)$$
である.

##<font color=#0000FF> F問題 (600pts, diff:1865) </font> [+1-1x2](https://atcoder.jp/contests/abc188/tasks/abc188_f)
この問題は逆変換を考えることにより, 以下の問題と同等である: $Y$ に $+1, -1, \div 2$(偶数のときのみ) を何回か施して, $X$ にしたい. 最小何回必要か?

以下 $f(y)$ を上の問題文において, $Y$ を $y$ に置き換えた時の答えとする. つまり, $f(Y)$ が求めるべき答えである.

まず, 自明な場合として, $y \leq X$ のとき, 数を真に大きくするという操作は $+1$ しかできない. よって, $f(y)=X-y$ である.

次に, $y>X$ のとき, $y$ から $X$ への変換について, 以下のように2つに場合分けする.

* $\div 2$ を1回もしない変換について, このとき, $\pm 1$ だけしかできないので $-1$ を $y-X$ 回するのが最適である. よって, このパターンにおける最小回数は $y-X$ である.
* $\div 2$ を1回でもする変換について, 最初に $\div 2$ をする前の整数を $p$ (偶数) とする. このとき, 最適な変換は $|p-y|<2$ を見たす. もし, $|p-y| \geq 2$ だった場合, $p \geq y$ とすると, $y$ 以上 $p$ 未満の偶数 $s$ が存在する. このとき,  $p$で $\div 2$ をする変換は $p/2$ に到達するのに $p-y+1$ 回 [^F1], $s$ で $\div 2$ をする変換は $(s-x)+1+(p/2-s/2)$[^F2] 回であるが,
$$ (s-x)+1+(p/2-s/2)=\dfrac{p+s}{2}-x+1<\dfrac{p+p}{2}-x+1=p-x+1$$
より, $s$ で $\div 2$ をする変換のほうが真に回数を小さくすることができる. また, $p \leq x$ の場合も同様である. 以上から, $y$ 以下の最大の偶数を $u$, $x$ 以上の最小の偶数を $v$ としたとき, このパターンにおける最小回数は
$$\min (f(u/2)+(y-u)+1, f(v/2)+(v-y)+1)$$
である.

以上より, $y>X$ のとき,
$$f(y)=\min (y-X, f(u/2)+(y-u)+1, f(v/2)+(v-y)+1)$$
であることがわかった.

計算量について考察する. $Y$ から計算される $u,v$ について, $|u-v| \leq 2$ なので, $|u/2-v/2| \leq 1$ となる. よって, $Y$ での再帰に呼び出される2つの引数は同じか連続した整数である.

ここで, 2つの連続した整数 $y, y+1$ に対して, $y$ のときに計算される $u,v$ を $u_1,v_1$, $y+1$ のときに計算される $u,v$ を $u_2,v_2$ とすると, $v_1=u_2$ であり, $y, y+1$ のうちの一方は偶数なので, $|u_1-v_2| \leq 2$ になる.

以上から, 各段階で引数に入る整数は高々2つなので, 計算量 $O(\log Y)$ で求めることができる.

###補足
この問題は AtCoder Grand Contest 044 <font color=#0000FF>A問題</font> [Pay to Win](https://atcoder.jp/contests/agc044/tasks/agc044_a) において, $A=D=1, B=C=\infty$ とし, 始点を $1$ から $X$ にしたものである.

[^F1]: $+1$ を $p-x$ 回, $\div 2$ を 1回
[^F2]: $+1$ を $s-x$ 回, $\div 2$ を 1回, $+1$ を $p/2-s/2$ 回
#感想
##良かった点
* 初めてコンテストに参加したときに打ちのめされた問題 ([URL](https://qiita.com/Kazun_kyopro/items/ce222d6756603849279a)) にリベンジを果たすことができた.
 
##反省点
* 全体的に解法の決定に迷いが生じてしまい, 調子が上がらなかった (特に, <font color=#008000>D問題</font>, <font color=#0000FF>F問題</font>).
* Eで<font color="red"> PENALTY </font> を発生させてしまった.