ABC 341 G — Highest Ratio

考察

区間の平均は、累積和を表す二点を結ぶ直線の傾きと見なせる。傾きを最大にする右端を探すには、点集合の上側の境界だけを残せばよい。さらに左端を右から動かすと、境界を作り直さずに更新できる。

まず左端 kk ごとに右端 rr をすべて試すと、累積和で各平均を定数時間で計算しても全体で O(N2)O(N^2) かかる。N≤2×105N\leq 2\times 10^5 では、右端の候補を絞る必要がある。

配列 A1,…,ANA_1,\ldots,A_N は問題文どおり1始まりとし、累積和と点は0始まりで

S0=0,Si=∑j=1iAj,Pi=(i,Si)(0≤i≤N)S_0=0,\qquad S_i=\sum_{j=1}^{i}A_j,\qquad P_i=(i,S_i)\quad(0\leq i\leq N)

と定める。区間 [k,r][k,r] の平均は

Sr−Sk−1r−(k−1)\frac{S_r-S_{k-1}}{r-(k-1)}

であり、Pk−1P_{k-1} から PrP_r への傾きに一致する。従って Pk−1,Pk,…,PNP_{k-1},P_k,\ldots,P_N の中で、最左点から右側の点への最大傾きを求めればよい。

この点集合の上側凸包、つまり全点を下側に含む凸な折れ線を考える。最左点から上側凸包の最初の辺を延長すると、すべての候補点はその直線上か下側にある。従って、その辺の右端への傾きが最大になる。必要なのは上側凸包の最左点に隣接する頂点だけである。

左端を一つ左に動かすと、対象の点集合には新しい最左点が一つ増える。このため PN,PN−1,…,P0P_N,P_{N-1},\ldots,P_0 の順に追加し、上側凸包の頂点をスタック hull で維持する。スタックは先頭から末尾へ x 座標の降順に並べる。追加する点を pp、追加前の末尾二点を順に a,ba,b とすると、横の並びは p,b,ap,b,a となる。

外積は cross⁡(u,v)=uxvy−uyvx\operatorname{cross}(u,v)=u_xv_y-u_yv_x と定義する。この向きでの判定値は

C=cross⁡(b−a,p−b)C=\operatorname{cross}(b-a,p-b)

である。mpbm_{pb} を pp から bb への傾き、mbam_{ba} を bb から aa への傾きとすると、

C=(xa−xb)(xb−xp)(mpb−mba)C=(x_a-x_b)(x_b-x_p)(m_{pb}-m_{ba})

となる。上側の凸な折れ線では左から右へ辺の傾きが減るので、残したいのは mpb>mbam_{pb}>m_{ba}、すなわち C>0C>0 の曲がりである。逆に C≤0C\leq 0 なら、bb は線分 papa の上には出ないため除ける。特に C=0C=0 では三点が共線であり、中点 bb を消しても pp からの傾きは aa で同じ値を得られる。さらに左から見ても線分上の中点が両端より大きい傾きを与えることはなく、将来の答えも失わない。

以上から、手順は次のように固定できる。

  1. 累積和を作り、hull を空にする。i=N,N−1,…,0i=N,N-1,\ldots,0 の順に処理する。
  2. 新点を p=Pip=P_i とする。hull に二点以上あり、末尾二点 a,ba,b に対して cross⁡(b−a,p−b)≤0\operatorname{cross}(b-a,p-b)\leq 0 である間、末尾の bb を pop する。pop 後の末尾二点で同じ判定を繰り返す。
  3. PiP_i を push する。i=Ni=N なら点を置くだけで、答えは求めない。
  4. i<Ni<N なら、push 直後の末尾は PiP_i、その一つ前は右側の隣接頂点 PjP_j である。次の値を保存する。
ans[i+1]=Sj−Sij−i\mathrm{ans}[i+1]=\frac{S_j-S_i}{j-i}

例えば A=(1,3,2)A=(1,3,2) なら、累積和の点は P0=(0,0),P1=(1,1),P2=(2,4),P3=(3,6)P_0=(0,0),P_1=(1,1),P_2=(2,4),P_3=(3,6) である。以下ではスタックを先頭から末尾の順で示す。

  • P3P_3 を追加すると、hull は [P3][P_3]。まだ答えは求めない。
  • P2P_2 を追加すると、hull は [P3,P2][P_3,P_2]。末尾二点から ans[3]=(6−4)/(3−2)=2\mathrm{ans}[3]=(6-4)/(3-2)=2 を得る。
  • P1P_1 を追加するときは C=1>0C=1>0 なので pop せず、hull は [P3,P2,P1][P_3,P_2,P_1]。ans[2]=(4−1)/(2−1)=3\mathrm{ans}[2]=(4-1)/(2-1)=3 を得る。
  • P0P_0 を追加するときは C=−2C=-2 なので P1P_1 を除く。次の判定は C=0C=0 となり、共線の P2P_2 も除く。push 後の hull は [P3,P0][P_3,P_0] で、ans[1]=(6−0)/(3−0)=2\mathrm{ans}[1]=(6-0)/(3-0)=2 を得る。

