ABC245A～Dの解答[Java]

## はじめに
入力のみ、提出時から変更してあります。他はなるべく提出時のままの方針です。

コンテスト中にはA,B,Dが解けました。Cはコンテスト後です。
では、見ていきましょう。

## A - Good morning
問題文は[こちら](https://atcoder.jp/contests/abc245/tasks/abc245_a)

if文で書いてみましょう。
まず、A>Cならば青木君が、A<Cならば高橋君が早く起きるのでそれを分岐します。
すると、それ以降のelseはA==C前提でコードが組めますので、条件はB>D(すなわち青木君の方が早く起きるとき)のみで分岐すれば良いです(同時刻なら高橋君の方が早く起きるので>に=は付けません)。
```A.java
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 D = sc.nextInt();

		//分岐させて正しい答えを出力する
		if(A>C)
			System.out.println("Aoki");
		else if(A<C)
			System.out.println("Takahashi");
		else if(B>D)
			System.out.println("Aoki");
		else
			System.out.println("Takahashi");
	}
}
```

なお、これは以下のように書くことも出来ます。

B、Dは高々59<2^6なので、A、Dを右シフトしてそれぞれB、Cを加算することで、ifとelseのみで済みます。

```A改.java
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 D = sc.nextInt();

		//高橋君が起きた時刻は青木君が起きた時刻より遅いか？(同時刻は含まない)
		if((A<<6)+B>(C<<6)+D)
			System.out.println("Aoki");
		else
			System.out.println("Takahashi");
	}
}
```

もちろん時間の定義にしたがってA*60+Bのようにしても同様に解けます。

## B - Mex
問題文は[こちら](https://atcoder.jp/contests/abc245/tasks/abc245_b)

普通に全探索をしました。
0から順に、Aに含まれていないかを確認して、含まれていれば1加算してまた探して…という感じです。
```B.java
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//値の取得
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i=0;i<N;i++)A[i] = sc.nextInt();

		//0から順に探す
		for(int i=0;true;i++){
			boolean Yes = true;

			//Aの中にあるか探す
			for(int j=0;j<N;j++){
				if(A[j]==i){
					Yes = false;
					break;
				}
			}

			//無ければ出力して終了
			if(Yes){
				System.out.println(i);
				System.exit(0);
			}
		}
	}
}
```

なお、事前にAをソートしてしまえば、Arrays.binarySearchの戻り値が0未満になるまで探すという手法もあります(要素中に同一の値があれば0以上、無ければ0未満が保証されているので)。

```B改.java
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//値の取得
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i=0;i<N;i++)A[i] = sc.nextInt();

		//Aのソート
		Arrays.sort(A);

		//初期値設定(++numberにするために、初期値は-1から)
		int number = -1;

		//0から順にA内にないものを探し、出力
		while(Arrays.binarySearch(A,++number)>=0){}
		System.out.println(number);
	}
}
```

直感的ではないのでちょっとわかりにくいかもしれませんが、記述自体はすっきりします。

## C - Choose Elements
問題文は[こちら](https://atcoder.jp/contests/abc245/tasks/abc245_c)

解説のままのコードです。
一番最初から見ている箇所までがtrueで、かつ次の数字を選ぶことは可能かをA、Bそれぞれで記録していくことで解けました。(いわゆるDPというやつです)。まぁ実際にコードを見た方が良いかなと思います(DPの説明が難しい…)。
```C.java
class Main{
	public static void main(String[] args){
		java.util.Scanner sc = new java.util.Scanner(System.in);

		//N、Kの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();

		//選択可能か見ていく為の配列
		boolean[] dpA = new boolean[N];
		boolean[] dpB = new boolean[N];
		dpA[0] = dpB[0] = true; //一番最初はtrue

		//A、Bの受け取り
		int[] A = new int[N];
		int[] B = new int[N];
		for(int i=0;i<N;i++){
			A[i] = sc.nextInt();
		}
		for(int i=0;i<N;i++){
			B[i] = sc.nextInt();
		}

		//二番目から順に、条件を満たすか記録していく
		for(int i=1;i<N;i++){

			//なんか好きだから三項演算子で
			if(dpA[i-1]){
				dpA[i] = Math.abs(A[i-1]-A[i])<=K?true:dpA[i];
				dpB[i] = Math.abs(A[i-1]-B[i])<=K?true:dpB[i];
			}
			if(dpB[i-1]){
				dpA[i] = Math.abs(B[i-1]-A[i])<=K?true:dpA[i];
				dpB[i] = Math.abs(B[i-1]-B[i])<=K?true:dpB[i];
			}
		}

		//最後まで選択可能だったらYes、そうでないならNoを出力
		if(dpA[N-1]||dpB[N-1])
			System.out.println("Yes");
		else
			System.out.println("No");
	}
}
```

詳しい説明は[公式解説](https://atcoder.jp/contests/abc245/editorial/3634)にまかせます(丸投げ)。

## D - Polynomial division
問題文は[こちら](https://atcoder.jp/contests/abc245/tasks/abc245_d)

高校数学で習った記憶がありますが、多項式の割り算で解けますね。

実装が少々面倒ですがCの最高次から順に見ていき、Aの最高次で割った値をAにかけてCから引く、というのを繰り返していけば答えが出ます。

筆算をイメージしてもらえればと思います。
```D.java
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//N、Mの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

		//添え字が0から始まることに注意！
		int[] A = new int[N+1];
		for(int i=0;i<=N;i++)A[i] = sc.nextInt();

		//同様に注意！
		int[] C = new int[N+M+1];
		for(int i=0;i<=N+M;i++)C[i] = sc.nextInt();

		//答えとなるBの長さ
		int lengthOfB = C.length-A.length + 1;

		//答えを記録する配列
		int[] answer = new int[lengthOfB];

		//順番にBを埋めていく
		for(int i=0;i<lengthOfB;i++){
			//今見ているCの係数が0ならスキップ
			if(C[C.length-1-i]==0){
				answer[i] = 0;
				continue;
			}

			//割り算をし、順にCから引いていく(筆算のイメージ)
			int temp = C[C.length-1-i] / A[A.length-1];
			for(int j=0;j<A.length;j++){
				C[C.length-1-i-j] -= A[A.length-1-j] * temp;
			}

			//答えを記録
			answer[i] = temp;
		}

		//記録した答えが逆順になっているので、後ろから出力
		for(int i=answer.length-1;i>0;i--){
			System.out.print(answer[i]+" ");
		}
		System.out.println(answer[0]);
	}
}
```
まだ高校の記憶が若干残ってて良かったです。

## 感想
A:易しい。
B:制約から全探索で良いかと思えたので良かった。
C:難しい…解説見ないと全然思いつかなかった…。
D:高校数学を懐かしく感じる問題だった。
って感じでした。

DP苦手ですね…精進が足りてないです…。