AtCoder Beginners Selection(10問) を javaで解いてみた　～後編～

前回に引き続き、AtCoder Beginners Selectionをjavaで解いてみました。
まだ初めて間もないですが、最初は問題文を読むのも苦痛だったのが、スッと問題文が頭に入ってくるようになってきました。

### 第6問 ABC088B - Card Game for Two

配列のソートの問題です。
いろいろな方法があるかと思いますが、Arraysクラスの `sort()` メソッドを使用して配列のソートを行いました。

#### :large_orange_diamond: 引っかかった点
プリミティブ型の配列を `Arrays.sort()` でソートする場合、ソート順は自然順序で並び替えされる昇順のみサポートしています。配列の宣言をラッパークラスでなく、プリミティブ型で宣言すると `sort()` メソッドを使用するタイミングでエラーが表示されます。そのため、カードの数値を格納する配列はint型のラッパークラスであるInteger型で宣言しています。

:::note info
Arrays.sort()でコンペアレーターを適用する場合、プリミティブ型の配列に使えない
:::

```java:Main.java
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    /**
     * カードの数値を長さNの配列に格納する
     * 配列を降順にソートする
     * 交互に配列の数値を合計する
     * 二つの合計値の差分を出力
     */
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        // プリミティブ型で宣言してしまうと、降順sortで引っかかる
        Integer[] numbers = new Integer[N];
        int Alice = 0;
        int Bob = 0;

        for (int i = 0; i < N; i++) {
            numbers[i] = scan.nextInt();
        }

        // 配列を降順にソート
        Arrays.sort(numbers, Collections.reverseOrder());

        // 最大値から順番に数値を合計する
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                Alice += numbers[i];
            } else {
                Bob += numbers[i];
            }
        }

        System.out.println(Alice - Bob);
        scan.close();
    }
}
```

### ABC085B - Kagami Mochi
問題文を読んだとき配列の重複排除の問題だと思いましたが、解説ではバケット法という考え方を紹介していました。当記事では配列の重複排除の記法を載せますが、B問題ではバケット法で解ける問題が多いようなのｄ、バケット法について学ぶ必要があると思います。

```java:Main.java
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    /**
     * 鏡餅の枚数を長さNの配列に格納する
     * 配列内の重複した値を排除する
     * 配列の長さを出力
     */
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = scan.nextInt();
        }

        int count = Arrays.stream(numbers)
                                .distinct()
                                .toArray()
                                .length;

        System.out.println(count);
        scan.close();
    }
}
```

```java
        // HashSetを使用して重複を排除するパターン
        HashSet<Integer> set = new HashSet<>();
        for (int n : numbers) {
            set.add(n);
        }

        System.out.println(set.size());
```

### 第 8 問: ABC 085 C - Otoshidama

ロジックは、第4問と同じfor分を用いた全探索だったため、早めにわかりましたが、
ここで初めて実行時間がオーバーしてエラーになりました。
自力じゃ解決できず、解説を確認しました。

1秒間に処理できるfor分のループ回数は、1億回程度のようです。
下記のコードでは、3重ループとなっており最大で80億回のループ(Nの最大値が2000のため)が発生してしまいます。

```java
// 実行時間のオーバーになるコード
outer: for (a = 0; a <= N; a++) {
    for (b = 0; b <= N - a; b++) {
        for (c = 0; c <= N - (a + b); c++) {
            if (10000 * a + 5000 * b + 1000 * c == Y) {
                flg = true;
                break outer;
            }
        }
    }
}
```

`int c` は、N-(a+b)で求めることができるため、一番深いループは必要ありません。
2重ループであれば4百万とおりのため、実行時間に問題ありません。

```java:Main.java
import java.util.Scanner;

public class Main {

    
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int Y = scan.nextInt();
        boolean flg = false;
        int a = 0;
        int b = 0;
        int c = 0;

        outer: for (a = 0; a <= N; a++) {
            for (b = 0; b <= N - a; b++) {
                c = N - (a + b);
                if (10000 * a + 5000 * b + 1000 * c == Y) {
                    flg = true;
                    break outer;
                }
            }
        }

        if (flg) {
            System.out.println(a + " " + b + " " + c);
        } else {
            System.out.println(-1 + " " + -1 + " " + -1);
        }
    }
}
```

本日は、ここまでにします。
今後は、A問題やB問題の過去問に取り組んでいきます。