AtCoderにJavaで出るための対策～AtCoder Beginners Selection編～

AtCoder Beginners Selectionをやっていきます。
自分で解きながら備忘録という意味でも解説を載せています。
パッと自分で解法が思いつかなかったときは、AtCoderに載っているユーザー解説などを参考に、Java版のコードにしたものを回答として載せています。

以下、問題のページです。

• PracticeA Welcome to AtCoder

1. ABC086A Product
2. ABC081A Placing Marbles
3. ABC081B Shift only
4. ABC087B Coins
5. ABC083B Some Sums
6. ABC088B Card Game for Two
7. ABC085B Kagami Mochi
8. ABC085C Otoshidama
9. ABC049C 白昼夢
10. ABC086C Traveling

問題

注意

Javaを使うときは、クラス名Mainにしてください。mainではコンパイルエラーになります。
引用：PracticeA - Welcome to AtCoder

PracticeA - Welcome to AtCoder

公式の回答

import java.util.*;
public 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();
		// 文字列の入力
		String s = sc.next();
		// 出力
		System.out.println((a+b+c) + " " + s);
	}
}

解説

• Scanner sc = new Scanner(System.in);では、標準入力を受け取ります。
  System.inは、 「標準」入力ストリームです。
• nextInt()：入力の次のトークンをintとしてスキャンします。
  ※標準入力から次の整数を読み取ります。
• next()：このスキャナから次の完全なトークンを検索して返します。
  ※標準入力から空白文字で区切られた次の単語や文字列を読み取ります。
• System.out.println：「標準」出力ストリームです。

追加知識

• nextDouble()：入力の次のトークンをdoubleとしてスキャンします。
  ※標準入力から次の小数を読み取ります。
• nextLine()：スキャナを現在行の先に進めて、スキップした入力を返します。
  ※標準入力から1行全体を読み取ります。
• hasNextInt()：このスキャナの入力内の次のトークンが、nextInt()メソッドを使ってデフォルト基数のint値として解釈可能な場合にtrueを返します。
  ※hasNextInt()メソッドは、次の入力が整数であるかどうかを判定します。条件に応じて処理を分岐させることができます。

引用

• System （Java SE 11 & JDK 11 ）
• Scanner （Java Platform SE 8 ）
• 【Java】ユーザー入力処理を行うScannerクラスの使い方 #初心者 - Qiita

ABC086A - Product

自分の回答

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		// スペース区切りの整数の入力
		int b = sc.nextInt();
		// 積
		int prod = a * b ;
		// 奇数か偶数か判定する
		if (prod%2==0){
		    System.out.println("Even");
		}else{
		    System.out.println("Odd");
		}
	}
}

解説

演算の仕方
今回は、積を求めるときと、偶数奇数を判定するときに、演算子を使用しています。

演算子	読み方	意味	使用例
+	プラス	足し算を行う演算子	5 + 5
-	マイナス	引き算を行う演算子	7 - 3
*	アスタリスク	掛け算を行う演算子	7 * 3
/	スラッシュ	割り算を行う演算子	7 / 3
%	パーセント	剰余（じょうよ）演算子。割り算の余り	7 % 3

上記表は、一週間で身につくJava言語の基本|第2日目：演算と変数 より引用

判定
if~elseを用いています。
演算子は、以下を参考にしてください。

演算子	意味	使用例
>	より大きい	a > 0
>=	以上	a >= 0
<	より小さい	a > 0
<=	以下	a <= 0
==	等しい	a == 0
!=	等しくない	a != 0

ABC081A - Placing Marbles

自分の回答

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字列の入力
		String s = sc.next();
		// 1の数を格納するための変数を定義
		int count = 0;
		// 1の数を数える
		for (int i = 0; i < s.length(); i++) {
		    if (s.charAt(i) == '1') {
		        count++;
		    }
		}
		// 出力
		System.out.println(count);
	}
}

解説

今回は、最初に文字列として1行読み込んだあとに、charAtを用いて、1つずつ文字を抜き出しています。
また、変数名.length()で、文字列の長さを取得しています。

charAtについて

変数名.charAt(値)

• 数字は、左から0でスタートする
• 一番最後の文字の位置は文字列.length() – 1

引用：【Java】charAtメソッド（n番目の文字を抜き出す） #文字列操作 - Qiita

参考：String （Java Platform SE 6）

繰り返し処理
今回は、for文を使って繰り返し処理をしています。