左端の順に出力すると答えは (2,3,2)(2,3,2) となる。最後の処理では P2P_2 を消したが、P0P2P_0P_2 と P0P3P_0P_3 の傾きはともに2なので、最大平均は保たれている。

典型の発動条件

prefix sum幾何

連続区間の平均や比率が「累積和の差 ÷ 長さ」で表されるとき、累積和の添字を x 座標、値を y 座標にして、右端選択を傾きの最大化へ変換できる。

monotone convex hull

点が x 座標順に追加され、凸包の端の隣接辺を求めたいとき、不要な曲がりを外積で除くスタックが使える。走査方向と残す側を先に決め、それに合う外積の符号を導く。任意順の追加や、凸包の端以外からの問い合わせへ同じ手順をそのまま使うことはできない。

問題固有の要素

左端 kk の問い合わせに必要なのは、累積和の点 Pk−1,…,PNP_{k-1},\ldots,P_N が作る上側凸包である。kk を右から減らすと、この接尾辞の点集合には最左点が一つ追加されるだけになる。この順序なら、全左端に対する凸包を一つのスタックの更新過程で扱える。

別の問題へ持ち帰る視点は、問い合わせの候補集合が入れ子なら、走査方向を変えて「削除」や「作り直し」を「追加」へ置き換えられないかを考えることである。

正当性

処理済みの点の上側凸包を、x 座標の降順にスタックへ保持する。新点 p=Pip=P_i は常に全処理済み点より左にある。末尾の a,ba,b に対して外積が0以下なら、bb は線分 papa の上には出ない。従って、今後さらに左に置く点から見ても、bb への傾きは p,ap,a への傾きの大きい方を超えず、最大値の候補から除ける。等号の場合も最大値は変わらない。末尾でこの除去を繰り返して新点を追加すると、全処理済み点を下側に含む上側凸包が保たれる。

上側凸包を左から読むと辺の傾きは減少するので、最左点 PiP_i からの最初の辺を延長した直線より上に候補点はない。この辺の右端で傾きの最大値を達成するため、追加直後のスタックの末尾とその一つ前の点から求めた値が ans[i+1]\mathrm{ans}[i+1] に等しい。i=Ni=N では候補区間がなく点だけを置き、i<Ni<N では右側の点が少なくとも一つ残る。よって N=1N=1 や全点が共線の場合を含め、すべての左端について正しい最大平均を得る。

実装上の注意

  • 外積の判定は整数で行う。SN≤2×1011S_N\leq 2\times 10^{11}、x 座標差は 2×1052\times 10^5 以下なので、各積の絶対値は 4×10164\times 10^{16} 以下、差の絶対値も 8×10168\times 10^{16} 以下である。符号付き64 bit整数に収まり、掛け算の前にその型へそろえる。
  • pop 条件はこの点順・外積の定義で C≤0C\leq 0 とする。全要素が等しい場合も共線の中点を除き、両端から同じ平均を得られる。
  • i=Ni=N では問い合わせない。i<Ni<N の答えは、新点を push した後の末尾二点から読み、1始まりの ans[i+1]\mathrm{ans}[i+1] へ保存する。j>ij>i なので分母は正になる。
  • 最後の除算を double などの浮動小数点数で行い、整数除算を避ける。答えは左端の昇順に、小数点以下10桁程度で出力すれば、要求される絶対誤差または相対誤差 10−610^{-6} に対応できる。

復習の核

  • 区間平均が現れたら「累積和の差 ÷ 添字の差」を書き、二点間の傾きとして候補を眺める。
  • 接尾辞ごとに同じ構造を求めたいなら、右から走査して一要素ずつ追加する形を探す。
  • 凸包の pop 不等号は暗記せず、点の左右関係と、上側に残したい辺の傾きの大小から復元する。共線の中点を消せるのは、ここでは最大値だけが必要だからである。

計算量と制約

時間

O(N)O(N)。累積和の構築と出力はそれぞれ O(N)O(N)。凸包の更新では、各点を一度だけ push し、pop も各点につき高々一度なので、while の全反復を合わせても O(N)O(N) となる。点は既に x 座標順のためソートは不要である。

空間

O(N)O(N)。累積和、上側凸包のスタック、各左端の答えを保存する。

制約との対応

1≤N≤2×1051\leq N\leq 2\times 10^5、1≤Ai≤1061\leq A_i\leq 10^6。全体を線形時間で処理でき、累積和と外積も符号付き64 bit整数で正確に扱える。N=1N=1 のときは P1P_1 を置いた後に P0P_0 を追加し、唯一の平均 A1A_1 を得る。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Highest Ratio の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 凸包・支持方向・境界候補

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

      主タグ: 凸包・支持方向・境界候補

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

      学習の位置

      体系上の位置: 凸包・支持方向・境界候補

      • 目的関数に対して内部候補が不要な理由を示し、凸境界だけを列挙できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題