ABC 294 F — Sugar Water 2

考察

候補の濃度以上になる混ぜ方の個数が分かれば、濃い方から何番目かを判定できる。砂糖量から「候補の濃度に達するために必要な砂糖量」を引くと、混合後の条件を二つの容器の寄与の和に分けられる。

全ての混ぜ方を作って濃度順に並べると、最大 NM=2.5×109NM=2.5\times 10^9 組になる。そこで、順位そのものを探す代わりに「ある濃度以上の組が KK 個以上あるか」を考える。その濃度を高くするほど条件は厳しくなるため、この判定には二分探索が使えそうだ。残る課題は、全組を調べずに個数を数えることである。

以後、候補濃度 xx は百分率ではなく、砂糖の質量を砂糖水の総質量で割った 0≤x≤10\leq x\leq 1 の比率とする。例えば x=0.5x=0.5 が50%に対応する。高橋君の容器 ii は砂糖 AiA_i グラム・水 BiB_i グラム、青木君の容器 jj は砂糖 CjC_j グラム・水 DjD_j グラムを含む。添字の範囲は 1≤i≤N1\leq i\leq N、1≤j≤M1\leq j\leq M とする。

混ぜた後の比率が xx 以上という条件を式にしよう。総質量は正なので、分母を払っても不等号の向きは変わらない。

Ai+CjAi+Bi+Cj+Dj≥x\frac{A_i+C_j}{A_i+B_i+C_j+D_j}\geq x

分母を払い、右辺を左辺へ移すと、

Ai+Cj−x(Ai+Bi+Cj+Dj)≥0\begin{aligned} &A_i+C_j\\ &\quad-x(A_i+B_i+C_j+D_j)\geq 0 \end{aligned}

ここで総質量に xx を掛けた量は、その総質量で候補濃度を満たすために必要な砂糖量である。容器ごとに「実際の砂糖量からこの必要量を引いた値」をスコアとして定義する。

ui=Ai−x(Ai+Bi),vj=Cj−x(Cj+Dj)\begin{aligned} u_i&=A_i-x(A_i+B_i), \\ v_j&=C_j-x(C_j+D_j) \end{aligned}

これで混合条件は ui+vj≥0u_i+v_j\geq 0 となる。例えば x=0.5x=0.5 のとき、砂糖4グラム・水1グラムのスコアは 1.51.5、砂糖1グラム・水4グラムのスコアは −1.5-1.5 である。和は0なので、二つを混ぜるとちょうど50%になる。濃度そのものを足すのではなく、質量の単位を持つスコアを足している。

公式解説は、砂糖 ss グラム・水 tt グラムに対し、水の量を固定して濃度 xx にするための砂糖量 tx/(1−x)tx/(1-x) を考え、余剰 s−tx/(1−x)s-tx/(1-x) を使う。本稿のスコアとの関係は、0≤x<10\leq x<1 で

s−x(s+t)=(1−x)(s−tx1−x)s-x(s+t)=(1-x)\left(s-\frac{tx}{1-x}\right)

である。固定した xx では全容器に同じ正数 1−x1-x を掛けているので、スコアの大小関係も、二つの和の符号も同じになる。以降は除算のない ui,vju_i,v_j を使う。公式解説の余剰の式は x=1x=1 では評価できないが、本稿の式は端点でも定義できる。

固定した xx で青木君のスコアを昇順に整列した配列を VV とし、その位置は0始まりとする。高橋君の容器 ii に対し、混ぜられる相手は vj≥−uiv_j\geq -u_i を満たすもの全てである。lower_bound(V, -u_i) が返す最初の位置を pip_i、該当要素がなければ pi=Mp_i=M とすれば、その個数は M−piM-p_i になる。従って

count(x)=∑i=1N(M−pi)\mathrm{count}(x)=\sum_{i=1}^{N}(M-p_i)

を求めればよい。等号も含めるので upper_bound ではなく lower_bound を使い、同じスコアも配列に残す。順位の対象は濃度の異なる値ではなく、容器の選び方 (i,j)(i,j) だからだ。例えば両者が同じ50%の砂糖水を2本ずつ持つなら、50%の組は4個ある。

探索の下端を L=0L=0、上端を R=1R=1 とする。砂糖も水も正なので、count(0)=NM≥K\mathrm{count}(0)=NM\geq K、count(1)=0<K\mathrm{count}(1)=0<K であり、下端が成功側、上端が失敗側になる。次を固定回数 II だけ繰り返す。

  1. x=(L+R)/2x=(L+R)/2 とし、この xx に対するスコアを計算する。
  2. 青木君のスコアを整列し、各高橋君のスコアから lower_bound で count(x)\mathrm{count}(x) を求める。
  3. count(x)≥K\mathrm{count}(x)\geq K なら L=xL=x、そうでなければ R=xR=x とする。

候補濃度が変わるたびにスコアも変わるため、青木君側の整列は毎回行う。探索後に初めて100倍し、100L100L を百分率で出力する。反復数と浮動小数点誤差の扱いは「実装上の注意」で確認する。

典型の発動条件

K番目値の二分探索

