AOJ PG応用(列の操作)

最小値、最大値

与えられた３つの整数a,b,cの最小値と最大値を出力してください

ex.java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 標準入力から1行読み取り
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");

        // String → int に変換するのを忘れないように！
        int[] input = new int[3];
        for (int i = 0; i < 3; i++) {
            input[i] = Integer.parseInt(parts[i]);
        }

        // 最小値と最大値を計算して出力
        int min = min(input);
        int max = max(input);
        System.out.println(min + " " + max);
    }

    // 最小値を求めるメソッド
    static int min(int[] input) {
        int min = input[0];
        for (int i = 1; i < input.length; i++) {
            if (input[i] < min) {
                min = input[i];
            }
        }
        return min;
    }

    // 最大値を求めるメソッド
    static int max(int[] input) {
        int max = input[0];
        for (int i = 1; i < input.length; i++) {
            if (input[i] > max) {
                max = input[i];
            }
        }
        return max;
    }
}

配列を昇順にソートして最初と最後の要素を表示するだけでもOK

最小最大要素

与えられた数列
A={a0,a1,...,an−1}に対して、以下のクエリを処理してください。
min(b,e): 区間[b,e)の要素ab,ab+1,...,ae−1の最小値を報告する
max(b,e): 区間[b,e)の要素ab,ab+1,...,ae−1の最大値を報告する
※[b, e) は 「b 以上 e 未満」

ex.java

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

public class Main {
    static int[] A; // グローバルに定義

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

        // nの読み取り
        int n = Integer.parseInt(br.readLine());

        // A配列の読み取り
        String[] aStr = br.readLine().split(" ");
        A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(aStr[i]);
        }

        // クエリ数
        int q = Integer.parseInt(br.readLine());

        for (int i = 0; i < q; i++) {
            String[] query = br.readLine().split(" ");
            int op = Integer.parseInt(query[0]);
            int b = Integer.parseInt(query[1]);
            int e = Integer.parseInt(query[2]);

            if (op == 0) {
                System.out.println(In_min(b, e)); //System.out.println内でメソッド呼び出し
            } else {
                System.out.println(In_max(b, e));
            }
        }
    }

    // 最小値取得
    static int In_min(int b, int e) {
        int min = A[b];
        for (int i = b + 1; i < e; i++) {
            if (A[i] < min) min = A[i];
        }
        return min;
    }

    // 最大値取得
    static int In_max(int b, int e) {
        int max = A[b];
        for (int i = b + 1; i < e; i++) {
            if (A[i] > max) max = A[i];
        }
        return max;
    }
}

変数のスコープについて

• mainメソッド内だけで使いたい変数
  → mainメソッド内で定義
• mainメソッドだけでなく、mainから呼び出す他のstaticメソッドでも使いたい
  → 本門の配列AのようにMainクラスのstatic変数として宣言（グローバル変数）
• mainメソッドの外の静的メソッドだけで使いたい（main内では使わない）
  → mainメソッド内だけの場合と同様に、そのメソッド内にだけ変数を書くのが基本
  （ただし、複数メソッド間で共有したいならstatic変数にする

★前処理＆インデックスによるカウント

整数を保持する数列
A={a0,a1,...,an−1}に対して、以下のクエリを処理してください。
count(b,e,k): ab,ab+1,...,ae−1の中に含まれるkの数を出力する

AOJ.java

import java.util.*;

public class Main {
    static Map<Integer, List<Integer>> valToIndices = new HashMap<>();

//数列 A を処理して、上記の Map を作っていく関数
//各値がどのインデックスで出るかまとめる
    public static void preprocess(int[] A) {
        for (int i = 0; i < A.length; i++) {
            valToIndices.computeIfAbsent(A[i], k -> new ArrayList<>()).add(i);
        }
    }
    //クエリ (b, e, k) を受け取り、「A[b]〜A[e-1] に k が何回あるか」を返す
    public static int count(int b, int e, int k) {
    //数 k の出現位置リストを取得,もし k が A に一度も出てこなければ、空リストを返す
        List<Integer> indices = valToIndices.getOrDefault(k, new ArrayList<>());
        // lowerBound: b以上の最初の位置
        int left = lowerBound(indices, b);
        // lowerBound: e以上の最初の位置（eは範囲外なので含まない）
        int right = lowerBound(indices, e);
        return right - left;
    }

