目次
トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）E,F問題メモ
E - Takahashi Quest
問題
- これから、冒険中の高橋君に $N$ 個の出来事 $(t_i,x_i)$ が順番に起こる
- $t_i=1$ のとき、タイプ $x_i$ のポーションを1つ発見する。拾うか拾わないかは自由
- $t_i=2$ のとき、タイプ $x_i$ のモンスターと遭遇する
- タイプ $x_i$ のポーションを1つ消費すると倒せる
- それ以外の場合、モンスターに敗北して高橋君の冒険は終了する
- 全てのモンスターを倒せるか判定せよ
- 倒せる場合、道中で保持しているポーションの個数の最大値を $K$ として、$K$ の最小値 $K_{min}$ とそれを実現する各ポーションの拾う・拾わないの一例を示せ
- $1 \le N \le 2 \times 10^5$
解法
後ろから考えると楽になる問題。
後ろからだと、例えば以下のような問題に言い換えられる。
- モンスター $x_i$ と遭遇したら、傷 $x_i$ を1回負う
- ポーション $x_i$ を1個使うと、傷 $x_i$ を1回分治せる
- 無傷で全出来事を終えられたらOK
道中で傷を同時に負っている最大個数が、元の問題での $K$ に相当する。
無駄に傷を治さないでいる必要は無いので、ポーションを見つけ次第すぐに治すのが最適。
そうした場合の $K$ が $K_{min}$ となる。
以下のアルゴリズムで貪欲的に処理できる。
- $d[x]:=$ 負っている傷 $x$ の個数
- モンスターと遭遇したら $d[x_i]+=1$
- ポーションを発見したら、$d[x_i]>0$ なら拾って使用、$d[x_i]-=1$
- 最終的に全てで $d[x]=0$ ならOK
- 各出来事処理後の $\sum_x d[x]$ の最大値が $K_{min}$
F - Bomb Game 2
問題
- 人 $1,2,...,N$ が一列に並ぶ
- 以下の処理を、列に並ぶ人が1人になるまで繰り返す
- 先頭の人を、確率 $\frac{1}{2}$ で列から外し、$\frac{1}{2}$ で最後尾に移動させる
- $i=1,2,...,N$ について、人 $i$ が最後の1人になる確率を $\mod{998244353}$ で求めよ
- $2 \le N \le 3000$
解法
タイトルからして、多分原案は、1/2で爆発する爆弾を渡していく感じだった？
DP
$DP[n,i]$ を、「$n$ 人いて、先頭から $i$ 番目の人が最後まで生き残る確率」とする。
$n=1$ のとき、明らかに $DP[1,1]=1$ で、そこから $n$ を増やしていきたい。各 $i$ に対する $DP[N,i]$ が答え。
n\i 1 2 3 ... 1 1 2 ? ? 3 ? ? ? 4 ? ? ? ?
$DP[n-1,j]$ から $DP[n,i]$ を求める時に嫌なのが、
- $n$ 人の時にどの人が次に外されるかで、先頭から $i$ 番目の人が、$n-1$ 人の状態では様々な“$j$ 番目”から始まる
ので、ただでさえ $N^2$ ある状態で、遷移にも $N$ かかり、全体で $O(N^3)$ となるところ。
n\i 1 2 3 n\i 1 2 3
3 ○ ○ ○ 3 ○ ○ ○ DP[3,j] から DP[4,i] に
↓↙↙ ↘↓↙ それぞれ異なる係数がかかる
4 ○ 4 ○
※ゲームの流れ的には上記の矢印の向きは逆だが、
今は最終状態から遡ってDPを埋めているため、埋める順序で表している
だが、まぁ、上手くまとめられることを期待して、とりあえずそれぞれの係数を考えてみる。
遷移係数
$K_{n,i}$ を、「$n$ 人いて、次に列から除外されるのが先頭から $i$ 番目の人である確率」とする。
すると、1巡目で除外される確率は「$i-1$ まで除外されず、$i$ で除外」の場合なので、$\dfrac{1}{2^i}$ である。
誰も除外されず1巡するのは $\dfrac{1}{2^n}$ で、元に戻る自己ループ形式の確率となって、
- $K_{n,i}=\dfrac{1}{2^i}+\dfrac{1}{2^n}K_{n,i}$
- $K_{n,i}=\dfrac{2^{n-i}}{2^n-1}$
となる。要は、分子だけを見ると $2^{n-1},...,8,4,2,1$ などと末尾から2の累乗となっている。（全て合計すると $2^n-1$）
$T_{n,i,j}$ を、「$n$ 人いて、先頭から $i$ 番目の人が生き残って、次、$n-1$ 人の状態が $j$ 番目から始まる確率」とする。
これが、$DP[n-1,j]$ から $DP[n,i]$ への係数となる。
$T_{n,i,j}$ は、$i$ より $j$ 人前の人が除外される確率なので、
n=5 除外される人 その確率（Tnij）の分子（分母は 2^n-1 = 31） i\j 1 2 3 4 i\j 1 2 3 4 1 5 4 3 2 1 1 2 4 8 2 1 5 4 3 2 16 1 2 4 3 2 1 5 4 3 8 16 1 2 4 3 2 1 5 4 4 8 16 1 5 4 3 2 1 5 2 4 8 16
こんな感じになる。
つまり、DPの遷移は以下のような感じになる。
DP[n,i]
n\i 1 2 3 4 n\i 1 2 3 4 n\i 1 2 3 4
4 ○ ○ ○ ○ 4 ○ ○ ○ ○ 4 ○ ○ ○ ○
x1 x2 x4 x8 x16 x1 x2 x4 x8 16 x1 x2 ...
↓↙↙ ↙ ↘↓↙↙ ↘↘↓↙
5 ○ 5 ○ 5 ○
（※それぞれさらに 1/31 倍するが、表記上は省略）
よく見ると、$DP[5,1]$ を愚直に計算すると、$DP[5,2]$ はその結果から計算できることがわかる。
- $DP[5,1]→DP[5,2]$ の求め方
- $DP[4,1]$ を引く
- 2で割る
- $DP[4,1]$ の16倍を足す
- $DP[5,2]→DP[5,3]$ の求め方
- $DP[4,2]$ を引く
- 2で割る
- $DP[4,2]$ の16倍を足す
- …
- $DP[n,i]→DP[n,i+1]$ の求め方
- $DP[n-1,i]$ を引く
- 2で割る
- $DP[n-1,i]$ の $2^{n-1}$ 倍を足す
よって、$DP[n,1]$ さえ $O(n)$ で求めれば、$DP[n,2]$ 以降は $O(1)$ で計算でき、全体で $O(N^2)$ で求めることができる。