候補全体を列挙するには多すぎても、閾値以上の要素数を高速に数えられるなら、順位を個数の判定へ変換する。閾値を上げたとき個数が増えないことと、同じ値を持つ別の選択を数えることを確認する。

二集合pair和数え上げ

二つの選択肢にまたがる条件が ui+vj≥0u_i+v_j\geq 0 へ分離できれば、一方を整列し、他方を固定して補数 −ui-u_i 以上の範囲を数えられる。比率の場合は、分母が正であることを確認してから「分子 − 閾値 × 分母」へ変形すると、この分離を見つけやすい。

問題固有の要素

混ぜた砂糖水では砂糖量も総質量も加算されるため、比率の不等式を払うと各容器のスコアの和になる。ここでは「条件を満たす組が存在するか」だけでは順位が分からず、条件を満たす容器の組を全て数える必要がある。比率の最適化で使う変形を、二集合の組数判定へつなぐ点が核心である。

正当性

総質量が正なので、組 (i,j)(i,j) の混合濃度が xx 以上であることと ui+vj≥0u_i+v_j\geq 0 は同値である。固定した ii について、整列した VV の位置 pip_i 以降がちょうど vj≥−uiv_j\geq -u_i を満たす相手となる。各組は自分の ii の集計で一度だけ数えられ、等しいスコアも除去しないので、count(x)\mathrm{count}(x) は同濃度の別の組を含む正しい個数になる。

全 NMNM 組の比率を重複も含めて降順に並べ、KK 番目を qKq_K とする。x≤qKx\leq q_K なら上位 KK 組が条件を満たし、x>qKx>q_K なら満たす組は KK 個未満となる。従って count(x)≥K\mathrm{count}(x)\geq K と x≤qKx\leq q_K は同値である。初期区間と更新は常に L≤qK<RL\leq q_K<R を保ち、厳密な実数演算では反復ごとに区間幅が半分になる。よって区間を十分に狭めた後の 100L100L は、求める百分率 100qK100q_K を近似する。

実装上の注意

  • KK と組数の合計は最大 2.5×1092.5\times 10^9 なので、符号付き64 bit整数で持つ。NMNM を計算するときも乗算前に型を広げる。スコアと探索端点には double などの浮動小数点型を使う。
  • 許容誤差は、百分率で出力した値の絶対誤差または相対誤差 10−910^{-9} である。厳密な実数演算なら II 回後の百分率の区間幅は 100⋅2−I100\cdot 2^{-I}。例えば30回では約 9.31×10−89.31\times 10^{-8} だが、40回なら約 9.10×10−119.10\times 10^{-11} となる。実装では丸めもあるため、公式解説にならい100回程度反復し、例えば固定小数点で小数部を15桁以上出力する。反復だけで丸め誤差まで消せるわけではなく、double では途中から中点が端点と一致し得る。
  • 判定の境界は等号を含む0に保つ。安易に許容幅を足して組を数えると、順位の境界そのものがずれる。K=1K=1 と K=NMK=NM、同濃度多数、砂糖量と水量が極端に偏る入力を、小さい全組列挙と比較して確認する。
  • 除算のないスコアなら x=1x=1 でも ui=−Bi<0u_i=-B_i<0、vj=−Dj<0v_j=-D_j<0 となり、全組が失敗する。x=0x=0 では全組が成功する。水も砂糖も正という制約が、初期端点を保証している。

復習の核

  • 比率を直接足せないときは、分母の正性を確かめて「分子 − 閾値 × 分母」を作り、選択肢ごとの寄与に分ける。
  • 「大きい方から何番目か」は「閾値以上が何個あるか」へ変える。等しい値でも選び方が違えば順位を占める。
  • 探索中の単位と出力の単位を区別し、換算倍率を誤差評価にも掛ける。

計算量と制約

時間

判定1回につき、スコアの計算が O(N+M)O(N+M)、青木君側の整列が O(Mlog⁡M)O(M\log M)、高橋君側からの NN 回の境界探索が O(Nlog⁡M)O(N\log M)。従って全体は O(I(Mlog⁡M+Nlog⁡M))O(I(M\log M+N\log M)) 時間(M≥2M\geq 2)。M=1M=1 も含めて書けば O(I(M+N)log⁡(M+1))O(I(M+N)\log(M+1)) であり、II は二分探索の反復数である。

空間

入力を保持する O(N+M)O(N+M) と、青木君側のスコア配列 O(M)O(M) を合わせて O(N+M)O(N+M)。全 NMNM 組を保持する必要はない。

制約との対応

1≤N,M≤5×1041\leq N,M\leq 5\times 10^4、1≤K≤NM1\leq K\leq NM、1≤Ai,Bi,Cj,Dj≤1051\leq A_i,B_i,C_j,D_j\leq 10^5。全組の列挙を避け、各判定を整列と境界探索で処理する。全ての砂糖量・水量が正なので混合濃度は0と1の間にあり、分母の正性と探索端点の成功・失敗が保証される。制限時間は4秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sugar Water 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

      主タグ: fractional programming・比率parametric search

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

      学習の位置

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

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

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題