AtCoder (AtCoder Beginners Selection) [ABC088B]

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

問題

ABC088B – Card Game for Two

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

問題概要

N枚のカードが場に置かれており、AとBの2人が交互にカードを取っていきます。カードを全て取り終わった際の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

備考

今回のコードですが、入力の文字列を読み込んですぐに配列に変換していますが、それを分離したところ少し早くなりました。ただ、余り大きな違いでもないので今回は省略したいと思います。

作成物

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

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

コメント

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