upper_bound (paizaランク B 相当) 学習記録（自分用）

はじめに

Paizaの問題集を解いた際のメモ。
一応クリアはしたものの良い実装ではないと思うのであまり参考にはならないかと思います。
あくまでも自分用の学習メモ。

問題集＞二部探索メニュー＞upper_bound
問題URL：https://paiza.jp/works/mondai/binary_search/binary_search__basic_step2

問題

n 人の生徒が受けた、10^9 点満点のテストの採点結果 A_1, A_2, ..., A_n があります。あなたは合格点を自由に設定することができます。合格点が k 点のとき、k 点より大きい点数を取った生徒が合格で、k 点以下の点数を取った生徒が不合格です。

入力値

n
A_1 A_2 ... A_n
q
k_1
k_2
...
k_q

1行目に、生徒の人数 n が与えられます。
2行目に、採点結果 A_i が半角スペース区切りで与えられます。
3行目に、合格点の候補数 q が与えられます。
続く q 行のうち i (1 ≦ i ≦ q) 行目に、合格点の候補 k_i が与えられます。
q 個の整数 k_1, k_2, ..., k_q が与えられます。各 k_i について、合格点が k_i のときに合格する生徒の数を答えてください。

条件（ここがポイント）

・ 入力はすべて整数
・ 1 ≦ n ≦ 100,000
・ 0 ≦ A_i ≦ 10^9 (1 ≦ i ≦ n)
・ 1 ≦ q ≦ 100,000
・ 0 ≦ k_i ≦ 10^9 (1 ≦ i ≦ q)

データ数が多いため線形探索では、処理時間がオーバーしてしまうためアルゴリズムをうまく活用する必要あり。

実装

二分探索法を用いて実装した

<?php
    $student_number = trim(fgets(STDIN));
    $student_score_array = explode(' ', trim(fgets(STDIN)));

    //二部探索法を用いるためにはそーつする必要がある
    sort($student_score_array);
    
    $q = trim(fgets(STDIN)); //合格点候補の数
    
    //二分探索法でざっくりと合格基準点あたりの生徒番号（key）を求める
    for ($i = 0; $i < $q; $i++) {
        $reference_score = trim(fgets(STDIN));  //合格点
        $left = 0;
        $right = $student_number-1;
        $flag = false;
        
        //二分探索である程度絞る
        while ($left <= $right) {
            $mid = floor(($left+$right) / 2);
            if ($student_score_array[$mid] == $reference_score) {
                break;
            } elseif ($student_score_array[$mid] < $reference_score) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        //ここでの$midは、基準点あるいは基準点に近い値だった生徒の番号が格納されている
        
        //２分探索法で求めた値が、実際に基準点より点数が高いかどうかを判別
        if ($student_score_array[$mid] > $reference_score) {
            //基準点より点数が高かった場合は、生徒の人数から$midの値を引いて、合格者数を算出する
            $result_number = $student_number - $mid;
        } else {
            $flag = false;
            //基準点より点数が低かった場合は、基準点より高いが一番ギリギリだった生徒の番号をループで求める
            while (!$flag) {
                if (isset($student_score_array[$mid])) {
                    if ($student_score_array[$mid] > $reference_score) {
                        $flag = true;
                        $result_number = $student_number - $mid;
                        break;
                    } else {
                        $mid++;
                    }
                } else {
                    $mid++;
                }
                
                //生徒の番号が生徒の数より大きくなってしまった場合→つまり合格者がいなかった場合
                if ($mid >= $student_number) {
                    $result_number = 0;
                    $flag = true;
                    break;
                }
            }
        }
        echo $result_number."\n";
    }
?>

まとめ

久しぶりにアルゴリズムの問題を解いた。
二分探索法も少し忘れつつも、以前勉強したかいあって思い出すための時間はそこまでかからなかった。

A問題を解けるようになるためには、データ数が多い問題に対してアルゴリズムを駆使していかに指定時間内に処理を終わらせるかが重要であるため、引き続き学習していく。