AtCoderの問題を解いてみます。今回は初心者向けの問題のAtCoder Beginners Selectionの４回目です。
問題
ABC088B – Card Game for Two
https://atcoder.jp/contests/abs/tasks/abc088_b
問題概要
N枚のカードが場に置かれており、AとBの２人が交互にカードを取っていきます。カードを全て取り終わった際のAとBのカードの点数の差を求める問題です。
回答
言語
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[] ai;
Main(BufferedReader br) throws Exception {
int n = Integer.parseInt(br.readLine());
int[] ai = new int[n];
int i = 0;
for (String a : br.readLine().split(" ")) {
ai[i] = Integer.parseInt(a);
i++;
}
Arrays.parallelSort(ai);
this.n = n;
this.ai = ai;
}
int execute() {
int result = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
result += ai[n - i - 1];
} else {
result -= ai[n - i - 1];
}
}
return result;
}
}解説
以下は入力（標準入力の読み込み）部分です。
Main(BufferedReader br) throws Exception {
int n = Integer.parseInt(br.readLine());
int[] ai = new int[n];
int i = 0;
for (String a : br.readLine().split(" ")) {
ai[i] = Integer.parseInt(a);
i++;
}
Arrays.parallelSort(ai);
this.n = n;
this.ai = ai;
}最初にカードの枚数Nが入力されるので、そのサイズの配列を用意しています。その後、カード（に書かれた数字）がスペース区切りで入力されるので、それを配列に設定しています。
配列の中身は、最後にArraysのparallelSortメソッドでソートをしています。調べた感じ、sortメソッドとparallelSortメソッドのどちらが早いかは配列のサイズによる様なのですが、今回はparallelSortメソッドにしました。
以下はAとBの点数の差（最終的な出力）を計算し返却するメソッドです。
int execute() {
int result = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
result += ai[n - i - 1];
} else {
result -= ai[n - i - 1];
}
}
return result;
}
事前にソートしているので、配列は小さい順に並んでいます。なので、配列の最後から順にカードをとる様にしています。Aの合計とBの合計をそれぞれ計算してからその差を計算しても良いのですが、最終的に同じになるので都度足し引きする様にしています。
結果
今回の結果は以下のようになりました。
- 実行時間：75 ms
- メモリ：21204 KB
備考
今回のコードですが、入力の文字列を読み込んですぐに配列に変換していますが、それを分離したところ少し早くなりました。ただ、余り大きな違いでもないので今回は省略したいと思います。
作成物
今回の作成物は以下に置いています。
コメント