AtCoder Beginner Contest 190 感想

##総合結果
* [Score] 1600 pts
* [Time] 45:04 + <font color="red"> 05:00 $\times$ 0 </font>=45:04
* [Ranking] 767 th [Rated内: 561 st]
* [Performance] <font color=#0000FF> 1668　</font>
* [Rating] <font color=#0000FF> 1866 </font> → <font color=#0000FF> 1847 </font> (-19)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 01:58
* <font color=#808080> B問題 </font> 03:47
* <font color=#804000> C問題 </font> 07:43
* <font color=#804000> D問題 </font> 13:47 
* <font color=#0000FF> E問題 </font> <font color=#FF0000> TLE $\times$ 3</font>
* <font color=#00C0C0> F問題 </font> 45:04

##提出コード(コンテスト後提出 (▲) 含む)
* <font color=#808080> A問題 </font> [■](https://atcoder.jp/contests/abc190/submissions/19773078)
* <font color=#808080> B問題 </font> [■](https://atcoder.jp/contests/abc190/submissions/19776013)
* <font color=#804000> C問題 </font> [■](https://atcoder.jp/contests/abc190/submissions/19782251)
* <font color=#804000> D問題 </font> [■](https://atcoder.jp/contests/abc190/submissions/19782251)
* <font color=#0000FF> E問題 </font> [▲](https://atcoder.jp/contests/abc190/submissions/19819402)
* <font color=#00C0C0> F問題 </font> [■](https://atcoder.jp/contests/abc190/submissions/19803088)

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 14) </font> [Very Very Primitive Game](https://atcoder.jp/contests/abc190/tasks/abc190_a)

$C=0$ , つまり, 高橋くん先行のとき, 高橋くんが勝つための必要十分条件は, $A>B$ である. 逆に, $C=1$ , つまり, 高橋くん高校のとき, 高橋くんが勝つための必要十分条件は $A \geq B$ である. ここで, $A \geq B$ について, $A,B$ は整数なので, $A+1>B$ と同値である. よって, 高橋くんが勝つための必要十分条件は $A+C>B$ とひとまとめにできる.

なお, $A,B \leq 100$ という制約から, 実際にシミュレーションしてもよい.

##<font color=#808080> B問題 (200pts, diff: 21) </font> [Magic 3](https://atcoder.jp/contests/abc190/tasks/abc190_b)
ダメージを与えることのできる必要十分条件は, $X_i < S$ かつ $Y_i > D$ を満たす整数 $i$ が存在することである. これは ${\tt for}$ 文で $i=1, \dots, N$ とすることによって調べることができる.

##<font color=#804000> C問題 (300pts, diff: 472) </font> [Bowls and Dishes](https://atcoder.jp/contests/abc190/tasks/abc190_c)
各人はボールは皿 $A_i$ に置くか, 皿 $B_i$ に置くかの2択を迫られている. よって, $K$ 人が取りうる可能性は $2^K$ 通りであり, 各ボールの置き方について満たされる条件の数は $O(M)$ で調べられるので, 全体の計算量 $O(2^K(K+M+N))$ で求めることができた.

##<font color=#804000> D問題 (400pts, diff: 722) </font> [Staircase Sequences](https://atcoder.jp/contests/abc190/tasks/abc190_d)
初項が $a$, 公差が $1$, 項数が $n$ である等差数列の総和 $S$ は
$$S=\sum_{k=1}^n (a+k-1)=\dfrac{1}{2}n(2a+n-1)$$
である. よって, $n(2a+n-1)=2N$ を満たす整数 $a$ と自然数 $n$ が解答になる. ここで, $n$ は $2N$ の約数に限られ, このとき, $a=\dfrac{\frac{2N}{n}-l+1}{2}$ が整数になれば適合である. よって, $2N$ の約数の全列挙に $O(\sqrt{2N})=O(\sqrt{N})$, 適合かどうかの判定に1つの約数あたり $O(1)$ でできるので, 全体の計算量は $O(\sqrt{N})$ になる.

##<font color=#0000FF> E問題 (500pts, diff: 1645) </font> [Magical Ornament](https://atcoder.jp/contests/abc190/tasks/abc190_e)
$M=\\{1, \dots, N\\}, E=\\{A_1 B_1, \dots, A_M B_M\\}$ とする. この問題は以下と同値である.

> グラフ $G=(V,E)$ において, $K$ 個の頂点 $C=(C_1, \dots, C_K)$ を全て通る最短の歩道の頂点数を求めよ. 

2頂点 $u,v$ 間の距離を $d(u,v)$ と書くことにする. 頂点  $C_i$ を始点とするBFSを実行することによって, $d(C_i, C_j)~(j=1, \dots, K)$ を計算量 $O(N+M)$ で求めることができる.

以下, $C$ を全て通る最短の歩道の頂点数を求める. bit-DP で求める. $S \subset C, v \in C$ [^e1] として, ${\rm DP}[S,v]$ を
$${\rm DP}[S,v]:=S内の全ての点を通り, vで終わる歩道のうち, 最短なものの頂点数~(存在しないならば \infty)$$
とする. このとき,
$${\rm DP}[\\{C_i\\}][v]=\begin{cases} 1 & (C_i=v) \\\\ \infty & (C_i \neq v) \end{cases}$$
という自明な解と関係式
$${\rm DP}[S,v]=\min_{w \in C} ({\rm DP}[S \setminus \\{w\\}][w]+d(w,v))$$
から, $\min_{v \in C} {\rm DP}[C, v]$ が答えである. 計算量は $K$ 回のBFS と $K$ 頂点におけるBitDPの計算量をあわせて $O(K^2 2^K+K(N+M))$ である.

[^e1]: $C$ は数列であるが, 全て異なるという条件から, 集合とみなしても問題ない.

##<font color=#00C0C0> F問題 (600pts, diff: 1321) </font> [Shift and Inversions](https://atcoder.jp/contests/abc190/tasks/abc190_f)
数列 $B^{(k)}$ を $B^{(k)}\_i:=a_{i+k {\rm ~mod~} N}$ で定義される列とする. ここで, 定性的に, $B^{(k+1)}$ は $B^{(k)}$ の初項を末項に移動させた数列であることがわかる. ここで, $X^{(k)}$ で $B^{(k)}$ の転倒数とする.

$X^{(k)}$ が求まっているとする. ここから $X^{(k+1)}$ を求めたい. $B^{(k)}$ の初項を $p_{k}=B^{(k)}\_0$ とする. ここで, $p_k$ は $B^{(k)}$ の初項なので, $X^{(k)}$ のうち, $p_k$ が寄与しているのは $B^{(k)}$ が順列であることから, $p_k$ である. よって, $p_k$ を末項に移動させると, $X^{(k)}$ に寄与していた $p_k$ 分は全て消える. 逆に, 残りの $N-p_k-1$ 個は末項に移動させると, 位置関係が変更するので, $X^{(k+1})$ に新たに $N-p_k-1$ だけ加わることがわかる.

以上から,
$$X^{(k+1)}=X^{(k)}-p_k+(N-p_k-1)=X^{(k)}+(N-2p_k-1)$$
であることがわかる.

最後に, $X^{(0)}$ を求めたい. $X^{(0)}$ は定義から
$$X^{(0)}=\sum_{i=0}^{N-1} \sum_{j=i+1}^{N-1} \left[B^{(0)}\_i > B^{(0)}\_j \right]$$
であるが, これは
$$X^{(0)}=\sum_{i=0}^{N-1} \sum_{k=B^{(0)}\_i+1}^{N-1} \left[k は B^{(0)}\_0, \dots, B^{(0)}\_{i-1} に存在する \right]$$
と同じである. よって, 以下のように Bit木を用いて計算することによって, $X^{(0)}$ を $O(N \log N)$ で求めることができる.

* 長さ $N$ の列 $T$ を $0$ で初期化する.
* $i=0, \dots, N-1$ に対して以下を順次実行する.
 * $X^{(0)}$ に $\sum_{k=B^{(0)}_i+1}^{N-1} T_k$ を加算する.
 * $T_{B^{(0)}_i}$ に $1$ を加算する.
* $X^{(0)}$ が答えである.

よって, 以上のことから $X^{(0)}, \dots, X^{(N-1)}$ を $O(N \log N)$ で求めることができた.

#感想
##良かった点
* 順位表の状況から <font color=#00C0C0> F問題 </font> 問題を先に解くことができた.

##反省点
* <font color=#0000FF> E問題 </font> で高速なプログラムを組むことができなかった.