AtCoder (AtCoder Beginners Selection) [ABC087B]

AtCoderの問題を解いてみます。今回は初心者向けの問題のAtCoder Beginners Selectionの2回目です。

ABC087B – Coins

https://atcoder.jp/contests/abs/tasks/abc087_b

問題概要

500円玉、100円玉、50円玉を使ってX円を支払う方法の数(コインの枚数の組の数)を求める問題です。500円玉はA枚、100円玉はB枚、50円玉はC枚までという制限があります。

作成ソース

言語

Java8 (OpenJDK 1.8.0)

試作版

最初に作ったコードが以下です。このコードは最初なので比較的、単純に作りました。

    public static void main(String... args) {
        int x, a, b, c;
        try (Scanner sc = new Scanner(System.in)) {
            a = sc.nextInt(); // 500 * a
            b = sc.nextInt(); // 100 * b
            c = sc.nextInt(); // 50 * c
            x = sc.nextInt(); // = x
        }

        System.out.println(new Main().count(x / 50, a, b, c));

    }

    private int count(int x, int a_max, int b_max, int c_max) {
        int count = 0;
        for (int a = 0; a <= a_max; a++) {
            int _x = x - a * 10;

            if (_x < 0) {
                break;
            }

            count += count(_x, b_max, c_max);

        }

        return count;

    }

    private int count(int _x, int b_max, int c_max) {

        int count = 0;
        for (int b = 0; b <= b_max; b++) {
            int c = _x - 2 * b;
            if (c < 0) {
                break;
            }

            if (c <= c_max) {
                count++;
            }
        }

        return count;
    }

Xは50の倍数という条件があるので計算しやすいように最初に50で割っています。これによって、「x = x / 50」と再定義することで、以下を満たす(a,b,c)の組を求める問題と同値になります。

 x = 10a + 2b + c

また、さらに移項すると

 x -10a = 2b + c

となります。最初のループである以下のメソッドは上記をベースに作成していて、aを0からA(aの最大値)までループさせつつ、「x -10a」が負の数になったらループが終了するようにしています。

    private int count(int x, int a_max, int b_max, int c_max) {
        int count = 0;
        for (int a = 0; a <= a_max; a++) {
            int _x = x - a * 10;

            if (_x < 0) {
                break;
            }

            count += count(_x, b_max, c_max);

        }

        return count;

    }

そして、「2b + c」の組の数は次のメソッドで計算しています。

    private int count(int _x, int b_max, int c_max) {

        int count = 0;
        for (int b = 0; b <= b_max; b++) {
            int c = _x - 2 * b;
            if (c < 0) {
                break;
            }

            if (c <= c_max) {
                count++;
            }
        }

        return count;
    }

これも先ほどと同様に「x = x -10a」と再定義すると

 x = 2b + c

となるので移項して

 x -2b = c

となります。あとは、bを0からB(bの最大値)までループさせつつ、「x -2b」が負の数になったらループが終了するようにしています。また、C(cの最大値)を超えなければカウントしています。

結果

解説をみてもらったらわかると思いますが、ちょっと無駄が多い印象だったので、これは提出はしませんでした。サンプルの3ケースがパスすることは確認しています。

改良版

色々と試行錯誤しつつ作成したのが以下のコードです。

public class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(count(
                Integer.parseInt(br.readLine()),
                Integer.parseInt(br.readLine()),
                Integer.parseInt(br.readLine()),
                Integer.parseInt(br.readLine())));
        pw.flush();
    }

    static int count(int A, int B, int C, int x) {
        x = x / 50;
        A = Math.min(x / 10, A);

        if (x % 2 == 0) {
            x = x / 2;
            C = C / 2;

        } else {

            if (C == 0)
                return 0;

            x = (x - 1) / 2;
            C = (C - 1) / 2;
        }

        int count = 0;

        for (int a = 0; a <= A; a++) {
            count += combinationNum(x - (5 * a), B, C);
        }
        return count;

    }

    static private int combinationNum(int x, int n1, int n2) {

        if (n1 < n2) {
            int tmp = n1;
            n1 = n2;
            n2 = tmp;
        }

        if (n1 + n2 < x)
            return 0;

        if (n1 <= x)
            return n1 + n2 - x + 1;

        if (n2 <= x)
            return n2 + 1;

        return x + 1;

    }

}

入出力部分

入出力部分は以下のようにしました。BufferedReaderやPrintWriterを使った形に変更しています。

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(count(
                Integer.parseInt(br.readLine()),
                Integer.parseInt(br.readLine()),
                Integer.parseInt(br.readLine()),
                Integer.parseInt(br.readLine())));
        pw.flush();
    }

これは最後に手を加えたところで、他の人のコードも参考にしました。最初に使ったScannerからBufferedReaderに変更したところ、実行時間で95ms→75msほどの性能アップしました。プロジェクト開発では可読性の方が重要なのでScannerを使った方が良いと思いますが、このような競技コンテストではBufferedReaderの方が良さそうです。

xとなる自然数の組

以下はサブメソッドで、xとなる整数の組の数を求めるメソッドです。

    static private int combinationNum(int x, int n1, int n2) {

        if (n1 < n2) {
            int tmp = n1;
            n1 = n2;
            n2 = tmp;
        }

        if (n1 + n2 < x)
            return 0;

        if (n1 <= x)
            return n1 + n2 - x + 1;

        if (n2 <= x)
            return n2 + 1;

        return x + 1;

    }

なぜこうなるのかは説明が長くなるのでここでは省略して、別途説明したいと思います。

メイン部分

メイン部分が以下です。

    static int count(int A, int B, int C, int x) {
        x = x / 50;
        A = Math.min(x / 10, A);

        if (x % 2 == 0) {
            x = x / 2;
            C = C / 2;

        } else {

            if (C == 0)
                return 0;

            x = (x - 1) / 2;
            C = (C - 1) / 2;
        }

        int count = 0;

        for (int a = 0; a <= A; a++) {
            count += combinationNum(x - (5 * a), B, C);
        }
        return count;

    }

先ほどのサブメソッドに渡すパラメータを調整して、サブメソッドに渡し、返却値を足していっています。xが奇数か偶数かで少々挙動が違うので、そこで場合分けしています。本当はaのループも外したかったのですが、現状ではこのままになっています。

結果

今回の結果は以下のようになりました。

  • 実行時間:70 ms
  • メモリ:21332 KB

感想

ちょっと気になったので改良しましたが、結果的にはそこまでスマートになりませんでした。また、性能も上がりはしましたが、そこまで劇的に上がったという訳ではないので、微妙だったかなと思います。(性能に関してはjavaを使っている時点で、あまり気にしないのが正解の気もします。)

個人的にはロジック考えるのは好きなので、もう少し改良できれば試してみたいと思いますが、普通ならそこまで考えず、動くものを単純に動かすのが正解だと思います。

コメント

タイトルとURLをコピーしました