前回に引き続き、AtCoder Beginners Selectionをjavaで解いてみました。
まだ初めて間もないですが、最初は問題文を読むのも苦痛だったのが、スッと問題文が頭に入ってくるようになってきました。
第6問 ABC088B - Card Game for Two
配列のソートの問題です。
いろいろな方法があるかと思いますが、Arraysクラスの sort() メソッドを使用して配列のソートを行いました。
引っかかった点
プリミティブ型の配列を Arrays.sort() でソートする場合、ソート順は自然順序で並び替えされる昇順のみサポートしています。配列の宣言をラッパークラスでなく、プリミティブ型で宣言すると sort() メソッドを使用するタイミングでエラーが表示されます。そのため、カードの数値を格納する配列はint型のラッパークラスであるInteger型で宣言しています。
Arrays.sort()でコンペアレーターを適用する場合、プリミティブ型の配列に使えない
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問題ではバケット法で解ける問題が多いようなのｄ、バケット法について学ぶ必要があると思います。
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();
}
}
// 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のため)が発生してしまいます。
// 実行時間のオーバーになるコード
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百万とおりのため、実行時間に問題ありません。
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問題の過去問に取り組んでいきます。