for ( 初期化処理 ; 条件式 ; 増分処理 ){
    処理
}

一週間で身につくJava言語の基本|第4日目：繰り返し処理より引用

ABC081B - Shift only

回答

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
      int a = sc.nextInt();
      // 整数aが偶数の場合は、操作を行う
      int count = 0;
      while (a % 2 == 0) {
        // 整数aを2で割って更新する
        a /= 2;
        // 結果を1つ増やす
        count++;
      }
      // 最小値を更新する
      res = Math.min(res, count);
    }

    // 結果を出力する
    System.out.println(res);
  }
}

AtCoder Beginners Selectionの実施記録（Java） #AdventCalendar2022 - Qiita
より引用

解説

• whileで、条件があう間（今回は、すべての数が偶数の間）処理を行っています。

whlie(条件式）{
    処理
}

引用：一週間で身につくJava言語の基本|第4日目：繰り返し処理

• Integer.MAX_VALUE：intに設定可能な最大値231-1を保持する定数
  引用：Integer （Java Platform SE 8 ）
• min(int a, int b)：2つのint値のうち小さいほうを返します。
  引用：Math （Java Platform SE 8 ）

考え方

以下の、入力例1の処理を下に説明します。

3
8 12 40

int n = sc.nextInt();で、「3」を読み取っています。
for文はnになるまでの間、aを読み取ります。
while文は、aの値が偶数の間、処理を行います。
都度、試行回数の最小値を更新していき、その最小値を答えとして出力します。

for文の回数	while文の回数	aの値	countの値
1回目		8
	1回目	4(a/2)	1
	2回目	2(a/2)	2
	3回目	1(a/2)	3
2回目		12
	1回目	6(a/2)	1
	2回目	3(a/2)	2
3回目		40
	1回目	20(a/2)	1
	2回目	10(a/2)	2
	3回目	5(a/2)	3

ABC087B - Coins

自分の回答

import java.util.Scanner;

public 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 count = 0;
    // a,b,cの数の組み合わせをfor文で求める
    for (int i = 0;i<=a;i++){
        for(int j = 0;j<=b;j++){
            for(int k = 0;k<=c;k++){
                // xになるとき、countをプラスする
                if((500*i+100*j+50*k)==x){
                    count++;
                }
            }
        }
    }
    // 結果を出力する
    System.out.println(count);
  }
}

解説

概ね、今までの知識で解ける問題です。
for文のネストがありますが、ABC081B - Shift onlyと同じような考え方で解くことができます。
ポイントとしては、int i = 0;i<=a;i++の<=の部分です。
0枚という選択肢もあるので0からスタートしaの枚数まで処理を行うというところでミスをしないようにしましょう。

ABC083B - Some Sums

回答

AtCoder ABC 083 B - Some Sums （6Q, 灰色, 200 点） - けんちょんの競プロ精進記録を参考にJava版にしました。

import java.util.*;

public class Main {
    // 整数 n の各桁の和を求める関数
    public static int calc(int n) {
        int res = 0;
        while (n > 0) {
            res += n % 10;
            n /= 10;
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        int res = 0;
        for (int n = 1; n <= N; n++) {
            int wa = calc(n);
            if (wa >= A && wa <= B) res += n;
        }
        System.out.println(res);
    }
}

解説

概ね、今までの知識で解ける問題です。

考え方は、以下、けんちょんさんのブログを参考にさせていただきました。

各桁の和を求める部分を関数化すると考えやすくなるので、これからは整数 n の各桁の和を求める関数を calc(int n) などとする。
そうすると、n=1,2,…,N に対して、calc(n) が A 以上 B 以下になるものについて、その総和を求めればよい。

AtCoder ABC 083 B - Some Sums （6Q, 灰色, 200 点） - けんちょんの競プロ精進記録

ABC088B - Card Game for Two

回答

以下のABC088-B - Card Game for Two を解く - 考えて競プロするを参考に、Java版の回答を作成しました。

import java.util.*;
import java.util.Arrays;
import java.util.Collections;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[101];
        for (int i = 0; i < N; i++){
            A[i] = sc.nextInt();
        }
        Arrays.sort(A);
        for (int f = 0, l = A.length - 1; f < l; f++, l--){
            int temp = A[f];
            A[f]  = A[l];
            A[l] = temp;
        }
        int a = 0;
        int b = 0;
        for (int i = 0; i < A.length; i++) {
            if (i % 2 == 0) {
                a += A[i];
            } else {
                b += A[i];
            }
        }
        System.out.println(a-b);
    }
}

