『こちらを探索』BOJ 14434アトラクション1

質問する

問題の背景から見ると、すべての児童の初日の身長は0で、各児童の身長は1で、この日の長さはkの順に並んでいます.この場合、i児とj児が身長制限のあるkアトラクションに乗れるという質問は全部でq個あり、所定の時間内に日付ごとに何個回答できるかという質問があります.

に近づく

すべての問題について、日付を基準に二分探索を行い、最初にアトラクションに乗れる日を探します.(身長が下がらないので初日から最終日まで搭乗可能)

特定の日に2人の子供が対応するアトラクションに乗れるかどうかを判断しなければならない.

2-1. 長身の子供の番号を順番に検索する.
->時間的複雑度はO(q87 logk87 k)O(q*logk*k)O(q87 logk87 k)であり,問題制限の解法に合致しない.

2-2. 配列を現在の日付に切り取って並べ替えた後、upper bound-low bowndを使用して、その子の総身長が何回増加したかを計算します.
->最終的にはソートが必要なため、2-1よりも時間的に複雑です.

2-3. これまで子供が全部で何回成長したかさえわかればいいので、qforゲートを回す前に、子供一人一人の身長成長日(長さ可変配列>javaはArrayListを使用)を事前に保存しておき、必要に応じて、この検索で、これまでに何回か成長してきました.
時間複雑度O(q87 logk87 logk)O(q*logk*logk)O(q87 logk87 logk)が利用可能です.

予め長さkの解答配列(初期化0)を設定しておき、各質問に搭乗可能な初日が得られ、その後[搭乗可能な初日]+1と回答する.
すべての質問の検索が終了すると、残りの答えをインデックス1から最後の順に検索し、答え[i]に答え[i-1]を追加します.i-1から搭乗可能な質問に答えてi-1から最後まで答えられるからです.

解答案を出力すると正解が得られます

コード#コード#

import java.io.*;
import java.util.*;

class Main {
    static int n;
    static int m;
    static int k;
    static int q;

    static int[] limit;
    static ArrayList<Integer>[] list;

    static int find(int day, int child1) {
        int l = -1;
        int r = list[child1].size();

        while (l + 1 < r) {
            int mid = (l + r) / 2;

            if (list[child1].get(mid) <= day) {
                l = mid;
            } else {
                r = mid;
            }
        }

        return l + 1;
    }

    static boolean check(int day, int child1, int child2, int ride) {

        int height1 = find(day, child1);
        int height2 = find(day, child2);

        if (height1 + height2 >= limit[ride - 1]) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        k = Integer.parseInt(temp[2]);
        q = Integer.parseInt(temp[3]);

        temp = br.readLine().split(" ");
        limit = new int[m];

        for (int i = 0; i < m; i++) {
            limit[i] = Integer.parseInt(temp[i]);
        }
        list = new ArrayList[n + 1];

        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
        temp = br.readLine().split(" ");
        for (int i = 0; i < k; i++) {
            list[Integer.parseInt(temp[i])].add(i);
        }
        int[] answer = new int[k];

        for (int i = 0; i < q; i++) {
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            int ride = Integer.parseInt(temp[2]);

            int l = -1;
            int r = k;

            while (l + 1 < r) {
                int mid = (l + r) / 2;

                if (check(mid, u, v, ride)) {
                    r = mid;
                } else {
                    l = mid;
                }
            }

            if (r == k)
                continue;
            answer[r] += 1;
        }

        for (int i = 1; i < k; i++) {
            answer[i] += answer[i - 1];
        }

        for (int i = 0; i < k; i++) {
            System.out.println(answer[i]);
        }

    }
}