J - K-Ba

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo
Tweet
問題
提出
テストケース
解説

概要

条件を整理して扱いやすい形にしましょう．

問題原案：uni_kakurenbo

解説

dd や vv の添え字を 0-based indexing とします．

利益を正とできるような (l,r)(l, r) の条件を考えます．

d,vd, v それぞれの累積和 D,VD, V を次のように定めます：

  • D0=V0=0D_0 = V_0 = 0
  • Dk=∑0≤i<kdk\displaystyle D_k = \sum_{ 0 \leq i < k } d_k
  • Vk=∑0≤i<kvk\displaystyle V_k = \sum_{ 0 \leq i < k } v_k

すると，22 場 l,rl, r 間について，

  • 道のり： Dr−Dl  [m]D_r - D_l \; \scriptsize \mathrm{[m]}
  • クリア時の報酬： Vr−Vl  [円]V_r - V_l \; \scriptsize \mathrm{[円]}

と表すことができます．

利益を「正」とするためには報酬 Vr−Vl  [円]V_r - V_l \; \scriptsize \mathrm{[円]} 以上の金額を改造に費やしてならないので，最大で Vr−Vl−1  [円]V_r - V_l - 1 \; \scriptsize \mathrm{[円]} まで使うことができます．
この問題を解くうえでは，必ず使える最大の金額を費やして改造することとして問題ありません．

Vr−Vl−1  [円]V_r - V_l - 1 \; \scriptsize \mathrm{[円]} を費やして改造された馬が，T  [秒]T \; \scriptsize \mathrm{[秒]} で走りきることのできる距離の最大値は T(Vr−Vl−1)  [m]T (V_r - V_l - 1) \; \scriptsize \mathrm{[m]} ですから，正の利益が期待できる組 (l,r)(l, r) は結局以下をみたすとわかります：

  • Dr−Dl≤T(Vr−Vl−1)    (l<r)D_r - D_l \leq T (V_r - V_l - 1) \;\; \scriptsize (l < r)

これを満たす l,rl, r を数えたいです．
l,rl, r が散らばっていると扱いづらいので，この条件を変形して都合よく整理します．
Dr−Dl≤T(Vr−Vl−1)⇔(TVl−Dl)≤(TVr−Dr)−TD_r - D_l \leq T (V_r - V_l - 1) \Leftrightarrow (T V_l - D_l) \leq (T V_r - D_r) - T ですから，Sk=TVk−DkS_k = T V_k - D_k とすると，最終的に条件は以下のように書けると分かります：

  • Sl≤Sr−T  (l<r)S_l \leq S_r - T \; \scriptsize (l < r)

これを満たす (l,r)(l, r) の組は，一点加算および区間和取得のできるデータ構造を用いることで数え上げられます．(転倒数を高速に求める方法に似ていると思います．)

ただし，SS の要素のとりうる範囲が広いため，Binary Indexed Tree などにそのまま乗せることは難しいです．

大小関係のみが分かればよいことに注目すると，SS および S−TS - T の値をまとめて座標圧縮し，その圧縮後の値を用いて計算を行えばよいと分かります．

O(Klog⁡K)O(K \log K) 時間などで解くことができます．

なお，制約がタイトであるため，計算量のオーダーが同程度のアルゴリズムでも定数倍によって判定が分かれる場合があります．

解説：uni_kakurenbo

実装例

C++