解説

以下のABC088-B - Card Game for Two を解く - 考えて競プロするを参考にしました。
つまり、大きな方を取っていくはず→偶数番目、奇数番目に取っていく、という考え方で解けます。

2人のプレイヤーがN枚のカードを交互に取っていく
それぞれが取ったカードに書かれた数字の合計を最大にしようとするとき
先攻は後攻に対して何点差をつけられるか、という問題

常に数字が最大のものを取るようにしてシミュレーションを行う
最後に各自の合計の差を取って出力する

Python（Kenkoroさん回答）や、C++(hamayanhamayanさん回答)ではサクッと降順にできるようでしたが、配列の要素を昇順・降順にソートする（sort）によると、Javaのソートは昇順しか対応していないようです。
そのため、以下の部分で、降順に直しています。

for (int f = 0, l = A.length - 1; f < l; f++, l--){
    int temp = A[f];
    A[f]  = A[l];
    A[l] = temp;
}

ABC085B - Kagami Mochi

回答

Kagami Mochi ［AtCoder Beginner Contest 085 B］ - はまやんはまやんはまやんを参考に、Java版の回答を作成しました。

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[101];
        for (int i = 0; i < N; i++){
            D[i] = sc.nextInt();
        }
        Set<Integer> se = new HashSet<Integer>();
    
        for (int i = 0; i < N; i++){
            se.add(D[i]);
        }
        int ans = se.size();
        
        System.out.println(ans);
    }
}

解説

Kagami Mochi ［AtCoder Beginner Contest 085 B］ - はまやんはまやんはまやんを参考にしました。
以下の考え方です。
JavaのHashSetを用いて重複を削除し、その要素数を求めています。

今回は順番を入れ替えてもOKなので、貪欲に作っていくことを考える。
貪欲に作るには一番下は最大の餅にすればいい。
下から二番目は二番目に大きい餅にすればいい。
注意すべきなのは同じ大きさの餅は置けないということ。
そのため、貪欲においていくと餅の大きさの種類数だけおけることになる。
　
N個の数の種類数を求めるには、setにいれて個数を数えればいい。
Kagami Mochi ［AtCoder Beginner Contest 085 B］ - はまやんはまやんはまやんより引用

HashSetの使い方は、【Java】 HashSetの使い方ガイド | 初心者向けチュートリアル #Java入門 - Qiita
を参考にしました。
宣言方法
Set<型> 変数名 = new HashSet<型>();
値の追加
set.add(値);
要素の数
変数名.size()

ABC085C - Otoshidama

回答

Otoshidama ［AtCoder Beginner Contest 085 C］ - はまやんはまやんはまやんを参考に、Java版の回答を作成しました。

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Y = sc.nextInt();
        for (int a = 0; a < N + 1; a++) {
            for(int b = 0; b < N + 1; b++) {
                int c = N - (a + b);
                if (0 <= c) {
                    if (10000 * a + 5000 * b + 1000 * c == Y) {
                        System.out.println(a+" "+b+" "+c);
                        return;
                    }
                }
            }
        }
        System.out.println("-1 -1 -1\n");
    }
}

解説

Otoshidama ［AtCoder Beginner Contest 085 C］ - はまやんはまやんはまやんを参考にしました。
10000円札：a枚
5000円札：b枚
1000円札：N-(a+b)枚
c = N - (a + b)とし、Y = 10000 * a + 5000 * b + 1000 * cとなるものを全探索していきます。

10000円と5000円と1000円の枚数a,b,cを全探索する。
このまま全探索するとO(N^3)でTLEするので、a,bのみ全探索する。
するとcはN-(a+b)となり一意に定まるので大丈夫。
これはO(N^2)。あとは、合計がYになるかを判定して、なれば答える。
どれもならないなら-1
オーバーフローするかもと思いlong longを使った。
Otoshidama ［AtCoder Beginner Contest 085 C］ - はまやんはまやんはまやんより引用

ABC049C - 白昼夢

自分の回答

import java.util.*;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        // 後ろから単語を削除していく
        while (true) {
            if (s.endsWith("eraser")) {
                s = s.substring(0, s.length() - 6);
            } else if (s.endsWith("erase")) {
                s = s.substring(0, s.length() - 5);
            } else if (s.endsWith("dreamer")) {
                s = s.substring(0, s.length() - 7);
            } else if (s.endsWith("dream")) {
                s = s.substring(0, s.length() - 5);
            } else {
                break;
            }
        }
        
        // すべての単語が削除されて空になればYES、残っていればNO
        if (s.isEmpty()) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

