ch6 二分探索法

6.1

この問題は「座標圧縮」と呼ばれる典型的な処理です。
各要素が全体で何番目に小さいか（0始まりの順位）を求める問題で、ソートを使うと \(O(N \log N)\) で実現できます。

アイデア

  1. 値と元の位置をペアにする
    配列 a の各要素に、「値」と「もともとあったインデックス」をセットにしたタプルを作ります。
    例：a = [12, 43, 7, 15, 9] → [(12,0), (43,1), (7,2), (15,3), (9,4)]

  2. 値でソートする
    タプルのリストを「値」の昇順に並べ替えます。
    ソート後：[(7,2), (9,4), (12,0), (15,3), (43,1)]
    こうすると、先頭から順に「0番目に小さい値、1番目に小さい値…」と順位が決まります。

  3. 順位を格納する配列を作る
    答えを入れる配列 rank を用意し、ソート後のリストを先頭から見ていきます。
    ソート後の i 番目の要素が持つ「元のインデックス」の位置に、順位 i を入れます。
    上の例なら：

    • i=0 → 元のインデックス 2 → rank[2] = 0
    • i=1 → 元のインデックス 4 → rank[4] = 1
    • i=2 → 元のインデックス 0 → rank[0] = 2
    • i=3 → 元のインデックス 3 → rank[3] = 3
    • i=4 → 元のインデックス 1 → rank[1] = 4

    結果 rank = [2, 4, 0, 3, 1] となり、問題例と一致します。

ソートが \(O(N \log N)\)、その後の走査が \(O(N)\) なので、全体で \(O(N \log N)\) です。
※値がすべて相異なるという条件があるので、同点を気にする必要はありません。

6.2

アイデア

条件は「a のある要素 < b のある要素 < c のある要素」なので、真ん中の配列 b に着目して考えます。
ある b[j] を固定したとき、次の2つが分かれば、その b[j] を使う組の数が計算できます。

  • a の中で b[j] より小さい要素の個数
  • c の中で b[j] より大きい要素の個数

この2つの積が、その b[j] に対する有効な (i, k) の組み合わせ数です。
あとはすべての j についてこれを合計すれば答えになります。

効率的な求め方

  1. 配列 a と c をソートする

    • a は昇順にソート → \(O(N \log N)\)
    • c も昇順にソート → \(O(N \log N)\)
      ※ b はそのまま使うためソート不要です。

  2. 各 b[j] について個数を二分探索で求める

    • a の中で b[j] より小さい要素の個数 → bisect_left(a, b[j]) のインデックスがその個数。
    • c の中で b[j] より大きい要素の個数 → N - bisect_right(c, b[j]) で求められる。
      （bisect_right は b[j] より大きい最初の位置を返すため、そこから末尾までが条件を満たす要素数）
      これは1つの b[j] あたり \(O(\log N)\) なので、全体で \(O(N \log N)\) です。

  3. 積を合計していく
    各 j について (aの小さい個数) * (cの大きい個数) を足し上げます。

  • 個数を求めるだけなので二分探索を実装しなくてもbisectを使うことができる
  • 数列の要素に重複があっても、bisect_left / bisect_right を使うことで「より小さい」「より大きい」を正しく数えられます。
  • 答えが大きくなる可能性があるため、言語によっては64ビット整数が必要ですが、Pythonの整数は自動拡張されるので問題ありません。
  • この解法の計算量は、ソートに \(O(N \log N)\)、二分探索のループに \(O(N \log N)\) で、全体 \(O(N \log N)\) です。

6.3

アイデア

4つの数の組み合わせを直接調べると \(O(N^4)\) かかります。そこで、「2つの数の和」をあらかじめ全列挙し、問題を2段階に分けることで高速化します。

  1. 2数の和を全生成する
    配列 \(a\) から2つの要素（重複可）を選んだ和の一覧 \(S\) を作ります。
    組み合わせは \(N \times N = N^2\) 通り → \(O(N^2)\)。

  2. ソートする
    \(S\) を昇順にソートします → \(O(N^2 \log N)\)。

  3. 探索する
    いま、選ぶ4つの数は「2つの数の和」2つに分解できます。
    一方の和を \(x \in S\)、もう一方を \(y \in S\) とすると、条件は \(x + y \le M\) です。
    ソート済みの \(S\) に対し、各 \(x\) について \(M - x\) 以下で最大の \(y\) を二分探索で見つけ、\(x + y\) の最大値を記録します。
    各 \(x\) の探索は \(O(\log |S|) = O(\log N)\)、全体で \(O(N^2 \log N)\) です。

