AtCoderに登録したら解くべき精選過去問10をJavaで解いてみた

はじめに

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～にて紹介されていた問題をJavaで解いてみました。

上記の記事ではC++での解法が書かれていたり、他の言語で解いてみた記事が紹介されているので、ここではなるべくJava特有のメソッドなどを使ってみようと思います。
とはいえ、JavaはC++をベースにした言語ですので、C++で同様の実装が可能なのですが…

第1問: ABC 086 A - Product

2整数の積の偶奇を問う問題です。基本問題ですね。

Javaでは入力を受け取る際にはScannerにSystem.inを渡して使います。
また、受け取るデータの型によっていくつかのメソッドを使い分けます。

• 単語の場合はnext()
• 整数の場合はnextInt()
• 文字列（1行）の場合はnextLine()

今回は整数を扱うのでnextInt()を使っています。

補足ですが、整数を扱う場合にはnextInt()よりもInteger.parseInt(sc.next())の方が速かったり、そもそもScannerは遅いから自作Scannerメソッドを使ったりする人がいるらしいです。
気になる人はググってみてね。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if ((a * b) % 2 == 0)
            System.out.println("Even");
        else
            System.out.println("Odd");
    }
}

第2問: ABC 081 A - Placing Marbles

与えられた3桁の数字の中にある"1"を数える問題です。

数字を扱う問題ですが、文字列として扱うと解きやすいのでnext()を使います。
"0"と"1"のみで構成された文字列なので、"0"を取り除いた残りの文字列の長さを調べればそれが答えです。
replaceAll()で"0"を""に置換しましょう。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        s = s.replaceAll("0", "");
        System.out.println(s.length());
    }
}

第3問: ABC 081 B - Shift Only

いくつかの整数を同時に、いずれかの数が割り切れなくなるまで2で割るとき、何回割れるかを求める問題です。

ある数が2で割り切れるということは、2進数で表したときに1の位が0であるということと同じ意味です。
すなわち、ある数が2で何回割り切れるかは最下位から続く0の数を調べれば分かります。
全ての数のorを取った値に対してこの操作を行うと、最も2で割ることができる回数が小さい数についての答えを調べることができます。
最下位から続く0の数は、Integer.numberOfTrailingZeros()で調べることができます。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int bit = 0;
        for (int i=0; i<N; i++) {
            bit |= sc.nextInt();
        }
        System.out.println(Integer.numberOfTrailingZeros(bit));
    }
}

第4問: ABC 087 B - Coins

500円玉、100円玉、50円玉を使ってある金額を支払う方法が何通りあるかを求める問題です。

500円玉と100円玉の枚数をそれぞれfor文で決めて、50円玉の枚数はXとの差額で計算します。
問題の条件にXは50の倍数であることが記されているので、50円玉の枚数が小数になってしまう場合などは考慮する必要はありません。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int X = sc.nextInt();

        int res = 0;
        for (int a=0; a<=A; a++) {
            for (int b=0; b<=B; b++) {
                int c = (X - a * 500 - b * 100) / 50;
                if (c >= 0 && c <= C)
                    res++;
            }
        }

        System.out.println(res);
    }
}

第5問: ABC 083 B - Some Sums

N以下の数について、各桁の合計がA以上B以下の数の合計を求める問題です。

ここでは、素直に1以上N以下の各値について各桁の合計を調べていきます。
各桁の合計を計算しているのはwhile文の部分です。
n % 10で最下位の値をdigSumに加え、n /= 10で最下位の桁を捨てていきます。
10進数は2進数と比べて扱いが面倒で嫌ですね…

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();

        int sum = 0;
        for (int i=1; i<=N; i++) {
            int n = i;
            int digSum = 0;
            while (n > 0) {
                digSum += n % 10;
                n /= 10;
            }
            if (digSum >= A && digSum <= B)
                sum += i;
        }
        System.out.println(sum);
    }
}

第6問: ABC 088 B - Card Game for Two

数字の書かれた何枚かのカードがあり、それを2人で交互に取り、その合計を競うゲームを考えます。
このとき、先攻のプレイヤは後攻のプレイヤよりもどれだけ多くの数字を取ることができるかを求める問題です。

お互いに自身の得点が最大になるようカードを取るため、場にあるカードのうちで最大の数が書かれたカードを取っていきます。
すなわち、カードを降順にソートし、先頭から交互にカードを取っていくことになります。

配列のソートにはArrays.sort()を使います。
また、今回は降順にソートしたいため、2番目の引数にComparator.reverseOrder()を渡します。
ちなみに、Listのソートを行いたいときは、Collections.sort()を使います。
Javaでは配列よりもListを使うことの方が多いため、そちらを利用することの方が多いかもしれません。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Integer a[] = new Integer[N];
        for (int i=0; i<N; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a, Comparator.reverseOrder());

        int Alice = 0;
        int Bob   = 0;
        for (int i=0; i<N; i+=2) {
            Alice += a[i];
        }
        for (int i=1; i<N; i+=2) {
            Bob += a[i];
        }
        System.out.println(Alice - Bob);
    }
}

第7問: ABC 085 B - Kagami Mochi

様々なサイズのお餅がいくつかあるとき、異なるサイズのお餅のみを用いて最大何段の鏡餅を作ることができるかを求める問題です。