解説

はじめ、私は、matchesとreplaceを使って、すべて変更できたらYES、できなかったらNOにしようと考えていました。
すると、dreameraserのとき、dreamerとaserとなってしまい、うまくいきません。
そこで、後ろからチェックします。
そうすることで、うまくチェックできるようになります。

• endsWith：この文字列が、指定された接尾辞で終るかどうかを判定します。
• substring：この文字列の部分文字列である文字列を返します。
• isEmpty：length()が0の場合にのみ、trueを返します。

引用：String （Java Platform SE 8 ）

ABC086C - Traveling

回答

Traveling ［AtCoder Regular Contest 089 / AtCoder Beginner Contest 086 C］ - はまやんはまやんはまやんを参考に、Java版の回答を作成しました。

import java.util.Scanner;

public class Main {
    static int N;
    static int[] T = new int[101010];
    static int[] X = new int[101010];
    static int[] Y = new int[101010];

    static String solve() {
        int pt = 0, px = 0, py = 0;
        for (int i = 0; i < N; i++) {
            int d = Math.abs(px - X[i]) + Math.abs(py - Y[i]);
            int dt = T[i] - pt;
            if (dt < d) return "No";
            if ((dt - d) % 2 == 1) return "No";

            pt = T[i];
            px = X[i];
            py = Y[i];
        }
        return "Yes";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            T[i] = sc.nextInt();
            X[i] = sc.nextInt();
            Y[i] = sc.nextInt();
        }
        sc.close();
        System.out.println(solve());
    }
}

解説

各区間について独立に実現可能か考える。
(px, py)から(X[i], Y[i])へ時間ptから時間T[i]で遷移可能かを判定する。
2つの座標を距離dは
d = abs(px - X[i]) + abs(py - Y[i])
である。これは移動は上下左右でしか行えないため、マンハッタン距離を距離とする。
使える時間dtは
dt = T[i] - pt
である。

まず自明なこととしてdt < dであるなら実現不可能である。
最短距離で移動しても間に合わないためである。

あとは、その場にとどまらずに移動できるかであるが、「dt - dが偶数であるなら移動できる」と言える。
詳しく言うと

最短距離で移動した後に使える時間がdt-d
目標の座標を右へ1つ移動->左へ1つ移動で目標の座標に戻るという動作で時間の調整ができる
この時間の調整で目標の座標に最後にとどまれるのはdt-dが偶数のときだけ

各区間で実現可能性を確かめて、全て実現可能ならYes
1つでも実現不可能ならNo
Traveling ［AtCoder Regular Contest 089 / AtCoder Beginner Contest 086 C］ - はまやんはまやんはまやんより引用

用語

マンハッタン距離とは？

座標平面上の2点 A($a_{1}$,$a_{2}$),B($b_{1}$,$b_{2}$)の間の距離を
$d(A,B)=|a_{1}-b_{1}|+|a_{2}-b_{2}|$
で測ったものを$L^1$距離(マンハッタン距離)と言う。
L1距離（マンハッタン距離）の意味と性質 | 高校数学の美しい物語より引用

CC 表示-継承 3.0,リンク

static 変数とは？

staticキーワード（修飾子）を付けて宣言される変数であり、すべてのオブジェクト（インスタンス）で共有される共通の情報となる。あるオブジェクトからクラス変数の値を変更すると、その他のすべてのオブジェクトに影響が及ぶため、オブジェクト全体に共通する情報を扱いたい場合に使用する。
Javaのstatic修飾子：クラス変数（static変数）、クラスメソッド（staticメソッド） #Java - Qiitaより引用

abs
absは、絶対値を求めるものです。
Javaでは、Math.abs(int値)を使い、これでint値の絶対値を返します。

参考：Math （Java Platform SE 8 ）

終わりに

AtCoder Beginners Selectionを解いてみて、色々な知識がつきました。
会社でもJavaを使いそうな感じなのでJavaでやってみましたが、AtCoderのための知識みたいな部分も結構必要そうなので、継続して学習しないといけないなという感じです。
間違っていることなどあれば、コメントから教えていただければ幸いです。
ここまで読んでいただきありがとうございました。