ポイント

  • 重複を許すため、\(S\) は \(a_i + a_j\) （\(i,j\) は独立に全範囲）とすれば同じ要素の複数回使用もカバーできます。(こんなの思いつけるかい)
  • 二分探索には bisect_right を使い、M - x 以下の最後の位置を求めます。
  • 正の整数のみなので \(S\) の要素も2以上ですが \(x > M\) のときはスキップして構いません。

補足

  • 実際の競技では \(N \le 1000\) 程度でも \(N^2=10^6\) は十分扱えます。
  • ソート後の探索にしゃくとり法（二つのポインタ） を用いると \(O(N^2)\) に改善できますが、問題の要求は \(O(N^2 \log N)\) のため二分探索で十分です。
  • Pythonでは答えが32bitに収まらない場合もあるので、そのまま整数で扱える点も安心です。

6.4

問題

  • \(N\) 個の小屋が一直線、座標 \(a_0 \le a_1 \le \dots \le a_{N-1}\)（\(0\) 以上 \(M\) 以下）
  • その中から \(M\) 個選び、「選んだ小屋間の最小距離」を最大化せよ

アルゴリズム（二分探索＋貪欲法）

メモ

二分探索

  • 探索範囲：最小距離の候補 \(d\) の下限 \(L = 0\)、上限 \(R = a_{N-1} - a_0\)
  • 条件 possible(d) = 「最小距離を \(d\) 以上にできるか？」

判定 possible(d)（貪欲法）

  • 先頭の小屋を必ず選ぶ(なるべくたくさん選びたいのでとりあえず最左(or右)端は選ぶのがいい)
  • 前回選んだ小屋から距離 \(\ge d\) の最も左の小屋を選ぶ
  • 選べた数が \(M\) 個以上 → true、そうでなければ false

最小値の最大化

while left < right:
    mid = (left + right + 1) // 2   # 中央値を**切り上げ**
    if possible(mid):
        left = mid          # mid は条件を満たすので、これ以上の値を探す
    else:
        right = mid - 1     # mid は条件を満たさないのでmid-1 以下を探す
return left

while left < right:
    mid = (left + right + 1) // 2   # 中央値を**切り上げ**
    if possible(mid):
        left = mid          # mid は条件を満たすので、これ以上の値を探す
    else:
        right = mid - 1     # mid は条件を満たさないのでmid-1 以下を探す
return left

計算量：\(O(N \log A)\) （\(A = a_{N-1}\)）

ポイント

  • 貪欲法：局所最適（最も左の許容小屋を選ぶ）が全体最適に繋がる
  • mid を +1 するのは、left と right が隣り合ったとき無限ループを防ぐため

解答コード

from typing import List


class Solution:
    def possible(self, d: int, a: List[int], m: int) -> bool:
        count = 1  # 最初の小屋は必ず選ぶから
        prev = a[0]
        for i in range(1, len(a)):
            if a[i] - prev >= d:
                count += 1
                prev = a[i]
            if count == m:
                return True

        return False

    def agressive_cows(self, a: List[int], m: int) -> int:
        left = 0
        right = a[-1] - a[0]

        while right > left:
            mid = (right + left + 1) // 2  # 区間更新を保証して無限ループを避ける
            if self.possible(mid, a, m):
                left = mid
            else:
                right = mid - 1  # midは条件を満たさないのでmid-1以下を探す

        return left


from typing import List


