考察
候補の濃度以上になる混ぜ方の個数が分かれば、濃い方から何番目かを判定できる。砂糖量から「候補の濃度に達するために必要な砂糖量」を引くと、混合後の条件を二つの容器の寄与の和に分けられる。
全ての混ぜ方を作って濃度順に並べると、最大 組になる。そこで、順位そのものを探す代わりに「ある濃度以上の組が 個以上あるか」を考える。その濃度を高くするほど条件は厳しくなるため、この判定には二分探索が使えそうだ。残る課題は、全組を調べずに個数を数えることである。
以後、候補濃度 は百分率ではなく、砂糖の質量を砂糖水の総質量で割った の比率とする。例えば が50%に対応する。高橋君の容器 は砂糖 グラム・水 グラム、青木君の容器 は砂糖 グラム・水 グラムを含む。添字の範囲は 、 とする。
混ぜた後の比率が 以上という条件を式にしよう。総質量は正なので、分母を払っても不等号の向きは変わらない。
分母を払い、右辺を左辺へ移すと、
ここで総質量に を掛けた量は、その総質量で候補濃度を満たすために必要な砂糖量である。容器ごとに「実際の砂糖量からこの必要量を引いた値」をスコアとして定義する。
これで混合条件は となる。例えば のとき、砂糖4グラム・水1グラムのスコアは 、砂糖1グラム・水4グラムのスコアは である。和は0なので、二つを混ぜるとちょうど50%になる。濃度そのものを足すのではなく、質量の単位を持つスコアを足している。
公式解説は、砂糖 グラム・水 グラムに対し、水の量を固定して濃度 にするための砂糖量 を考え、余剰 を使う。本稿のスコアとの関係は、 で
である。固定した では全容器に同じ正数 を掛けているので、スコアの大小関係も、二つの和の符号も同じになる。以降は除算のない を使う。公式解説の余剰の式は では評価できないが、本稿の式は端点でも定義できる。
固定した で青木君のスコアを昇順に整列した配列を とし、その位置は0始まりとする。高橋君の容器 に対し、混ぜられる相手は を満たすもの全てである。lower_bound(V, -u_i) が返す最初の位置を 、該当要素がなければ とすれば、その個数は になる。従って
を求めればよい。等号も含めるので upper_bound ではなく lower_bound を使い、同じスコアも配列に残す。順位の対象は濃度の異なる値ではなく、容器の選び方 だからだ。例えば両者が同じ50%の砂糖水を2本ずつ持つなら、50%の組は4個ある。
探索の下端を 、上端を とする。砂糖も水も正なので、、 であり、下端が成功側、上端が失敗側になる。次を固定回数 だけ繰り返す。
- とし、この に対するスコアを計算する。
- 青木君のスコアを整列し、各高橋君のスコアから
lower_bound で を求める。
- なら 、そうでなければ とする。
候補濃度が変わるたびにスコアも変わるため、青木君側の整列は毎回行う。探索後に初めて100倍し、 を百分率で出力する。反復数と浮動小数点誤差の扱いは「実装上の注意」で確認する。
典型の発動条件
K番目値の二分探索
候補全体を列挙するには多すぎても、閾値以上の要素数を高速に数えられるなら、順位を個数の判定へ変換する。閾値を上げたとき個数が増えないことと、同じ値を持つ別の選択を数えることを確認する。
二集合pair和数え上げ
二つの選択肢にまたがる条件が へ分離できれば、一方を整列し、他方を固定して補数 以上の範囲を数えられる。比率の場合は、分母が正であることを確認してから「分子 − 閾値 × 分母」へ変形すると、この分離を見つけやすい。
問題固有の要素
混ぜた砂糖水では砂糖量も総質量も加算されるため、比率の不等式を払うと各容器のスコアの和になる。ここでは「条件を満たす組が存在するか」だけでは順位が分からず、条件を満たす容器の組を全て数える必要がある。比率の最適化で使う変形を、二集合の組数判定へつなぐ点が核心である。
正当性
総質量が正なので、組 の混合濃度が 以上であることと は同値である。固定した について、整列した の位置 以降がちょうど を満たす相手となる。各組は自分の の集計で一度だけ数えられ、等しいスコアも除去しないので、 は同濃度の別の組を含む正しい個数になる。
全 組の比率を重複も含めて降順に並べ、 番目を とする。 なら上位 組が条件を満たし、 なら満たす組は 個未満となる。従って と は同値である。初期区間と更新は常に を保ち、厳密な実数演算では反復ごとに区間幅が半分になる。よって区間を十分に狭めた後の は、求める百分率 を近似する。
実装上の注意
- と組数の合計は最大 なので、符号付き64 bit整数で持つ。 を計算するときも乗算前に型を広げる。スコアと探索端点には
double などの浮動小数点型を使う。
- 許容誤差は、百分率で出力した値の絶対誤差または相対誤差 である。厳密な実数演算なら 回後の百分率の区間幅は 。例えば30回では約 だが、40回なら約 となる。実装では丸めもあるため、公式解説にならい100回程度反復し、例えば固定小数点で小数部を15桁以上出力する。反復だけで丸め誤差まで消せるわけではなく、
double では途中から中点が端点と一致し得る。
- 判定の境界は等号を含む0に保つ。安易に許容幅を足して組を数えると、順位の境界そのものがずれる。 と 、同濃度多数、砂糖量と水量が極端に偏る入力を、小さい全組列挙と比較して確認する。
- 除算のないスコアなら でも 、 となり、全組が失敗する。 では全組が成功する。水も砂糖も正という制約が、初期端点を保証している。
復習の核
- 比率を直接足せないときは、分母の正性を確かめて「分子 − 閾値 × 分母」を作り、選択肢ごとの寄与に分ける。
- 「大きい方から何番目か」は「閾値以上が何個あるか」へ変える。等しい値でも選び方が違えば順位を占める。
- 探索中の単位と出力の単位を区別し、換算倍率を誤差評価にも掛ける。
計算量と制約
時間
判定1回につき、スコアの計算が 、青木君側の整列が 、高橋君側からの 回の境界探索が 。従って全体は 時間()。 も含めて書けば であり、 は二分探索の反復数である。
空間
入力を保持する と、青木君側のスコア配列 を合わせて 。全 組を保持する必要はない。
制約との対応
、、。全組の列挙を避け、各判定を整列と境界探索で処理する。全ての砂糖量・水量が正なので混合濃度は0と1の間にあり、分母の正性と探索端点の成功・失敗が保証される。制限時間は4秒、メモリ制限は1024 MiB。
出典