    // 二分探索→リストの中から、値がtarget 以上の最初のインデックスを探す
    public static int lowerBound(List<Integer> list, int target) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
        }

        preprocess(A);

        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int b = sc.nextInt();
            int e = sc.nextInt();
            int k = sc.nextInt();
            System.out.println(count(b, e, k));
        }
    }
}

• この手の問題は線形探索法かと思ったけど入力サイズが大きいとTLEしてしまうので今回は不採用
• 線形探索法がだめな場合、集合や二分探索など代替案の中から今回は「前処理でインデックスを作る」を選択
• 「インデックスを作る」→たとえば、配列 A = [50, 10, 30, 10] があるとき、
  「10はどこにある？」と聞かれたら、普通は1つずつ見ていって探すが（線形探索）いちいちやってたら時間がかかる
• よく使う値にすぐアクセスしたいなら、こういう「メモ帳」みたいなものを最初に作っておく

ex.java

valToIndices = {
    //値（ｋ）：配列Ａにおける出現位置（インデックス）
    1: [0, 2, 5],
    4: [1, 3],
    2: [4],
    3: [6],
    5: [7],
    6: [8]
}

• Map（値）> を使って、各値kがどのインデックスに出現するかを前処理で記録
• computeIfAbsent(key, k -> new ArrayList<>())→key が存在すればその値を返し、存在しなければ k -> new ArrayList<>() が呼ばれて値を作り、map.put(key, 値) して返す
• k -> new ArrayList<>はラムダ式→「k」を引数に取って、新しい空のArrayListを返す
• computeIfAbsentが内部で自動的にkeyをkに渡し、それを引数としてラムダ式の処理部分を実行

ex.java

valToIndices.computeIfAbsent(1, k -> new ArrayList<>()).add(0);
//「1というキーがなければ、空のリストを作ってそこに 0 を追加する」

• getOrDefault(key, defaultValue)→キーがあればその値を返し、なければ new ArrayList<>() を返す（でもMapには追加しない！）
  →値を登録したいときはcomputeIfAbsentでいいけど単に読みたいだけなら getOrDefault
• 例えばcount(1,4,3)でindices = [0, 1, 2, 4] （Ａにおける３の出現位置）だとする
• インデックス 1, 2, 3 の中に 3 が何回あるか数える→lowerBoundを使う
• lowerBound→list の中で、「target以上」の値が最初に現れるインデックスを返す
• binarysearchはインデックスがある位置を返すための二分探索なのでここでlowerboundを定義

辞書順比較

２つの数列A={a0,a1,...,an−1}とB={b0,b1,...,bm−1}を辞書式順で比較してください。

aoj.java

//数列問題だし数値を直接利用したいので標準入力をScannerでうけとる
//Aの要素数nとAの要素を受け取る
//Bの要素数mとBの要素を受け取る
//線形探索していく。要素をループで順に比較し、A[i] != B[i]になったときその大小を判定→A[i]<B[i]なら1,それ以外なら0を出力
import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[]A = new int[n];
        for(int i=0;i<n;i++){
            A[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[]B = new int[m];
        for(int i=0;i<m;i++){
            B[i] = sc.nextInt();
        }
        int minLen = Math.min(n,m);
        for(int i=0;i<minLen;i++){
            if(A[i] < B[i]){
                System.out.println(1);
                sc.close();
                return;
            }else if(A[i] > B[i]){
               System.out.println(0);
                sc.close();
                return; 
            }
        }
        if(n<m){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
        sc.close();
    }
}

• ループ回数を短い方の数列にあわせる→Math.minで要素数の小さいほうをループ回数に設定