class Solution:
    def possible(self, d: int, a: List[int], m: int) -> bool:
        count = 1  # 最初の小屋は必ず選ぶから
        prev = a[0]
        for i in range(1, len(a)):
            if a[i] - prev >= d:
                count += 1
                prev = a[i]
            if count == m:
                return True

        return False

    def agressive_cows(self, a: List[int], m: int) -> int:
        left = 0
        right = a[-1] - a[0]

        while right > left:
            mid = (right + left + 1) // 2  # 区間更新を保証して無限ループを避ける
            if self.possible(mid, a, m):
                left = mid
            else:
                right = mid - 1  # midは条件を満たさないのでmid-1以下を探す

        return left

ch7 貪欲法

貪欲法が最適になるパターン

  1. 交換しても悪化しない
  2. 現在が良いほど未来も良い

1. 交換しても悪化しない

区間スケジューリング問題: N 個の仕事があり，i(＝0, 1, ..., N－1) 番目の仕事は時刻 si に開始し，時刻 ti に終了します．これらの中から自分が行う仕事をできるだけ多く選びたいとします．ただし時刻が重なっている複数の仕事を選ぶことはできません．最大で何個の仕事をこなすことができるでしょうか．

この時終端時刻の順にソートすると、終端時刻が最も早い区間を\(p\)とすると\(p\)は必ず選択していい。なぜなら、「選ぶ区間の個数」を減らさずに区間\(p\)を選ぶ解を作れるから。 どういうことかというと、仮に重複のない区間を二つ選んだとする。そのうちの終端時刻が早い方を\(p\)に置き換えてもそれは必ず解になるということ よって、\(p\)自体は必ず選ぶことができる。これを繰り返す。（この部分が貪欲法）

7.1

500円玉，100円玉，50円玉，５円玉，１円玉がそれぞれ a0, a1, a2, a3, a4, a5 枚あります これらを用いて X 円を支払いたいとします． ここで，支払いに用いるコインの合計枚数をなるべく少なくしたいと考えています． 最小で何枚のコインで支払うことができるでしょうか．ただし，そのような支払い方が少なくとも１つは存在するものとします．

from typing import List


class Solution:

    COIN_VALUES = [500, 100, 50, 10, 5, 1]

    # 時間計算量: 硬貨の種類をkとしてO(k)
    def solve(self, coin_nums: List[int], X: int) -> int:
        if len(coin_nums) != 6:
            raise ValueError(f"coin_nums must have {len(self._COIN_VALUES)} elements")
        if X < 0:
            raise ValueError("inputs must be non-negative")

        remaining = X
        total_coins = 0
        # 貪欲法
        for coin_value, coin_num in zip(self._COIN_VALUES, coin_nums):
            use = min(X // coin_value, coin_num)

            remaining -= coin_value * use
            total_coins += use

        if remaining != 0:
            raise ValueError("X cannot be paid with given coins")

        return total_coins

from typing import List


class Solution:

    COIN_VALUES = [500, 100, 50, 10, 5, 1]

    # 時間計算量: 硬貨の種類をkとしてO(k)
    def solve(self, coin_nums: List[int], X: int) -> int:
        if len(coin_nums) != 6:
            raise ValueError(f"coin_nums must have {len(self._COIN_VALUES)} elements")
        if X < 0:
            raise ValueError("inputs must be non-negative")

        remaining = X
        total_coins = 0
        # 貪欲法
        for coin_value, coin_num in zip(self._COIN_VALUES, coin_nums):
            use = min(X // coin_value, coin_num)

            remaining -= coin_value * use
            total_coins += use

        if remaining != 0:
            raise ValueError("X cannot be paid with given coins")

        return total_coins

解法の正当性

今回の硬貨体系（500,100,50,10,5,1）は、各硬貨が一つ下の硬貨の整数倍（canonical coin system）になっており、無制限枚数であれば貪欲法が最小枚数を与えることが知られている。 しかし、枚数制限がある場合は、貪欲法が必ずしも最小枚数を与えるとは限らないケースが一般に存在する（例：ユーロ硬貨でも制限付きでは貪欲が失敗しうる）。その場合は動的計画法を使う解法も存在する しかし、以上のような性質はその場で思いつけるものではないので「直感的な日常の支払いに照らし合わせた」という説明ができた方がいい

7.2