トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）E,F問題メモ

トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）

ぞろめ！

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}$

Python3

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[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)$ で求めることができる。

Python3