ABC 280 E — Critical Hit

考察

攻撃列のdamage累積は1または2ずつ狭義増加し、N damage以上に初めて達する攻撃回数が求める停止時刻である。

threshold iとi+1へ到達する攻撃回数の差は0か1で、その期待差は累積damageがちょうどiを訪れる確率になる。

採用する候補: damage累積がちょうどiを訪れる確率p_iを漸化式p_0=1,p_i=1-(P/100)p_{i-1}で求め、Σ_{i=0}^{N-1}p_iを取る。

棄却する候補: 攻撃回数ごとに残りstaminaの全確率分布を更新し、終了確率から期待値を合計する。

解けるが二次元分布を持つ必要がなく、訪問確率の一次元recurrenceより状態が多い。

q=P·inv(100)を法上で作り、p=1,ans=0からi=0,…,N-1でans+=p、p=1-q·pと更新する。最後のansを998244353で出力する。

典型の発動条件

停止時刻のtail/indicator和

発動条件: 単調過程がthresholdへ達するまでのstep期待値を求めるとき。

各中間levelを訪れたindicatorの和として停止回数を表し、期待値を足す。

overshootの補事象recurrence

発動条件: step幅が小さく、特定levelを飛び越す経路が直前levelからの1patternに限られるとき。

訪問失敗を直前訪問×長step確率として更新する。

問題固有の要素

damageが1/2だけなのでlevel iを飛ばすにはi-1から2を出すしかなく、訪問確率が1つ前だけで閉じる。

別の問題へ持ち帰る視点: 単調random walkのhit確率では、最大step幅からovershoot直前の候補状態数を調べる。

正当性

iを訪れない唯一の形はi-1を訪れた直後にdamage2で飛び越すことなので、p_i=1-q p_{i-1}(q=P/100)となる。 停止までの攻撃回数はdamage level 0,…,N-1のうち実際に訪れたlevel数に一致し、期待値の線形性で訪問確率の和になる。 期待停止時刻を各threshold訪問indicatorの和へ分解し、1次元の定数遷移だけで計算できる。

実装上の注意

  • p_iをanswerへ足してからp_{i+1}へ更新し、0からN-1までちょうどN項を合計する。
  • P=0,100でも同じ式が使えることを小例で確認し、負剰余1-q·pを正規化する。

復習の核

  • p_0=1,p_1=1-q,p_2=1-q(1-q)をpathで列挙し、『iを飛ばす』補事象が重複しない理由を確認する。

計算量と制約

時間

O(N)、訪問確率p_iの一次漸化式。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2\times 10^5; 0 \leq P \leq 100; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Critical Hit の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 寄与の数え上げと順序交換

    補助タグ: 法上の四則演算・高速累乗・逆元 確率・期待値DP

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

    この解説で扱わないこと:

    • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題