はじめに

自分用の備忘録

問題文

下記のリンクを参考にしてください！

解答例

import java.util.Scanner;

public class Main {
    static int N, K;
    static int[] A;

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

        N = sc.nextInt();
        K = sc.nextInt();

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

        long Left = 1, Right = 1000000;
        while (Left < Right) {
            long Mid = (Left + Right) / 2;
            boolean answer = check(Mid);
            if (answer == false) {
                Left = Mid + 1;
            }
            if (answer == true) {
                Right = Mid;
            }
        }

        System.out.println(Left);

    }

    static boolean check(long seconds) {
        long sum = 0;
        
        for (int i = 1; i <= N; i++) {
            sum = sum + seconds / A[i];
        }

        if (sum >= (long)K) {
            return true;
        }
        return false;
    }
}

解説

このコードは、競技プログラミングの問題「A12 - Printer」の解答例です。この問題は、特定の時間内に最大で何枚のカードを印刷できるかを求めるものです。以下に、コードの各部分の説明を行います。

import java.util.Scanner;

public class Card {
    static int N, K;
    static int[] A;

ここでは、必要なライブラリをインポートし、クラスと変数を定義しています。Nはプリンターの数、Kは印刷する必要があるカードの数、Aは各プリンターが1枚のカードを印刷するのに必要な時間を格納する配列です。

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

        N = sc.nextInt();
        K = sc.nextInt();

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

この部分では、標準入力からデータを読み込んでいます。まず、プリンターの数Nと印刷する必要があるカードの数Kを読み込みます。次に、各プリンターが1枚のカードを印刷するのに必要な時間を配列Aに格納します。

        long Left = 1, Right = 1000000;
        while (Left < Right) {
            long Mid = (Left + Right) / 2;
            boolean answer = check(Mid);
            if (answer == false) {
                Left = Mid + 1;
            }
            if (answer == true) {
                Right = Mid;
            }
        }

        System.out.println(Left);

この部分では、二分探索を用いて最適な印刷時間を求めています。LeftとRightは探索範囲の下限と上限を表し、Midはその中間値です。check(Mid)関数は、Mid秒でK枚のカードを印刷できるかどうかをチェックします。印刷できる場合、上限RightをMidに更新し、印刷できない場合、下限LeftをMid+1に更新します。このプロセスをLeftがRight以上になるまで続け、最終的なLeftの値が最小の印刷時間となります。

    static boolean check(long seconds) {
        long sum = 0;
        
        for (int i = 1; i <= N; i++) {
            sum = sum + seconds / A[i];
        }

        if (sum >= (long)K) {
            return true;
        }
        return false;
    }
}

この部分は、指定された時間secondsでK枚のカードを印刷できるかどうかをチェックする関数です。各プリンターがseconds秒で印刷できるカードの枚数を合計し、その合計がK以上であればtrueを、そうでなければfalseを返します。これにより、二分探索の各ステップで印刷可能な時間をチェックできます。

以上が、このコードの解説です。このコードは、二分探索というアルゴリズムを用いて、効率的に最適な解を見つけ出すことができます。競技プログラミングでは、このようなアルゴリズムを理解し、適切に使用することが重要です。

ソース: Bing との会話 2024/3/17 (1) github.com. https://github.com/JihunLim/AlgoSolve/tree/1ba848826ae3c202874a3c6aa1de7acda383222f/OI_01%2Fsrc%2FMain.java.

所感

難しかった。でもこれをすらすらできるようにあったら、レベルアップするぞ！

二分探索のメモ

二分探索は、ソートされたリストや配列から特定の要素を効率的に探すためのアルゴリズムです。以下に、その基本的な手順を説明します。

初期化: 探索範囲の下限Leftと上限Rightを設定します。通常、Leftは配列の最初のインデックス、Rightは最後のインデックスに設定します。
中間点の計算: Midを(Left + Right) / 2で計算します。これにより、探索範囲の中間点を得ることができます。
要素のチェック: Midの位置の要素が目的の値と一致するかどうかをチェックします。一致する場合、その位置を返して探索を終了します。
範囲の更新: 目的の値がMidの位置の要素より大きい場合、LeftをMid + 1に更新します。目的の値がMidの位置の要素より小さい場合、RightをMid - 1に更新します。
終了条件のチェック: LeftがRightより大きくなったら、探索を終了します。これは、目的の値が配列に存在しないことを意味します。

二分探索は、探索範囲を半分にすることで効率的に解を見つけることができるため、大きなデータセットに対して非常に有効なアルゴリズムです。

復習記録

2024年3月19日

3回目の復習見てようやく書けるようになった！今回書けるようになって気づいたことは2分探索をするときには関数を main 外で作るんだけど、その時は答えを返すものとtrue falseを返すものの二つの種類がある！今回の問題の場合はtrueとfalseを返す形で書いていますね。前回のA11のときは答えをそのまま返してもらう形で書いてましたね。なるほど。

taipy.hatenablog.com

2024年3月20日

いやー、今日ようやく自分がミスしていた箇所がわかった。ミスった箇所はfor文のインデックスだった。

間違い

long sum = 0;
// N に注目！
        for (int i = 1; i < N; i++) {
            sum = sum + (midValue / A[i]);
        }

正解

long sum = 0;
// Nに注目！
        for (int i = 1; i <= N; i++) {
            sum = sum + (midValue / A[i]);
        }

対策としてはもうコードスニペット的なのを作っちゃうかな。VSCode登録する機能があるみたいだし。

code.visualstudio.com

zenn.dev

qiita.com

参考文献

github.com

taiPyのお悩み解決ブログ

日々の発見をまとめます！

Javaの解答例：A12 - Printer , 競技プログラミングの鉄則