重複を除いた数を扱う問題では、Setが役に立ちます。
SetはListのようにいくつものオブジェクトを保存することができますが、重複するものについては無視されます。
全てのお餅のサイズをSetに追加し、最後にSetが持っているデータの数を数えれば簡単に答えが求まります。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Set<Integer> num = new HashSet<>();
        for (int i=0; i<N; i++) {
            int di = sc.nextInt();
            num.add(di);
        }
        System.out.println(num.size());
    }
}

第8問: ABC 085 C - Otoshidama

10000円札、5000円札、1000円札があり、その合計がN枚、Y円になるような組み合わせを求める問題です。

第4問と似たような問題ですね。
2重for文を使うなど、解法も似たような感じになっています。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Y = sc.nextInt();

        for (int a=0; a<=N; a++) {
            for (int b=0; b<=N-a; b++) {
                int c = N - a - b;
                int total = a * 10000 + b * 5000 + c * 1000;
                if (total == Y) {
                    System.out.println(a + " " + b + " " + c);
                    return;
                }
            }
        }

        System.out.println("-1 -1 -1");
    }
}

第9問: ABC 049 C - Daydream

ある文字列が、"dream", "dreamer", "erase", "eraser"を組み合わせて連結することで作れるかどうかを判定する問題です。

先頭から文字列を当てはめていくと、"dreamerase"の先頭が"dreamer"に一致してしまったり、"dreamererase"の先頭が"dream"に一致してしまうため、後ろからチェックしていきます。
後ろからですと、このような間違いは発生しません。

ある文字列が他の文字列のお尻に一致するかどうかを調べるためにはendsWith()を使います。
もちろん、ある文字列が他の文字列の頭に一致するかどうかを調べるstartsWith()もあります。

import java.util.*;

class Main {
    static String[] strs = {
        "dream",
        "dreamer",
        "erase",
        "eraser"
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();

        while (true) {
            boolean endsWithStr = false;
            for (String str: strs) {
                if (S.endsWith(str)) {
                    endsWithStr = true;
                    S = S.substring(0, S.length() - str.length());
                    break;
                }
            }
            if (!endsWithStr) {
                System.out.println("NO");
                break;
            }
            if (S.length() <= 0) {
                System.out.println("YES");
                break;
            }
        }
    }
}

と、書いてみたはいいものの、実はこの解答ではAtCoderでパスできません。MLEだそうです…
どうやら原因は文字列の生成のしすぎのようです。
改良を加え、endsWith()を使わないコードにしたらパスできたのですが、それを載せても面白くないので、別解を載せます。

---

単純に、それぞれの文字列を置換で削除していきます。
こちらの方法では、誤った削除がおこらないように削除する文字列の順番を工夫します。
dreamerはdreamより前に、eraserはeraseよりも前に、eraseとeraserはdreamerよりも前に削除をしましょう。

【追記】
この方法ですと、"dreameraseer"のような文字列がeraseとdreamerで構成できると誤認してしまいます。
置換の際には空文字列はなく使われていない文字に置換し、最後にその文字を削除すれば正しい結果が得られます。
ご指摘いただきました@CuriousFairy315 さん、ありがとうございます！

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();

        S = S.replaceAll("eraser",  "-");
        S = S.replaceAll("erase",   "-");
        S = S.replaceAll("dreamer", "-");
        S = S.replaceAll("dream",   "-");
        S = S.replaceAll("-", "");
        if (S.length() == 0)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

第10問: ABC 086 C - Traveling

座標(0, 0)を出発し、時刻tiに(xi, yi)にいることができるかどうかを判定する問題です。

時刻までに目的の座標にたどり着くことが可能であれば周囲をウロウロしておくことで時間調整ができるのですが、時刻の奇数時刻前に目的の座標にたどり着いてしまった場合はちょうどの時刻に目的の座標にいることができないことに注意が必要です。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int preT = 0;
        int preX = 0;
        int preY = 0;

        for (int i=0; i<N; i++) {
            int postT = sc.nextInt();
            int postX = sc.nextInt();
            int postY = sc.nextInt();

            int dt = postT - preT;
            int dist = Math.abs(postX - preX) + Math.abs(postY - preY);
            if ((dt < dist) || ((dist - dt) % 2 != 0)) {
                System.out.println("No");
                return;
            }

            preT = postT;
            preX = postX;
            preY = postY;
        }

        System.out.println("Yes");
    }
}

おわりに

私は競プロに手を出してまだ1ヶ月ほどのひよっこなので、もっと良い解法がたくさんありそうです。（コメントでぜひ教えてください！）

現在Javaはそんなに実行が遅い言語ではありませんが、CやC++と比べればまだまだ遅いですし、メモリも余計に食います。
実際、第9問なんかも前者の実装をC++で書いたら普通にパスできました。
AOJなどのように言語ごとに時間やメモリの制限の緩和があれば良いのですが、AtCoderではどの言語も平等です。

AtCoderで競プロをやる上では、C++を用いるのが一番良い気がします。（もちろん、他の言語で解くのも楽しいけどね！）
私自身、現在競プロのためにC++を勉強中です。
C++以外で競プロをやっている人は、これを期にC++も始めてみましょう！
（Javaの記事でC++をオススメするとは一体…）