ABC 236 E — Average and Median

考察

平均や中央値そのものを最大化する代わりに、「ある値以上にできるか」を考える。すると、どちらもカードごとの重みの和で判定できる。隣り合う二枚をともに選ばないことだけが禁止されているので、重みの最大和は直前のカードを選んだかどうかの二状態DPで求められる。

条件を満たす選び方を全列挙するのは難しい。たとえば偶数番目をすべて選べば奇数番目は自由に選べるので、合法な選び方だけでも指数個ある。一方、目標値を下げれば達成しやすくなるため、目標値を固定した判定が速く解ければ二分探索につながる。

以下では、選んだカードの添字集合を SS、目標値を KK とする。N≥2N\geq2 なので、最初の隣接対だけを見ても少なくとも一枚は選ばなければならず、SS は空にならない。

平均の条件を和へ変える

平均は総和を枚数で割った値である。正の枚数 ∣S∣|S| を払えば、平均を状態に持たずに済む。

∑i∈SAi∣S∣≥K⟺∑i∈S(Ai−K)≥0\frac{\sum_{i\in S}A_i}{|S|}\geq K \quad\Longleftrightarrow\quad \sum_{i\in S}(A_i-K)\geq0

そこで各カードの重みを wi=Ai−Kw_i=A_i-K とする。合法な選び方で重みの和を最大化し、その最大値が 0以上 なら、平均を KK 以上にできる。

下側中央値の条件を個数差へ変える

中央値には総和が使えないので、各値が閾値のどちら側にあるかに注目する。選んだカードのうち、KK 以上の枚数を pp、KK 未満の枚数を qq とする。

本問の中央値は、小さい方から ⌈(p+q)/2⌉\lceil(p+q)/2\rceil 番目である。小さい値がこの順位まで届かなければ中央値は KK 以上なので、条件は次のようになる。

q<⌈p+q2⌉⟺p>qq<\left\lceil\frac{p+q}{2}\right\rceil \quad\Longleftrightarrow\quad p>q

したがって、Ai≥KA_i\geq K なら wi=1w_i=1、それ以外なら wi=−1w_i=-1 とすればよい。重みの和は p−qp-q となり、その最大値が 0より大きい ときだけ成功する。偶数枚で両者が同数なら下側の中央は KK 未満なので、平均と同じ「0以上」にはできない。

直前の選択だけを残して最大和を求める

ここからは、どちらの変換でも同じDPを使える。先頭 ii 枚について選ぶかどうかを決め、その中の隣接対の条件を満たす選び方を考える。

  • fif_i:ii 枚目を選ぶ場合の、選んだ重みの和の最大値。
  • gig_i:ii 枚目を選ばない場合の、選んだ重みの和の最大値。

未来の選択に影響するのは直前の一枚を選んだかだけである。同じ状態に達した選び方なら、重みの和が最大のものだけを残してよい。

境界用に f0=g0=0f_0=g_0=0 と置き、i=1,2,…,Ni=1,2,\ldots,N の順に次を計算する。

fi=max⁡(fi−1,gi−1)+wi,gi=fi−1.\begin{aligned} f_i&=\max(f_{i-1},g_{i-1})+w_i,\\ g_i&=f_{i-1}. \end{aligned}

現在を選べば直前はどちらでもよく、現在を選ばなければ直前を選ぶ必要がある。添字0は実在するカードの選択を表すものではなく、一枚目を自由に選ぶための初期値である。実際、f1=w1, g1=0f_1=w_1,\ g_1=0 となり、一枚目だけを選ばないことも許される。二枚目以降は非選択を続けられないので、最後まで空集合が残ることはない。

配列全体を持つ必要はないが、更新は必ず旧二値から同時に行う。実装の流れは次の擬似コードになる。

f = 0
g = 0
各カード i = 1, 2, ..., N について:
    next_f = max(f, g) + w_i
    next_g = f
    (f, g) = (next_f, next_g)
return max(f, g)

先に f を上書きしてから g = f とすると、一つ前の状態を参照できない。終了時は最後を選ぶ義務がないので、fNf_N だけでなく F(K)=max⁡(fN,gN)F(K)=\max(f_N,g_N) を使う。この値を平均では F(K)≥0F(K)\geq0、中央値では F(K)>0F(K)>0 と判定する。

たとえば A=(1,2,1,1), K=2A=(1,2,1,1),\ K=2 の中央値判定では、重みは (−1,1,−1,−1)(-1,1,-1,-1) となる。各段階の最大和は次のとおりである。

処理した枚数 iifif_igig_i
000
1-10
21-1
301
400

最大和は0なので判定は失敗する。たとえば二枚目と四枚目を選べば和0になるが、選んだ値は1と2であり、下側中央値は1である。2は一枚しかなく、隣接条件を満たすには1も少なくとも一枚必要なので、正の個数差は作れない。

最後に、平均・中央値それぞれについて成功する最大の閾値を二分探索する。同じ選び方のまま閾値を下げれば条件は保たれるので、どちらの判定も成功側から失敗側へ一度だけ切り替わる。具体的な探索境界と平均の精度は「実装上の注意」で定める。

典型の発動条件

平均・中央値の答え二分探索

発動条件: 選択集合上の平均または中央値を最大化し、候補値以上という条件が加法的に書けるとき。変換後の和を制約内で最大化できれば、その値を判定に使える。

平均は分母となる選択枚数が正であること、中央値は採用する順位と必要な個数差を確認する。変換後に必要な処理は選択制約によって変わり、本問ではDPがその役割を担う。

連続非選択禁止の二状態 DP

