AtCoder Beginner Contest 217 感想

#総合結果
* [Score] 2000 pts
* [Time] 85:39 + <font color="red"> 05:00 $\times$ 2 </font> = 95:39
* [Ranking] 480 th [Rated内: 265 th]
* [Performance] <font color=#0000FF> 1910　</font>
* [Rating] <font color=#0000FF> 1908 </font> → <font color=#0000FF> 1908 </font> (± 0)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:04|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc217/submissions/25556343)||
|<font color=#808080> B問題 </font>|200 pts|02:50|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc217/submissions/25560227)||
|<font color=#808080> C問題 </font>|300 pts|04:16|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc217/submissions/25562875)||
|<font color=#008000> D問題 </font>|400 pts|33:37|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc217/submissions/25584635)||
|<font color=#008000> E問題 </font>|500 pts|13:18|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc217/submissions/25573718)||
|<font color=#0000FF> F問題 </font>|500 pts|<b>85:39</b>|<font color="red"> 2 Penalties </font>|[■](https://atcoder.jp/contests/abc217/submissions/25602930)|[■](https://atcoder.jp/contests/abc217/submissions/25617237)|
|<font color=#C0C000> G問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#FF0000> H問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>2000 pts</b>|<b>95:39</b>|<b><font color="red"> 2 Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 21) </font> [Lexicographic Order](https://atcoder.jp/contests/abc217/tasks/abc217_a)
入力される $2$ の文字列 $S,T$ に対して, 辞書式の意味で $S<T$ かどうかを判定すれば良い. 例えば, Python では ${\tt S<T}$ で判定できる.

##<font color=#808080> B問題 (200pts, diff: 22) </font> [AtCoder Quiz](https://atcoder.jp/contests/abc217/tasks/abc217_b)
答えは $\\{\alpha\\}=\\{{\tt ABC}, {\tt ARC}, {\tt AGT}, {\tt AHC}\\} \setminus \\{S_1, S_2, S_3\\}$ なる $\alpha$ である. これを求めるためには様々な方法がある.
 
##<font color=#808080> C問題 (300pts, diff: 49) </font> [Inverse of Permutation](https://atcoder.jp/contests/abc217/tasks/abc217_c)

条件は, 以下のように言い換えることができる.

* $i=1,\dots,N$ に対して, $Q_{P_i}=i$ である.

よって, $i=1, \dots, N$ の順に $Q_{P_i} \gets i$ とすればよい.

##<font color=#008000> D問題 (400pts, diff: 802) </font> [Cutting Woods](https://atcoder.jp/contests/abc217/tasks/abc217_d)

数式で言い換えると, 以下のようになる.

* $S=\\{0,L\\}$ とする.
* クエリ $(c_1, x_1), \dots, (c_Q, x_Q)$ を順に処理せよ.
    * $c_q=1$ のとき: 集合 $S$ に $x_q$ を加えよ.
    * $c_q=2$ のとき: 集合 $S$ の要素のうち, $x$ より大きい最小の整数を $r$, $x$ より小さい最大の整数を $l$ としたとき, $r-l$ を出力せよ.

このクエリの要求を達成するためには, 例えば順序つき集合を用いれば高速にクエリにたいする処理を行うことができる.

ただし, Python 系の場合, この2つのクエリを扱えるデータ構造が標準搭載されていないので, 自作するか, クエリ先読み+セグメント木+座標圧縮にように高度なデータ構造などのあわせ技をしなければならない.

##<font color=#008000> E問題 (500pts, diff: 986) </font> [Sorting Queries](https://atcoder.jp/contests/abc217/tasks/abc217_e)

以下のようにして解くことができる.

* ヒープ $H$ とキュー $Q$ を用意する.
* クエリを順に以下のように実行する.
    * クエリ $1$: $Q$ に $x$ を push する.
    * クエリ $2$:
        * $H$ が空でなければ, $H$ の最小値 $y$ を pop して, $y$ を出力する.
        * $H$ が空でなければ, $Q$ の先頭 $y$ を pop して, $y$ を出力する.
    * クエリ $3$: $Q$ の要素を全て $H$ に加える.

このようにすることで, 償却計算量 $O(Q \log Q)$ で処理できる.

##<font color=#0000FF> F問題 (600pts, diff: 1954) </font>[Make Pair](https://atcoder.jp/contests/abc217/tasks/abc217_f)

区間DPで解くことにする. $1 \leq L \leq R \leq 2N+1$ に対して, ${\rm DP}[L,R]$ で

* ${\rm DP}[L,R]:=$ (問題を右半開区間 $[L,R)$ に制限したの場合の場合の数

とする. また, $1 \leq x < y \leq 2N$ に対して,

$$T[x,y]=\begin{cases} 1 & (\exists j {\rm ~s.t.~} (x,y)=(A_j, B_j)) \\\\ 0 & {\rm otherwise} \end{cases}$$

と定義する. つまり, $x,y$ がペアとして取り除けるならば $1$, そうでなければ $0$ である.

ベースケースとして, $L=R$ のときは ${\rm DP}[L,R]=1$ とする.

遷移を考える. ここで, 人 $L$ がどの人とペアになるかで場合分けする. なお, 2人ずつ取り除くことから, 人 $L$ と人 $t$ がペアになるとして,

* $L < t < R$
* $t-L$ :奇数 ($t-L+1$ が偶数になっていなければいけないので)

を満たしていなければならない.  上の条件を満たす $t$ を固定する. この条件下での場合の数は

* $T[L,t]=1$ でなくてはいけない
* $(L,t)$ のペアで取り除く場合, $[L,R)$ は2つの区間 $[L+1, t), [t+1, R)$ に分割される.
* $\\{L,t\\}, [L+1, t), [t+1, R)$ をそれぞれチーム A,B,C と呼ぶことにし, $a:=1, b:=\frac{t-L-1}{2}, c:=\frac{R-t-1}{2}$ とする (それぞれのチーム内でできるペアの数).
* このとき, ペアを作る順番をチーム毎の目線で見ると, 以下の事がわかる.
    * A, B, C 内でそれぞれ $a,b,c$ 回ペアを作る
    * B チーム内で $b$ 回ペアを作った後, A チーム内でペアを作る.
* A,B,C を $a,b,c$ 個並べる並べ方のうち, どの B も A より先になるような並べ方の数は $\dbinom{a+b+c}{a+b}=\dbinom{\frac{R-L}{2}}{\frac{t-L+1}{2}}$ である.
* B チーム内でのペアの作り方は ${\rm DP}[L+1,t]$ 通り, C チーム内でのペアの作り方は ${\rm DP}[t+1,R]$ 通りである.
* B チーム, C チーム内のペアの作り方は他方に影響を与えない.

以上のことから, ${\rm DP}[L,R]$ は

$${\rm DP}[L,R]=\sum_{\substack{L < t \leq R \\\\ t-L: {\rm odd}}} \left(T[L,t] \times {\rm DP}[L+1,t] \times {\rm DP}[t+1,R] \times \dbinom{\frac{R-L}{2}}{\frac{t-L+1}{2}} \right)$$

である.

よって, この動的計画法における ${\rm DP}[1,2N+1]$ が答えであり, この値は $O(N^3)$ で求めることができる.

##<font color=#C0C000> G問題 (600pts, diff: 2047) </font>[Groups](https://atcoder.jp/contests/abc217/tasks/abc217_g)

(正解でき次第加筆予定)

##<font color=#FF0000> H問題 (600pts, diff: 3112) </font>[Snuketoon](https://atcoder.jp/contests/abc217/tasks/abc217_h)

(正解でき次第加筆予定)