mini notes

競技プログラミングの解法メモを残していきます。

第一回 アルゴリズム実技検定 O - 持久戦

問題:O - Endurance

解答:Submission #10095653 - 第一回 アルゴリズム実技検定 過去問

メモ: 各試行で現れるサイコロの目を数列にすると、狭義単調増加になる。 特に、全てのサイコロの中で最も大きい目を出すと、その時点で操作終了となる。

サイコロを区別せずに、xをサイコロの目としたときdp[x]を「そのサイコロの目が出た後にサイコロが何回振れるか」という値とする。このとき dp[x]の値はy>xなるyについてのdp[y]が分かれば算出できる。

サンプル1での計算過程はこんな感じ。各サイコロごとにdp値と各サイコロの期待回数を保持しながら合計を更新してゆく。

f:id:misora192:20200215082055j:plain
考察メモ