はじめに

Dr.Ken氏の、AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~という記事を読みました。

アルゴリズム系はJAVAで挑むものではない気がしますが、敢えてJAVA8的コードで解いてみます。
JAVA8といえば、Streamとラムダ式ですね(恐らく)。

注1)
AtCoderに通す用のコードではありません。
入出力部分は省略し、答えを返すメソッドとして実装しています。

注2)
問題概要等は、Dr.Ken氏のものを引用させていただいています。

第 1 問: ABC 086 A - Product (100 点)

【問題概要】
二つの正整数 $a$, $b$ が与えられます。 $a$ と $b$ の積が偶数か奇数か判定してください。

【数値例】
 $a = 3$
 $b = 4$
 答え: Even

【回答】

private static String answer1(int a, int b) {
    return (a % 2 == 0 || b % 2 == 0) ? "Even" : "Odd";
}

【コメント】
a か b が 2 で割れればOK。

第 2 問: ABC 081 A - Placing Marbles (100 点))

【問題概要】
0 と 1 のみから成る 3 桁の番号 s が与えられます。1 が何個含まれるかを求めてください。

【数値例】
 s = "101"
 答え: $2$

【回答】

private static long answer2(String s) {
    return s // "101"
        .chars() // ('1', '0', '1')
        .filter(c -> c == '1') // ('1', '1')
        .count(); // 2
    }

【コメント】
char のストリームに変換し、1 のみを抜き出してカウントします。

第 3 問: ABC 081 B - Shift Only (200 点)

【問題概要】
黒板に $N$ 個の正の整数 $A_1, \dots, A_N$ が書かれています。
すぬけ君は,黒板に書かれている整数がすべて偶数であるとき,次の操作を行うことができます。

  • 黒板に書かれている整数すべてを,$2$ で割ったものに置き換える。

すぬけ君は最大で何回操作を行うことができるかを求めてください。

【数値例】
 $N = 3$
 $A = (16, 12, 24)$
 答え: $2$

【回答】

private static int answer3(List<Integer> list) {
    return list.stream() // (16, 12, 24)
            .map(i -> Integer.toBinaryString(i)) // ("10000", "1100", "11000")
            .mapToInt(s -> s.length() - s.lastIndexOf("1") - 1) // (4, 2, 3)
            .min() // 2
            .getAsInt()
}

【コメント】
mapToInt 部分では、後ろに $0$ がいくつ付いているかをカウントしています。
(このようにロジックが覗くのは、ストリームの良い実装ではないかも知れません)

第 4 問: ABC 087 B - Coins (200 点)

【問題概要】
500 円玉を $A$ 枚、100 円玉を $B$ 枚、50 円玉を $C$ 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りあるでしょうか?

【コメント】
ジャバジャバした感じで書けませんでした。。
何かいい書き方があったら教えてください。

第 5 問: ABC 083 B - Some Sums (200 点)

【問題概要】
$1$ 以上 $N$ 以下の整数のうち、$10$ 進法で各桁の和が $A$ 以上 $B$ 以下であるものについて、総和を求めてください。

【数値例】
 $N = 20$
 $A = 2$
 $B = 5$
 答え: $84$

【回答】
※ Abc10 というクラスの中に作ってます。

private static long answer5(int n, int a, int b) {
    Set<Entry<Long, Long>> set = LongStream.range(1, n + 1).mapToObj(i -> i) // (1, ..., 20)
            .collect(Collectors.toMap(Abc10::getKey, Abc10::getValue)) // ({1: 1}, ..., {12: 3}, ..., {20: 2})
            .entrySet();

    return set.stream()
            .filter(m -> m.getValue() >= a) // {1: 1} とかは落ちる
            .filter(m -> m.getValue() <= b) // {15: 6} とかは落ちる
            .mapToLong(m -> m.getKey()) // keyのみ取得
            .sum(); // 足す
}

【回答補足】
※ Abc10 というクラスの中に作ってます。

private static long getKey(long l) {
    return l;
}

/*
 * すべての桁を足す
 */
private static long getValue(long l) {
    return String.valueOf(l) // "12"
            .chars() // ('1', '2')
            .mapToLong(Character::getNumericValue) // (1, 2)
            .sum(); // 3
}

【コメント】
key : 任意の数値
value : key の各桁の和
というハッシュマップを作り、filterで絞り込みます。

第 6 問: ABC 088 B - Card Game for Two (200 点)

【問題概要】
$N$ 枚のカードがあり、$i$ 枚目のカードには $a_i$ という数が書かれています。
Alice と Bob はこれらのカードを使ってゲームを行います。ゲームでは 2 人が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。
2 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2 人とも自分の得点を最大化するように最適戦略をとったとき、Alice は Bob より何点多くの得点を獲得できるかを求めてください。

【数値例】
 $N = 3$
 $a = (2, 7, 4)$
 答え: $5$

【回答】

private static int answer6(List<Integer> list) {
    List<MyInt> rev_list =list.stream() // (2, 7, 4)
            .sorted(Comparator.reverseOrder()) // (7, 4, 2)
            .map(MyInt::createMyInt)
            .collect(Collectors.toList());

    return rev_list.stream() // (7, 4, 2)
            .mapToInt(mi -> rev_list.indexf(mi) % 2 == 0 ? mi.i : -mi.i) // (7, -4, 2)
            .sum(); // 5
}

【回答補足】

class MyInt {
    public Integer i;

    public static MyInt createMyInt(int i) {
        MyInt mi = new MyInt();
        mi.i = i;
        return mi;
    }
}

【コメント】
降順に並べ替え、偶数番目を負の数にして合計します。
indexOfを使ってリスト内の位置を取得するため、Integerのラッパーを作っています。
(Integer型に対してそのままindexOfを使うと、最初に現れた数字の位置を返してしまうため)

