Loading [MathJax]/jax/output/CommonHTML/jax.js

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

E - Takahashi Quest

問題

  • これから、冒険中の高橋君に N 個の出来事 (ti,xi) が順番に起こる
  • ti=1 のとき、タイプ xi のポーションを1つ発見する。拾うか拾わないかは自由
  • ti=2 のとき、タイプ xi のモンスターと遭遇する
    • タイプ xi のポーションを1つ消費すると倒せる
    • それ以外の場合、モンスターに敗北して高橋君の冒険は終了する
  • 全てのモンスターを倒せるか判定せよ
  • 倒せる場合、道中で保持しているポーションの個数の最大値を K として、K の最小値 Kmin とそれを実現する各ポーションの拾う・拾わないの一例を示せ
  • 1N2×105

解法

後ろから考えると楽になる問題。

後ろからだと、例えば以下のような問題に言い換えられる。

  • モンスター xi と遭遇したら、傷 xi を1回負う
  • ポーション xi を1個使うと、傷 xi を1回分治せる
  • 無傷で全出来事を終えられたらOK

道中で傷を同時に負っている最大個数が、元の問題での K に相当する。
無駄に傷を治さないでいる必要は無いので、ポーションを見つけ次第すぐに治すのが最適。
そうした場合の KKmin となる。

以下のアルゴリズムで貪欲的に処理できる。

  • d[x]:= 負っている傷 x の個数
  • モンスターと遭遇したら d[xi]+=1
  • ポーションを発見したら、d[xi]>0 なら拾って使用、d[xi]=1
  • 最終的に全てで d[x]=0 ならOK
  • 各出来事処理後の xd[x] の最大値が Kmin

Python3

F - Bomb Game 2

問題

  • 1,2,...,N が一列に並ぶ
  • 以下の処理を、列に並ぶ人が1人になるまで繰り返す
    • 先頭の人を、確率 12 で列から外し、12 で最後尾に移動させる
  • i=1,2,...,N について、人 i が最後の1人になる確率を mod998244353 で求めよ
  • 2N3000

解法

タイトルからして、多分原案は、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[n1,j] から DP[n,i] を求める時に嫌なのが、

  • n 人の時にどの人が次に外されるかで、先頭から i 番目の人が、n1 人の状態では様々な“j 番目”から始まる

ので、ただでさえ N2 ある状態で、遷移にも N かかり、全体で O(N3) となるところ。

n\i  1  2  3    n\i  1  2  3
3   ○ ○ ○    3   ○ ○ ○      DP[3,j] から DP[4,i] に
    ↓↙↙           ↘↓↙       それぞれ異なる係数がかかる
4   ○          4      ○

※ゲームの流れ的には上記の矢印の向きは逆だが、
  今は最終状態から遡ってDPを埋めているため、埋める順序で表している

だが、まぁ、上手くまとめられることを期待して、とりあえずそれぞれの係数を考えてみる。

遷移係数

Kn,i を、「n 人いて、次に列から除外されるのが先頭から i 番目の人である確率」とする。

すると、1巡目で除外される確率は「i1 まで除外されず、i で除外」の場合なので、12i である。
誰も除外されず1巡するのは 12n で、元に戻る自己ループ形式の確率となって、

  • Kn,i=12i+12nKn,i
  • Kn,i=2ni2n1

となる。要は、分子だけを見ると 2n1,...,8,4,2,1 などと末尾から2の累乗となっている。(全て合計すると 2n1

Tn,i,j を、「n 人いて、先頭から i 番目の人が生き残って、次、n1 人の状態が j 番目から始まる確率」とする。
これが、DP[n1,j] から DP[n,i] への係数となる。

Tn,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[n1,i] を引く
    • 2で割る
    • DP[n1,i]2n1 倍を足す

よって、DP[n,1] さえ O(n) で求めれば、DP[n,2] 以降は O(1) で計算でき、全体で O(N2) で求めることができる。

Python3

programming_algorithm/contest_history/atcoder/2023/1216_abc333.txt · 最終更新: 2023/12/19 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0