AtCoder (AtCoder Beginners Selection) [ABC085B,ABC085C]

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

問題:ABC085B – Kagami Mochi

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

問題概要

餅の数Nとそれぞれの餅(円形)の直径であるdが入力されるので、何段に重ねることができるかを求める問題です。直径が小さい時のみ重ねることができるので、同じ直径のものは重ねることができません。

回答言語

Java8 (OpenJDK 1.8.0)

作成コード(初期作成)

最初に作成したコードが以下です。

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(new Main(br).execute());
        pw.flush();
    }

    int n;
    int[] d;

    Main(BufferedReader br) throws Exception {
        n = Integer.parseInt(br.readLine());
        d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = Integer.parseInt(br.readLine());
        }
    }

    int execute() {
        Arrays.parallelSort(d);
        int r = 0;
        int b = 0;
        for (int di : d) {
            if (di != b) {
                r++;
                b = di;
            }
        }
        return r;
    }
}

解説

入出力部分は省略します。メインのロジックは以下の部分になります。

    int execute() {
        Arrays.parallelSort(d);
        int r = 0;
        int b = 0;
        for (int di : d) {
            if (di != b) {
                r++;
                b = di;
            }
        }
        return r;
    }

最初に入力をソートし小さい順に並べ替えています。その後、順番に値をチェックし、同じ値ではない(=後の直径の方が大きい)場合に、段数のカウントをしています。最終的にカウントした結果を返しています。

結果

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

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

作成コード(変更版)

最初のコードを作成した後、他の人のコードを眺めていたところ、重複しないものの数を数えるというアイディアがありました。それを参考に作成してみたのが以下のコードです。

public class Main {

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

        Set<Integer> set = new HashSet<>();

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            set.add(Integer.parseInt(br.readLine()));
        }
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(set.size());
        pw.flush();
    }
}

解説

入力をSetに順々にaddしていき、最後までaddが終わったら最終的にそのサイズを返却しています。Setは重複しないので同じ直径のものは取り除かれユニークなもの数が返却されています。

結果

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

  • 実行時間:72 ms
  • メモリ:21204 KB

性能的には最初のバージョンと余り変わらない(誤差レベル)かなと思います。

問題:ABC085C – Otoshidama

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

問題概要

10000円札、5000円札、1000円札が合計N枚入っているお年玉袋に対して、合計金額がY円という可能性があるか(お札の組み合わせがあるか)を判定する問題です。

可能性がある場合は、その場合のお札の組み合わせを空白区切で返却します。お札の組み合わせは複数ありえますが、どの組み合わせでもOKとなっています。

可能性がない場合は「-1 -1 -1」という文字列を返します。

回答言語

Java8 (OpenJDK 1.8.0)

作成コード

作成したコードが以下です。

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(new Main(br).execute());
        pw.flush();

    }

    int n, y;

    Main(BufferedReader br) throws Exception {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        y = Integer.parseInt(s[1]);
    }

    String execute() {
        int bill_10 = -1;
        int bill_05 = -1;
        int bill_01 = -1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n - i; j++) {
                int k = n - i - j;
                if (i * 10_000 + j * 5_000 + k * 1_000 == y) {
                    bill_10 = i;
                    bill_05 = j;
                    bill_01 = k;
                    break;
                }
            }
        }
        return bill_10 + " " + bill_05 + " " + bill_01;
    }
}

解説

入出力部分は省略します。メインのロジック部分が以下です。

    String execute() {
        int bill_10 = -1;
        int bill_05 = -1;
        int bill_01 = -1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n - i; j++) {
                int k = n - i - j;
                if (i * 10_000 + j * 5_000 + k * 1_000 == y) {
                    bill_10 = i;
                    bill_05 = j;
                    bill_01 = k;
                    break;
                }
            }
        }
        return bill_10 + " " + bill_05 + " " + bill_01;
    }

単純に全部の組み合わせを総当たりで試し、条件を満たすものがあればその組み合わせを返す様にしています。条件を満たすものがない場合は、初期値の-1を返しています。

結果

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

  • 実行時間:81 ms
  • メモリ:22868 KB

もう少し改良できそうな感じではありますが、十分かなと思います。

作成物

今回の作成物は以下に置いています。

https://github.com/masaki-code/java/tree/master/atcoder

コメント

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