競技プログラミング用 知識集積所
ABC421E - Yacht
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
n回目の結果を見てn+1回目の行動を決めるあたり、露骨に動的計画法。
問題は、DPテーブルとして何のデータをもつか。
値のほうは「その状況での期待値」だとしても、キーの方を何にするかが難しい。
「各目が何個キープ済か」をキーにするのが要素数最小にはなるだろうが、次の段階での計算がややしづらい。
問題は、DPテーブルとして何のデータをもつか。
値のほうは「その状況での期待値」だとしても、キーの方を何にするかが難しい。
「各目が何個キープ済か」をキーにするのが要素数最小にはなるだろうが、次の段階での計算がややしづらい。
そこで、サイコロ1つごとに
- 事前にその目が出ていて、キープ済（6通り）
- 今回その目が出た（6通り）
- まだ目が確定していない
の13個の状態を定義することにする。
これを使って、残りサイコロ回数4通り*（13通りの状態）^5の約150万要素をもつ6次元vector※としてしまえばよい。
これを使って、残りサイコロ回数4通り*（13通りの状態）^5の約150万要素をもつ6次元vector※としてしまえばよい。
DPテーブル埋めは、
- 残り0回のところは、map※などを用いて愚直に点数を計算する
- 「今回出た」や「未確定」があるところは、最後の1回でもキープしなかったという状況なので0点でいい
- 残り1回以上のところは、
- 「未確定」がある場合、そのサイコロで各目が出た場合6通りの期待値の平均
- それ以外は、「今回出た」のところを「キープして/せずに進む」の2択*最大5セットで前の情報を見て全探索し、期待値の最大値を探す
で埋めることができる。
キープする/しないの選択も加味しても、6^5+19^5*3のおよそ740万回のループでテーブルが埋まる。
ただ、このアイデアをそのまま実装すると、11重ループ※になるので、考えどころではあるかもしれない。
ただ、このアイデアをそのまま実装すると、11重ループ※になるので、考えどころではあるかもしれない。
