外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

W - Nyaometry Dash

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、trueryob

配点 650 点

実行時間制限
2 秒
メモリ制限
512 MiB

解説

クリアまでの期待時間

練習後の区間 ii の成功率を pip_i とし、最初の ii 区間を連続で成功するまでにかかる時間の期待値を EiE_i とします。

区間 ii に挑戦するためには、まず区間 i−1i-1 までを突破する必要があります。その後、区間 ii のプレイに 11 単位時間がかかり、確率 1−pi1-p_i で最初からやり直すことになります。

したがって、

Ei=Ei−1+1+(1−pi)EiE_i=E_{i-1}+1+(1-p_i)E_i

が成り立ちます。整理すると、

Ei=Ei−1+1piE_i=\frac{E_{i-1}+1}{p_i}

を得ます。初期条件は E0=0E_0=0 です。

この漸化式を展開すると、求める期待値は

EN=∑i=1N1pipi+1⋯pNE_N=\sum_{i=1}^N\frac{1}{p_i p_{i+1}\cdots p_N}

となります。

貪欲法

区間 ii の現在の難易度を did_i とし、si=1000−dis_i=1000-d_i とおきます。このとき pi=si/1000p_i=s_i/1000 であり、区間 ii を 11 回練習することは sis_i を 11 増やすことに対応します。

ここで、期待値の減少量が最大となる区間を 11 回練習するという操作を繰り返す貪欲法を考えます。

区間 ii を練習したときの期待値の減少量を Δi\Delta_i とします。

ENE_N の各項のうち、pip_i を分母に含む項は、練習によって sisi+1\frac{s_i}{s_i+1} 倍になります。

したがって、

Δi=1si+1∑j=1i1pjpj+1⋯pN\Delta_i= \frac{1}{s_i+1} \sum_{j=1}^{i} \frac{1}{p_jp_{j+1}\cdots p_N}

です。

ここで、

Pi=∏j=1ipj,P0=1P_i=\prod_{j=1}^{i}p_j,\qquad P_0=1

および

Si=∑j=0i−1PjS_i=\sum_{j=0}^{i-1}P_j

と定義すると、

Δi=1PNSisi+1\Delta_i=\frac{1}{P_N}\frac{S_i}{s_i+1}

となります。

1PN\frac{1}{P_N} はすべての区間に共通であるため、si<1000s_i<1000 である区間のうち、

Sisi+1\frac{S_i}{s_i+1}

が最大となる区間を選んで練習すればよいです。

貪欲法の正当性

以下、交換法により貪欲法の正当性を示します。

まず、二つの区間 a,ba,b (a<ba<b) に対して、練習による期待値の減少量の比を考えます。

ΔaΔb=sb+1sa+1SaSb(1)\frac{\Delta_a}{\Delta_b} = \frac{s_b+1}{s_a+1}\frac{S_a}{S_b} \tag{1}

また、

SbSa=1+∑j=ab−1Pj∑j=0a−1Pj\frac{S_b}{S_a} = 1+ \frac{\displaystyle\sum_{j=a}^{b-1}P_j} {\displaystyle\sum_{j=0}^{a-1}P_j}

です。分子・分母を Pa−1P_{a-1} で割ると、

SbSa=1+∑j=ab−1∏k=ajpk∑j=0a−11∏k=j+1a−1pk\frac{S_b}{S_a} = 1+ \frac{ \displaystyle\sum_{j=a}^{b-1} \prod_{k=a}^{j}p_k }{ \displaystyle\sum_{j=0}^{a-1} \frac{1}{\prod_{k=j+1}^{a-1}p_k} }

となります。ただし、空積は 11 とします。

成功率を増加させると、この分数の分子は単調非減少であり、分母は単調非増加です。

したがって、各区間の成功率を増加させたとき、SbSa\frac{S_b}{S_a} は単調非減少となります。

この性質を用いて、ある時点で貪欲法が選ぶ区間を ii とします。

残りの練習を最適に割り振った結果を考えます。この割り振りに区間 ii の練習が含まれているならば、最初に区間 ii を練習しても最適解が得られます。

以下、区間 ii に対する練習が含まれていないと仮定します。

最適な割り振りにおいて、練習を行う区間のうち番号が最小のものを jj とし、区間 jj に対する練習を 11 回だけ取り除いた状態を考えます。

この状態において、区間 jj を練習する代わりに区間 ii を練習しても、期待値が悪化しないことを示します。

j<ij<i の場合

式 (1)(1) より、

ΔjΔi=si+1sj+1SjSi\frac{\Delta_j}{\Delta_i} = \frac{s_i+1}{s_j+1}\frac{S_j}{S_i}

です。

区間 ii は練習されていないため sis_i は変化していません。一方、sjs_j は単調非減少であり、先ほど示した性質より SjSi\frac{S_j}{S_i} は単調非増加です。

したがって、ΔjΔi\frac{\Delta_j}{\Delta_i} は貪欲法で区間 ii を選んだ時点の値以下になります。

その時点では Δi≥Δj\Delta_i\ge\Delta_j だったため、現在も Δi≥Δj\Delta_i\ge\Delta_j が成り立ちます。

i<ji<j の場合

式 (1)(1) より、

ΔiΔj=sj+1si+1SiSj\frac{\Delta_i}{\Delta_j} = \frac{s_j+1}{s_i+1}\frac{S_i}{S_j}

です。

jj は練習を行う区間のうち番号が最小のものなので、区間 1,2,…,j−11,2,\ldots,j-1 の成功率は変化していません。

したがって、Si,Sj,siS_i,S_j,s_i は変化せず、sjs_j のみが単調非減少です。

よって ΔiΔj\frac{\Delta_i}{\Delta_j} は貪欲法で区間 ii を選んだ時点の値以上になり、現在も Δi≥Δj\Delta_i\ge\Delta_j が成り立ちます。

以上より、いずれの場合も、区間 jj に対する練習を 11 回取り除き、代わりに区間 ii を練習しても期待値は悪化しません。

したがって、貪欲法で選んだ区間を練習するような最適解が必ず存在します。

これを残りの練習回数について繰り返すことで、貪欲法の正当性が示されました。

実装・計算量

各練習について、累積積とその累積和を用いることで、すべての区間の Sisi+1\frac{S_i}{s_i+1} を O(N)O(N) 時間で計算できます。

si<1000s_i<1000 である区間のうち、この値が最大となるものを選び、sis_i を 11 増やします。

これを最大 KK 回繰り返します。すべての区間の難易度が 00 となった場合は、その時点で終了してよいです。

最後に、

E0=0,Ei=1000(Ei−1+1)siE_0=0,\qquad E_i=\frac{1000(E_{i-1}+1)}{s_i}

を順に計算し、ENE_N を出力します。

以上より、時間計算量 O(N(K+1))O(N(K+1))、空間計算量 O(N)O(N) でこの問題を解くことができました。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。