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
もう少し改良できそうな感じではありますが、十分かなと思います。
作成物
今回の作成物は以下に置いています。
コメント