0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

AtCoder Beginner Contest 217 感想

Posted at

総合結果

  • [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

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?