外部サイトへ移動します

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

別タブで開く

解説

H - Potential and World Changer

作成者 sevenc_nanashi

テスター unbakedbread

配点 500 点

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

解説

入力される譜面定数・譜面ポテンシャルは小数点以下4桁までなので、10410^4倍して整数として扱います。以下では、この整数に変換した値を使い、出力時に10410^4で割ることにします。

ポテンシャルの計算を高速に行うことを考えます。

倍率が同じ順位区間ごとに、譜面ポテンシャルの合計を求めます。r0=0r_0 = 0とおくと、ri−1+1r_{i-1}+1位からrir_i位までの倍率はwiw_iです。

ここで、関数S(x)=上位x位の譜面の譜面ポテンシャルの合計S(x) = \text{上位}x\text{位の譜面の譜面ポテンシャルの合計}を考え、S(0)=0S(0) = 0とします。ri−1+1r_{i-1}+1位からrir_i位までの合計は、累積和の差S(ri)−S(ri−1)S(r_i)-S(r_{i-1})で求められます。したがって、

ポテンシャル=∑i=1kwi(S(ri)−S(ri−1))∑i=1kwi(ri−ri−1)\text{ポテンシャル} = \frac{\sum_{i=1}^{k}w_i\bigl(S(r_i)-S(r_{i-1})\bigr)}{\sum_{i=1}^{k}w_i(r_i-r_{i-1})}

と表せます。例えば、T=((1,3),(3,2),(5,1))T = ((1, 3), (3, 2), (5, 1))ならば、分子は3S(1)+2(S(3)−S(1))+(S(5)−S(3))3S(1)+2(S(3)-S(1))+(S(5)-S(3))、分母は3×1+2×2+1×2=93\times1+2\times2+1\times2=9です。k=1k = 1の場合は、この式でS(r1)/r1S(r_1)/r_1となります。

順位区間を順に処理し、直前のS(ri−1)S(r_{i-1})を保持しておけば、S(x)S(x)をkk回求めれば計算できます。記録が00の順位も倍率の合計に含めるため、分母では譜面数をNNで打ち切らず、各区間の長さri−ri−1r_i-r_{i-1}を使います。

では、関数S(x)S(x)を高速に計算するにはどうすればよいでしょうか。

譜面ポテンシャルの最大値が140000140000(14.000014.0000)であることを利用します。累積和Segment Treeを用いると、ある点以上のポテンシャルを持つ譜面の数や、ある点以上のポテンシャルを持つ譜面の合計ポテンシャルを高速に求めることができます。

よって、以下のように関数S(x)S(x)を作ることができます:

  • Segment Tree上の二分探索で「ある点以上のポテンシャルを持つ譜面の数がxx以上になる点の中で最大のもの」を求めます。
    • ただし、x>Nx > Nの場合は、S(x)=S(N)S(x) = S(N)とします。
  • その点以上のポテンシャルを持つ譜面の合計ポテンシャルを求めます。
    • ただし、同率でxx位の譜面が複数存在する場合、譜面数がxxを超えてしまうことがあるため、その分を引く必要があります。

譜面ポテンシャルごとの譜面の数とポテンシャルの合計をそれぞれSegment Treeで管理し、また譜面ごとの記録・譜面定数をそれぞれ配列で管理します。

  • 初期状態では、全ての譜面のポテンシャルを00としてSegment Treeに登録します。
  • タイプ11のクエリでは、譜面ssの記録が更新される場合に、譜面数・合計ポテンシャルのSegment Tree、および譜面ごとの記録を更新します。
  • タイプ22のクエリでは、もし譜面ssをすでにプレイ済なら、記録に新しい譜面定数−古い譜面定数\text{新しい譜面定数}-\text{古い譜面定数}を加え、譜面数・合計ポテンシャルのSegment Tree、および譜面ごとの記録を更新します。また、プレイ済かどうかに関わらず、譜面ssの譜面定数を更新しておきます。
  • タイプ33のクエリでは、倍率表を更新します。

ポテンシャルの最大値140000140000をMAX\text{MAX}、各クエリ後の倍率表TTの長さの合計をS=∑t=1QktS = \sum_{t=1}^{Q}k_tとすると、クエリ処理の計算量はO((Q+S)log⁡MAX)O((Q + S) \log \text{MAX})となります。制約よりS≤3×105S \leq 3 \times 10^5なので、これは十分高速です。

なお、ACLのFenwick Treeを用いると計算量はO((Q+S)log⁡2MAX)O((Q + S) \log^2 \text{MAX})となり、一部の言語(特にJITがある場合)ではこちらのほうが高速になる場合があります。
Fenwick Treeでの実装例(Ruby、2076ms)

ユーザー解説

ユーザー解説を書く

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