Shirotsume の日記

嘘Greedyを生やすな

ABC294-F「Sugar Water 2」

atcoder.jp

↑問題文へのリンク

タイトルを見て，あの幾何のやばいやつの続編か，いやだな～と思っていたのですがそれは D - Water Bottle でした．

考察はほぼ一瞬で終わって実装で手間取ったのですが，twitterを見ると考察が難しいと言っている人が多くてびっくりしていました． それぞれはそんなに難しくない（茶～緑diffくらい？）典型的な要素がいくつか組み合わさって難易度が青diffまで上がっている地力ゲーという印象があって，こういうのを安定して早く解けるかどうかで実力出そうだな～と思っていました．ということで振り返り兼自省としてこの問題の解説を書きます．

問題文

高橋君は N 本の砂糖水を、青木君は M 本の砂糖水を持っています。

高橋君の持っている i 番目の砂糖水は砂糖 A_i グラムと水 B_i グラムからなります。

青木君の持っている i 番目の砂糖水は砂糖 C_i グラムと水 D_i グラムからなります。

2 人の持つ砂糖水をそれぞれ 1 本ずつ選んで混ぜる方法は NM 通りあります。そのような方法でできる砂糖水の中で、濃度が高い方から K 番目の砂糖水の濃度が何 % であるかを求めてください。

K番目は何ですか問題

この問題のような，ある順序で並べ替えたとき K 番目になるものは何ですか？という問題には大きく2つの解法があると思っています．

  1. 前から貪欲に決定できる構造があるもの

例題↓ atcoder.jp

辞書順で～と言われたらまずこれです．辞書順では，先頭の文字がaであるものは絶対にbよりも先になるので，先頭から文字を貪欲に決定していくことができます．

例えばこの例題では，先頭がaであるかbであるかをまず判定し，次に2番目が…と順番に決めていくことができます．

  1. 二分探索で判定問題に落とし込めるもの

例題↓

atcoder.jp

辞書順のように，これを取ったら絶対に最小になるみたいなうまい性質がないときは多分これです．最終的な答えを決め打って，判定問題に変えてしまいます．

今回は砂糖水の濃度にいい性質がないので，1の方法で解くのは厳しそうです．よって2の方法で解きましょう．

二分探索に落とし込む

上から K 番目の砂糖水の濃度は X 以上か？という判定問題を考えます． X「以上」という条件にすることで，いい感じに解けます．この問題に限らず，ぴったり X を判定するのが難しければ X 以上/以下を考えてみるというのは良い発想だと思います．

上から K 番目が X %以上ということは，上から 1, 2, \dots, K 番目は X パーセント以上じゃないとダメです．よって，この判定問題は，以下のように言い換えられます．

  • NM通りの砂糖水のうち，濃度が X 以上の砂糖水が K 個以上あるか？

これが解けると，あとは X について二分探索すればACです． (0, 100) の範囲で実数で二分探索すればよいです．

実数の二分探索についてはえびちゃんのすてきな記事をお読みください．自分は決め打ちの方が（競プロ文脈では）いいと思います．

rsk0315.hatenablog.com

rsk0315.hatenablog.com

以降はこの判定問題の解法を考えていくことになります．

判定問題を解く

  • NM通りの砂糖水のうち，濃度が X 以上の砂糖水が K 個以上あるか？

という問題は，愚直に全通り試すことで O(NM) で解けます．が，これでは遅いので高速化を考えましょう．

まず，式を書いてみましょう．問題文に式を書いてくれているので，高橋君が砂糖水 (A_i, B_i) ，青木君が砂糖水 (C_j, D_j) を取ったとして，式に代入して濃度を計算します．

（濃度）= \frac{100(A_i + C_j)}{A_i + B_i + C_j + D_j}

よって，判定問題は，

以下の条件を満たす (i, j) (1 \leq i \leq N, 1 \leq j \leq M) が K 個以上か判定せよ．

  • \frac{100(A_i + C_j)}{A_i + B_i + C_j + D_j} \geq X

という数え上げ問題に帰着できます．

変数分離

このような (i, j) の入り乱れた問題は， i のついた項を左辺， j のついた項を右辺に寄せられるか考えてみるとよいです．こうすると， i を固定して j を高速に数えるみたいな方針で解けることが多いです．

↓例題

atcoder.jp

ということでそれを目指して式変形します．

\frac{100(A_i + C_j)}{A_i + B_i + C_j + D_j} \geq X

100(A_i + C_j) \geq X(A_i + B_i + C_j + D_j)

100A_i + 100C_j \geq XA_i + XB_i + XC_j + XD_j

100A_i - XA_i - XB_i \geq XC_j - 100C_j + XD_j

(100 - X)A_i - XB_i \geq (X - 100) C_j + XD_j

できました．あとは， P_i = (100 - X)A_i - XB_i とした数列 P ， Q_i = (X - 100)C_i + XD_i とした数列 Q を用意すると，以下の問題になります．

以下の条件を満たす (i, j) (1 \leq i \leq N, 1 \leq j \leq M) が K 個以上か判定せよ．

  • P_i \geq Q_j

ここまでくると茶diffくらいですかね．それぞれの i について， Q に含まれる P_i 以下の要素の個数が分かれば良いので， Q をソートして二分探索すればよいです．Pythonなら bisect_left やるだけです．

実装の際に

コンテスト本番で，式変形までは割とストレートにできたのですが，帰着してからが大変でした．素直に Q を二分探索していいところ，尺取り法的にできないか？みたいなことをずっと考えていました．制約が控えめで，log2つくらいなら通すよという感じなのでおとなしく甘えるべきでしたね．

実装を炎上させているところ，maspyさんのこのツイートを思い出しました．

（なんかちょっと前に似た趣旨のツイートがあった気がするが思い出せない）

これを参考に，愚直を書きつつ合わせていくことにするとすぐ答えが合いました．

愚直を書きつつ細部を部分ごとに合わせていくみたいなのは競技に限らずプログラミングの汎用テクニックだと思うので，こういうのをすぐできないのは反省ポイントです．

感想など

コンテスト中の提出です↓

atcoder.jp

いざ解説を書いてみると，しっかり青diffだなという印象になりました．しかし，F問題の実装量としては少ない方なので，もうちょっと早く通せてればという感じです．