発動条件: 各隣接対の少なくとも一方を選ぶという局所制約の下で重み和を最大化するとき。

未来に必要な情報が直前の選択だけなら、それより前の履歴を捨て、各状態の最大和だけを保持できる。重みが負でも、非選択を続ける遷移は作れない。

問題固有の要素

下側中央値の定義により、閾値以上のカードが厳密に過半数必要になる。また、両端のカードは選ばなくてもよい。隣接対への条件を、先頭や末尾を必ず選ぶ条件と取り違えないことが重要である。

たとえば A=(10,1), K=5A=(10,1),\ K=5 の平均判定では、f2=1, g2=5f_2=1,\ g_2=5 となる。一枚目だけを選ぶ最適解を拾うには、終了時に両状態の最大を取る必要がある。

正当性

一枚目の二通りを表す初期値から出発する。先頭部分の合法な選び方は、最後を選ぶか選ばないかで二状態に分かれる。現在を選ぶものは直前のどちらの状態からも作れ、選ばないものは直前を選んだ状態からだけ作れる。逆にこれらの遷移は新たな隣接条件を必ず満たす。同じ状態からの今後の選択肢は等しいので、各状態で最大和だけを残しても最適解を失わず、最後に両状態の最大を取れば全合法集合上の最大和が得られる。

合法集合は非空なので、平均の不等式では選択枚数を払う変形が成立する。下側中央値の順位条件は閾値以上の枚数が未満の枚数より多いことに等しい。従って、DPの最大和による平均の非負判定と中央値の厳密な正判定は、それぞれ目標値以上を実現する集合の存在と同値である。

閾値を下げても同じ集合で成功するため、二分探索は成功・失敗の境界を保てる。平均を千倍した整数閾値で探索すると終了値は最適平均の千倍の床となり、元の尺度へ戻した誤差は千分の一未満になる。中央値は整数なので、隣り合う整数境界まで探索した成功側が厳密な最適値になる。

実装上の注意

ここでは平均も整数演算で判定する。m=min⁡iAi, M=max⁡iAim=\min_i A_i,\ M=\max_i A_i と置く。

  • 平均の探索:整数閾値を QQ とし、重みを wi=1000Ai−Qw_i=1000A_i-Q に変える。DPの最大和が0以上であることは、平均を Q/1000Q/1000 以上にできることと同値である。成功側を L=1000mL=1000m、失敗側を R=1000M+1R=1000M+1 として始める。
  • 中央値の探索:整数閾値 KK に対する ±1\pm1 の重みを使い、DPの最大和が正かを調べる。成功側を L=mL=m、失敗側を R=M+1R=M+1 として始める。

どちらも全カードを選べば下端は成功し、最大値を超える上端は失敗する。R−L>1R-L>1 の間、中央の整数 ⌊(L+R)/2⌋\lfloor(L+R)/2\rfloor を判定し、成功なら LL、失敗なら RR をその値へ更新する。DPの二値は判定のたびに0へ初期化する。

最適平均を α\alpha とすると、平均の終了値は L=⌊1000α⌋L=\lfloor1000\alpha\rfloor であり、次が保証される。

0≤α−L1000<10−30\leq\alpha-\frac{L}{1000}<10^{-3}

一行目には L/1000L/1000 を小数として出力する。整数除算だけで出力すると小数部を失うので、たとえば L=5250L=5250 なら 5.250 とする。整数の商と余りを使い、小数部を必ず三桁で出してもよい。二行目には中央値の探索で得た整数 LL をそのまま出力する。

平均側では探索端点が最大 1012+110^{12}+1、判定で使う重みの絶対値が 101210^{12} 以下、DPの和の絶対値が 101710^{17} 以下になる。C++なら倍率を掛ける前に long long へ変換し、端点・重み・DP値をすべて符号付き64 bit整数で持つ。中央値側の和の絶対値は NN 以下である。

復習の核

  • 平均の最大化では、閾値を固定して正の分母を払い、要素ごとの重みの和へ変えられないかを考える。
  • 中央値の閾値変換は順位の定義から導く。下側中央値では同数を成功にせず、個数差が正かを調べる。
  • 局所制約のDPでは、未来に必要な直前の情報だけを残す。更新は旧状態から行い、終了条件で許される全状態を比べる。

計算量と制約

時間

一回の判定は NN 枚を走査するので O(N)O(N)。平均は O(log⁡(1000M))O(\log(1000M)) 回、中央値は O(log⁡M)O(\log M) 回の判定を行い、入力読込を含めて全体は O(Nlog⁡(1000M))O(N\log(1000M))。

空間

各判定のDPは直前の二値だけを持つので補助領域は O(1)O(1)。二分探索のたびに入力配列を読み直すため、その保持を含む全体の空間は O(N)O(N)。

制約との対応

公式制約は 2≤N≤105, 1≤Ai≤1092\leq N\leq10^5,\ 1\leq A_i\leq10^9、制限時間2秒、メモリ1024 MiB。平均の探索は高々40回、中央値は高々30回の判定で終わり、合計で高々 70N70N 枚分の更新になる。N≥2N\geq2 が空集合の除外を保証し、平均の出力誤差は許容される絶対誤差 10−310^{-3} 未満に収まる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Average and Median の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: fractional programming・比率parametric search

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

    主タグ: fractional programming・比率parametric search

    補助タグ: DPの最小十分状態

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

    学習の位置

    体系上の位置: fractional programming・比率parametric search

    • 比率候補xをbenefit-x·costの加法目的へ変換し、単調な判定問題を解いて最適比率を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題