Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 263 F問題 Tournament

AtCoder ABC ABC263 F問題 500 pts

問題

提出解答

問題の概要

人 $1$ , $\dots$ , 人 $2^N$ の $2^N$ 人からなるじゃんけん大会がある. このじゃんけん大会は次の形式で開催される.

参加者を人 $1$ , $\dots$ , 人 $2^N$ の順に横 $1$ 列に並べる.
次のことを回繰り返す ( 回目).
- $l=1,2, \dots, 2^{N-j}$ に対して, 左から $(2l-1)$ 人目と $2l$ 人目がじゃんけんし, 負けた人は列から抜ける.

終了後, 人 $i$ がちょうど $j$ 回勝つと $C_{i,j}$ 円が得られる. ただし, $C_{i,j}=0$ である.

$2^N$ 人が得られる賞金の総和の最大値を求めよ.

制約

$1 \leq N \leq 16$
$1 \leq C_{i,j} \leq 10^9$

解法

説明のため, 第 $j$ 回戦いおける $b=1,2, \dots, 2^{N-j}$ における人 $2^j (b-1)+1, \dots,$ 人 $2^j b$ の集団をブロック $b$ と呼ぶことにする. このとき, 各ブロックからは必ず1人ずつが勝ち上がる.

動的計画法で解く. $j=0,1,2, \dots, N$ 及び, $i=0,1,\dots, 2^N-1$ に対して, ${\rm DP}[j,i ]$ を以下で定める.

$j=0$ のときは $0$ .
$j \geq 1$ のときは第 $j$ 回終了後に人 $i$ が属するブロックにおいて, 人 $i$ が勝ち抜けた場合の残りの $(2^j-1)$ 人が得られる賞金の最大値

また, $j=1,2, \dots, N$ 及び, $b=1,2,\dots, 2^{N-j}$ $H(j,b)$ を

第 $(j+1)$ 回戦ちょうどで第 $j$ 回戦におけるブロック $b$ にいる $2^j$ 人が全滅で全滅する場合にこの $2^j$ 人が得られる賞金の総和の最大値

とする.

このとき, $\displaystyle H(j,b)=\max_{2^j b \leq k \lt 2^j(b+1)} \left({\rm DP}[j-1, k]+C_{k,j} \right)$ である. これを利用することにより, 第 $j$ 回戦目に人 $i$ と対決することになる対戦相手が属するブロックの番号 (これは $j,i$ から一意に定まる) を $b'$ としたとき,

${\rm DP}[j,i]={\rm DP}[j-1, i]+H(j,b')$

となる.

この動的計画法により, 求めるべき最終解答は

$\displaystyle \max_{i=1,2, \dots, 2^N} \left({\rm DP}[N,i]+C_{i,N} \right)$

である. 計算量も $O(N 2^N)$ 時間で求められる.