第 7 問: ABC 085 B - Kagami Mochi (200 点)

【問題概要】
$N$ 個の整数 $d[0], d[1], \dots, d[N-1]$ が与えられます。
この中に何種類の異なる値があるでしょうか?

【数値例】
 $N = 4$
 $d = (8, 10, 8, 6)$
 答え: $3$

【回答】

    private static int answer7(List<Integer> list) {
        return new HashSet<Integer>(list).size();
    }
}

コメント
リストをセットに直してカウントしてターンエンド

第 8 問: ABC 085 C - Otoshidama (300 点)

【問題概要】
10000 円札と、5000 円札と、1000 円札が合計で $N$ 枚あって、合計金額が $Y$ 円であったという。このような条件を満たす各金額の札の枚数の組を 1 つ求めなさい。そのような状況が存在し得ない場合には -1 -1 -1 と出力しなさい。

【数値例】
 $N = 9$
 $Y = 45000$
 答え: $(4, 0, 5)$ など

【回答】

private static String answer8(int n, int y) {
    Wallet wallet = new Wallet(y);

    while(wallet.canExchange10000To1000(n))
        wallet.exchange10000To1000();

    while(wallet.canExchange10000To5000And1000(n))
        wallet.exchange10000To5000And1000();

    while(wallet.canExchange5000To1000(n))
        wallet.exchange5000To1000();

    while(wallet.canExchange10000To5000(n))
        wallet.exchange10000To5000();

    if(wallet.totalBillsCount() != n)
        wallet.setInvalidBills();

    return wallet.toString();
}

【回答補足】

class Wallet{
    /*
     * 持っている紙幣の数
     */
    private int bills_10000;
    private int bills_5000;
    private int bills_1000;

    /*
     * コンストラクタ
     * nを最小枚数で満たすように紙幣を持たせる
     */
    public Wallet(int total) {
        bills_10000 = total / 10000;
        bills_5000 = total % 10000 / 5000;
        bills_1000 = total % 10000 % 5000 / 1000;
    }

    /*
     * 両替できるか
     * nを越さない & 紙幣を持っている
     * walletがnを知るという実装は正直微妙
     */
    public boolean canExchange10000To1000(int n) {
        return n - totalBillsCount() >= 9 && bills_10000 > 0;
    }

    public boolean canExchange10000To5000And1000(int n) {
        return n - totalBillsCount() >= 5 && bills_10000 > 0;
    }

    public boolean canExchange10000To5000(int n) {
        return n - totalBillsCount() >= 1 && bills_10000 > 0;
    }

    public boolean canExchange5000To1000(int n) {
        return n - totalBillsCount() >= 4 && bills_5000 > 0;
    }

    /*
     * 総枚数の取得
     */
    public int totalBillsCount() {
        return bills_10000 + bills_5000 + bills_1000;
    }

    /*
     * 両替
     */
    public void exchange10000To1000() {
        bills_10000 -= 1;
        bills_1000 += 10;
    }

    public void exchange10000To5000And1000() {
        bills_10000 -= 1;
        bills_5000 += 1;
        bills_1000 += 5;
    }

    public void exchange10000To5000() {
        bills_10000 -= 1;
        bills_5000 += 2;
    }

    public void exchange5000To1000() {
        bills_5000 -= 1;
        bills_1000 += 5;
    }

    /*
     * だめな時は全部-1
     */
    public void setInvalidBills() {
        bills_10000 = -1;
        bills_5000 = -1;
        bills_1000 = -1;
    }

    /*
     * 表示用
     */
    @Override
    public String toString() {
        return bills_10000
                + ", "
                + bills_5000
                + ", "
                + bills_1000;
    }
}

【コメント】
長々とクラスを作成しましたが、やっていることはシンプルです。
1. $Y$ 円を満たす最小枚数の組み合わせを求める
2. $N$ 枚を越さないように、10000 円を 1000 円 * 10 枚に両替する
3. $N$ 枚を越さないように、10000 円を 5000 円 * 1 枚 + 1000 円 * 5 枚に両替する
4. $N$ 枚を越さないように、5000 円を 1000 円 * 5 枚に両替する
5. $N$ 枚を越さないように、10000 円を 5000 円 * 2 枚に両替する

第 9 問: ABC 049 C - Daydream (300 点)

【問題概要】
英小文字からなる文字列 $S$ が与えられます。
$T$ が空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで $S = T$ とすることができるか判定してください。

  • $T$ の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。

【数値例】
 $S$ = "dreameraser"
 答え: "YES"

【コメント】
ジャバジャバ解く方法が思いつかない!

第 10 問: ABC 086 C - Traveling (300 点)

【問題概要】
シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。AtCoDeer くんの旅行プランでは、時刻 $0$ に 点 $(0, 0)$ を出発し、$1$ 以上 $N$ 以下の各 $i$ に対し、時刻 $t_i$ に 点 $(x_i, y_i)$ を訪れる予定です。

AtCoDeer くんが時刻 $t$ に 点 $(x, y)$ にいる時、 時刻 $t+1$ には 点 $(x+1,y), (x−1,y), (x,y+1), (x,y−1)$ のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeer くんの旅行プランが実行可能かどうか判定してください。

【数値例】
 $N = 2$
 $(t, x, y) = (3, 1, 2), (6, 1, 1)$
 答え: "Yes"

【コメント】
ジャバジャバ解く方法が思いつかない!

以上

速度を犠牲にして、可読性・保守性を手に入れたのがJAVAだと思ってます。
今回解いていない問題は、解こうとするとどうしてもc++的なコードになってしまいます。
何かいい解き方を思いついたら追記します。

ほかにも、もっと良く書けるものがあったら教えてください。

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.