🙆‍♀️

ABC312 C - Invisible Handのメモ

2024/04/01に公開

AtCoder

考察

まずは $X$ を固定した時に、それに対して売り手と買い手が何人ずつになるかを求めることを考えました。 $X$ が決まればそれぞれの人数ははっきり決まりますし、その $X$ が条件を満たすかどうかもわかります。なので $X$ の候補となる整数について売り手と買い手の人数を高速に求めて $X$ 候補を探索していく感じでできそう。各人数を高速に求める方法ですが、全探索だとダメそうですが二分探索が使えそうです。ソートしても問題ないですし。
あとは $X$ ですが、これも全探索は無理そうですね。ちょっと悩みましたが、こっちも二分探索できるじゃんと気づきました。二分探索と全探索を組み合わせる問題はけっこう見たことがありますが、二分探索を組み合わせる問題は個人的には初見でした。

二分探索について

これ以降は以下の二分探索テンプレートを使う前提で記述していきます。（一般的な実装だと思います）

二分探索するには判定問題が必要です。実はここで混乱して悩みました…
そもそも二分探索についてちゃんとわかってなかったですね。一般的な実装だと左側がNG、右側がOKという単調性を使います。つまり、ある位置でNGならそれより左側も全部NGなので右側を探索しにいく、ある位置でOKなら右側も全部OKなので左側を探索しにいく、となります。また、ここで言う二分探索で得られるのは条件を満たす要素のうち最も左側の値の位置です。

たとえば昇順ソートされた整数列を探索することを考えます。この時、判定問題は「要素が探索対象と一致するかどうか」ではなく、「要素が探索対象以上かどうか」とします。

[1, 2, 3, 4, 5, 6, 7, 8, 9]

ここから4の位置を探すとしたら、判定問題が「要素が探索対象以上かどうか」だとOKかNGかは以下のようになります。

[NG, NG, NG, OK, OK, OK, OK, OK, OK]

これだと境目から左は全部NG、右は全部OKと綺麗に分かれるので二分探索ができます。

一方「要素が探索対象と一致するかどうか」としてしまうと

[NG, NG, NG, OK, NG, NG, NG, NG, NG]

このようになります。これだと4の位置だけがOKとなってそれより右がOKにならないので二分探索が正しくできません。
めっちゃ基本なのですがよくわかってませんでしたね…（上の記事ではちゃんとそう書いてますが、理解が浅かったので忘れてました）

内側の二分探索の判定問題

上記を踏まえたうえで、まずは売り手の人数を求めるための判定問題についてです。これは結論から言えば「 $A_i$ が探索対象（ $X$ ）以下かどうか」という判定問題を使い、 $A$ の中の $X$ 以上の最小の数を求めます。
なんか直感的には「 $A_i$ が $X$ 以上かどうか」と思ってしまったのですが逆でした。 $A_i$ は要求金額、 $X$ は提示金額なので、たとえば100円（ $A_i$ ）以上が必要なのに80円（ $X$ ）が提示されたら金額が足りないのでNGとなるべきですね。
この場合、 $A_i$ が $X$ より大きかったらNG、 $X$ 以下であればOKなわけですが、ここで言う二分探索では左がNGで右がOKです。なので左が大きく右が小さい、つまり降順ソートされている必要があります。
これで二分探索ができますが、二分探索で求められるのは位置です。OKと言った人のうち最も左側の位置です。それより左の人はNGと言った人たちです。なので0-indexedだと、二分探索によってわかるのはNGと言った人数です。欲しいのはOKと言った人数なので、全体の人数から二分探索によって得られた値を引いて求めます。

次に買い手の人数ですが、これは上記と逆になりますね。つまり「 $B_i$ が探索対象（ $X$ ）以上かどうか」という判定問題を使い、 $B$ の中の $X$ 以下の最大の数を求めます。80円（ $B_i$ ）以下なら買ってよいのに100円（ $X$ ）が提示されたら高いのでNGですね。 $X$ が100円でも $B_i$ が110円ならOKです。 $B_i$ が低いとNG、高いとOKなのでこちらは昇順ソートされている必要があります。
なお、二分探索で得られるのはOKと言った人のうち最も左側の位置、というのは変わりません。なので、全体の人数から二分探索によって得られた値を引くというのは同じです。

外側の二分探索の判定問題

内側のほうはめちゃくちゃ混乱したのですが、外側のほうはわりと素直です。問題文に記載の条件がそのまま判定問題となります。つまり「売り手の人数が買い手の人数以上かどうか」です。

実装

外側の判定問題はisOkで定義していて、内側の判定問題はその中に記載します。内側の判定問題と、得られた値で引いて欲しい値を求めるのはcount()関数にしました。

あとは探索範囲ですが、内側の判定問題については配列の要素数、外側は雑に広範囲にしています。上限が $10^9$ だと微妙に足りず、 $10^9+1$ 以上である必要があるはず。（ $N < M$ かつ全ての $A_i$ と $B_i$ が $10^9$ とかだと、 $10^9$ だと条件を満たさず $10^9+1$ が答えになる）
ただ、ここで使うテンプレートだとexclusiveなので値としては $10^9+2$ 以上にします。

import kotlin.math.abs
import kotlin.math.min

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }
        .sortedDescending()
        .toIntArray()
    val b = readln().split(" ").map { it.toInt() }
        .sorted()
        .toIntArray()

    var ans = Int.MAX_VALUE

    val isOk: (Int) -> Boolean = { x ->
        //println(x)

        val seller = count(a) { a[it] <= x }
        //println(seller)

        val buyer = count(b) { b[it] >= x }
        //println(buyer)

        val ok = seller >= buyer
        //println(ok)

        if(ok) {
            ans = min(ans, x)
        }
        ok
    }

    binarySearch(0, Int.MAX_VALUE / 2, isOk)

    println(ans)
}

fun count(array: IntArray, isOk: (Int) -> Boolean): Int {
    val size = array.size

    return size - binarySearch(-1, size, isOk)
}

fun binarySearch(minNg: Int, maxOk: Int, isOk: (Int) -> Boolean): Int {
    var ng = minNg
    var ok = maxOk

    while(abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if(isOk(mid)) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

以上、二分探索やるだけなのに二分探索ができないためにハマった件についてでした。

考察

二分探索について

内側の二分探索の判定問題

外側の二分探索の判定問題

実装

Discussion