解説
クリアまでの期待時間
練習後の区間 i の成功率を pi とし、最初の i 区間を連続で成功するまでにかかる時間の期待値を Ei とします。
区間 i に挑戦するためには、まず区間 i−1 までを突破する必要があります。その後、区間 i のプレイに 1 単位時間がかかり、確率 1−pi で最初からやり直すことになります。
したがって、
Ei=Ei−1+1+(1−pi)Ei
が成り立ちます。整理すると、
Ei=piEi−1+1
を得ます。初期条件は E0=0 です。
この漸化式を展開すると、求める期待値は
EN=i=1∑Npipi+1⋯pN1
となります。
貪欲法
区間 i の現在の難易度を di とし、si=1000−di とおきます。このとき pi=si/1000 であり、区間 i を 1 回練習することは si を 1 増やすことに対応します。
ここで、期待値の減少量が最大となる区間を 1 回練習するという操作を繰り返す貪欲法を考えます。
区間 i を練習したときの期待値の減少量を Δi とします。
EN の各項のうち、pi を分母に含む項は、練習によって si+1si 倍になります。
したがって、
Δi=si+11j=1∑ipjpj+1⋯pN1
です。
ここで、
Pi=j=1∏ipj,P0=1
および
Si=j=0∑i−1Pj
と定義すると、
Δi=PN1si+1Si
となります。
PN1 はすべての区間に共通であるため、si<1000 である区間のうち、
si+1Si
が最大となる区間を選んで練習すればよいです。
貪欲法の正当性
以下、交換法により貪欲法の正当性を示します。
まず、二つの区間 a,b (a<b) に対して、練習による期待値の減少量の比を考えます。
ΔbΔa=sa+1sb+1SbSa(1)
また、
SaSb=1+j=0∑a−1Pjj=a∑b−1Pj
です。分子・分母を Pa−1 で割ると、
SaSb=1+j=0∑a−1∏k=j+1a−1pk1j=a∑b−1k=a∏jpk
となります。ただし、空積は 1 とします。
成功率を増加させると、この分数の分子は単調非減少であり、分母は単調非増加です。
したがって、各区間の成功率を増加させたとき、SaSb は単調非減少となります。
この性質を用いて、ある時点で貪欲法が選ぶ区間を i とします。
残りの練習を最適に割り振った結果を考えます。この割り振りに区間 i の練習が含まれているならば、最初に区間 i を練習しても最適解が得られます。
以下、区間 i に対する練習が含まれていないと仮定します。
最適な割り振りにおいて、練習を行う区間のうち番号が最小のものを j とし、区間 j に対する練習を 1 回だけ取り除いた状態を考えます。
この状態において、区間 j を練習する代わりに区間 i を練習しても、期待値が悪化しないことを示します。
j<i の場合
式 (1) より、
ΔiΔj=sj+1si+1SiSj
です。
区間 i は練習されていないため si は変化していません。一方、sj は単調非減少であり、先ほど示した性質より SiSj は単調非増加です。
したがって、ΔiΔj は貪欲法で区間 i を選んだ時点の値以下になります。
その時点では Δi≥Δj だったため、現在も Δi≥Δj が成り立ちます。
i<j の場合
式 (1) より、
ΔjΔi=si+1sj+1SjSi
です。
j は練習を行う区間のうち番号が最小のものなので、区間 1,2,…,j−1 の成功率は変化していません。
したがって、Si,Sj,si は変化せず、sj のみが単調非減少です。
よって ΔjΔi は貪欲法で区間 i を選んだ時点の値以上になり、現在も Δi≥Δj が成り立ちます。
以上より、いずれの場合も、区間 j に対する練習を 1 回取り除き、代わりに区間 i を練習しても期待値は悪化しません。
したがって、貪欲法で選んだ区間を練習するような最適解が必ず存在します。
これを残りの練習回数について繰り返すことで、貪欲法の正当性が示されました。
実装・計算量
各練習について、累積積とその累積和を用いることで、すべての区間の si+1Si を O(N) 時間で計算できます。
si<1000 である区間のうち、この値が最大となるものを選び、si を 1 増やします。
これを最大 K 回繰り返します。すべての区間の難易度が 0 となった場合は、その時点で終了してよいです。
最後に、
E0=0,Ei=si1000(Ei−1+1)
を順に計算し、EN を出力します。
以上より、時間計算量 O(N(K+1))、空間計算量 O(N) でこの問題を解くことができました。