総合結果
- [Score] 2000 pts
- [Time] 85:39 + 05:00 $\times$ 2 = 95:39
- [Ranking] 480 th [Rated内: 265 th]
- [Performance] 1910
- [Rating] 1908 → 1908 (± 0)
各問題ごとの詳細, 提出コード
Question | Score | Time/Result | Penalty | During Contest | After Contest |
---|---|---|---|---|---|
A問題 | 100 pts | 01:04 | ■ | ||
B問題 | 200 pts | 02:50 | ■ | ||
C問題 | 300 pts | 04:16 | ■ | ||
D問題 | 400 pts | 33:37 | ■ | ||
E問題 | 500 pts | 13:18 | ■ | ||
F問題 | 500 pts | 85:39 | 2 Penalties | ■ | ■ |
G問題 | 0 pts | --:-- | |||
H問題 | 0 pts | --:-- | |||
Total | 2000 pts | 95:39 | 2 Penalties |
問題ごとの略解
A問題 (100pts, diff: 21) Lexicographic Order
入力される $2$ の文字列 $S,T$ に対して, 辞書式の意味で $S<T$ かどうかを判定すれば良い. 例えば, Python では ${\tt S<T}$ で判定できる.
B問題 (200pts, diff: 22) AtCoder Quiz
答えは $\{\alpha\}=\{{\tt ABC}, {\tt ARC}, {\tt AGT}, {\tt AHC}\} \setminus \{S_1, S_2, S_3\}$ なる $\alpha$ である. これを求めるためには様々な方法がある.
C問題 (300pts, diff: 49) Inverse of Permutation
条件は, 以下のように言い換えることができる.
- $i=1,\dots,N$ に対して, $Q_{P_i}=i$ である.
よって, $i=1, \dots, N$ の順に $Q_{P_i} \gets i$ とすればよい.
D問題 (400pts, diff: 802) Cutting Woods
数式で言い換えると, 以下のようになる.
- $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つのクエリを扱えるデータ構造が標準搭載されていないので, 自作するか, クエリ先読み+セグメント木+座標圧縮にように高度なデータ構造などのあわせ技をしなければならない.
E問題 (500pts, diff: 986) Sorting Queries
以下のようにして解くことができる.
- ヒープ $H$ とキュー $Q$ を用意する.
- クエリを順に以下のように実行する.
- クエリ $1$: $Q$ に $x$ を push する.
- クエリ $2$:
- $H$ が空でなければ, $H$ の最小値 $y$ を pop して, $y$ を出力する.
- $H$ が空でなければ, $Q$ の先頭 $y$ を pop して, $y$ を出力する.
- クエリ $3$: $Q$ の要素を全て $H$ に加える.
このようにすることで, 償却計算量 $O(Q \log Q)$ で処理できる.
F問題 (600pts, diff: 1954) Make Pair
区間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)$ で求めることができる.
G問題 (600pts, diff: 2047) Groups
(正解でき次第加筆予定)
H問題 (600pts, diff: 3112) Snuketoon
(正解でき次第加筆予定)