ABC270A～Eの解答[Java]

## はじめに
今回はD以外はコンテスト中に、Dは解説を見てから解いたものを載せようと思います。

では、見ていきましょう。

## A - 1-2-4 Test
問題文は[こちら](https://atcoder.jp/contests/abc270/tasks/abc270_a)

1、2、4を二進数で表すと001、010、100となることから、それぞれの問題が解けたかはビットが立ってるかで判定できます。ということで、$A|B$が答えになりますね。
```A.java
class Main{

	static Library System = new Library(java.lang.System.in,java.lang.System.out);

	public static void main(String[] args)throws IOException{

		//A、Bの受け取り
		int A = System.in.nextInt();
		int B = System.in.nextInt();

		//答えの出力
		System.out.println(A|B);
 
		System.out.close();
	}
}
```
なんてことはないですね。

## B - Hammer 
問題文は[こちら](https://atcoder.jp/contests/abc270/tasks/abc270_b)

位置関係ごとに条件分岐させることで解きました。
```B.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//値の受け取り
		int X = System.in.nextInt();
		int Y = System.in.nextInt();
		int Z = System.in.nextInt();

		//Xまでまっすぐ進めるか？
		if(0<Z&&Z<Y||0<X&&(X<Y||0>Y))
			System.out.println(Math.abs(X));
		else if(Z<0&&Y<Z||0>X&&(X>Y||0<Y))
			System.out.println(Math.abs(X));
		else{

			//壁とゴールが同じ方向にあるとき
			if(X>0&&Y>0){
				if(X>Y&&Z<0)
					System.out.println(2*Math.abs(Z)+Math.abs(X));
				else
					System.out.println(-1);
			}else if(X<0&&Y<0){
				if(X<Y&&Z>0)
					System.out.println(2*Math.abs(Z)+Math.abs(X));
				else
					System.out.println(-1);
			}else{

				//違う方向ならXに直行
				System.out.println(Math.abs(X));
			}
		}
				
		System.out.close();
	}
}
```
最初条件が抜けててペナルティを頂いてしまいました。
もったいない･･･。

## C - Simple path
問題文は[こちら](https://atcoder.jp/contests/abc270/tasks/abc270_c)

DFSで解きました。
通った頂点をboolean型配列で記録し、$Y$に到着したら順にArrayListに記録して返しました。返ってきた物は逆順になっていることに注意しましょう(ちなみに、ArrayListをLinkedListに変えてaddFirstで記録すれば逆順にならなくて済みます)。
```C.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);

	//各種変数(DFS側で参照できるように)
	static boolean[] isUsed;
	static int Y;
	static ArrayList<ArrayList<Integer>> list;
 
	public static void main(String[] args)throws IOException{
 
		//N、X、Yの受け取り
		int N = System.in.nextInt();
		int X = System.in.nextInt();
		Y = System.in.nextInt();

		//通った場所か記録する変数
		isUsed = new boolean[N+1];

		//繋がってる頂点を記録するArrayList
		list = new ArrayList<ArrayList<Integer>>();
		for(int i=0;i<=N;i++)list.add(new ArrayList<Integer>());
		while(--N>0){
			int U = System.in.nextInt();
			int V = System.in.nextInt();
			list.get(U).add(V);
			list.get(V).add(U);
		}

		//Xは始点なのでtrueに
		isUsed[X] = true;

		//DFSで探す
		ArrayList<Integer> answer = dfs(X);
 
		//逆順に出力
		for(int i=answer.size()-1;i>=0;i--){
			System.out.print(answer.get(i));
			if(i==0)
				System.out.println();
			else
				System.out.print(' ');
		}
 
		System.out.close();
	}

	//DFS
	public static ArrayList<Integer> dfs(int now){

		//繋がってる頂点を調べる
		for(int next:list.get(now)){

			//行ったことあるならスルー
			if(isUsed[next])
				continue;

			//ゴール？
			if(next==Y){
				ArrayList<Integer> ans = new ArrayList<Integer>();
				ans.add(Y);
				ans.add(now);
				return ans;
			}

			//通過済みにしてDFS
			isUsed[next] = true;
			ArrayList<Integer> temp = dfs(next);

			//見つかった？
			if(temp!=null){
				temp.add(now);
				return temp;
			}
		}
		//見つからなかったらnullを
		return null;
	}
}
```
典型っちゃ典型な気がしました。

## D - Stones
問題文は[こちら](https://atcoder.jp/contests/abc270/tasks/abc270_d)

[公式解説](https://atcoder.jp/contests/abc270/editorial/4850)通りかと思います。
最初は二分探索で一番多く取れる$A_i$を探す問題だと思ってやったら半分くらいのケースで落ちました。
動的計画法ですね。
遷移の方法も公式解説のままです。
```D.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//各変数の受け取り
		int N = System.in.nextInt();
		int K = System.in.nextInt();
		int[] A = System.in.nextInt(K);

		//dp[i]：i個あったときの最適解
		int[] dp = new int[N+1];

		//いるかわからないけど1個の時を念のため
		dp[1] = 1;

		//遷移
		for(int i=2;i<=N;i++){
			int temp = A[0]+(i-A[0]-dp[i-A[0]]);
			for(int j=1;j<K&&A[j]<=i;j++){
				temp = Math.max(temp,A[j]+(i-A[j]-dp[i-A[j]]));
			}
			dp[i] = temp;
		}

		//N個の時の最適解を出力
		System.out.println(dp[N]);
 
		System.out.close();
	}
}
```
いやぁ･･･dpだろうなとは思ったんですがねぇ･･･遷移がわからず･･･無念･･･。

## E - Apple Baskets on Circle
問題文は[こちら](https://atcoder.jp/contests/abc270/tasks/abc270_e)

シミュレーションなんてやっていては到底終わりません。
そこで、1周するときにどうなるかを考えてみると、0以外の全ての場所が1個減っているということがわかります。ということで、$A$をソートして小さい方から順に見ていけばループ回数を特定できます。あとは$A_1$から順に、まだ0で無い場所を端数分引いてやれば答えが求まります。
```E.java
class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//N、Kの受け取り
		int N = System.in.nextInt();
		long K = System.in.nextLong();

		//何番目かも記録しておきたいので二次元で
		long[][] A = new long[N][2];
		for(int i=0;i<N;i++){
			A[i][0] = System.in.nextLong();
			A[i][1] = i;
		}

		//個数でソート
		System.sort(A);

		//食べたリンゴの総数
		long count1 = 0;
		//ループ回数
		long count2 = 0;
		//端数
		long tmp = 0;

		//少ない方から順に
		for(int i=0;i<N;i++){

			//このかごが空になるまでループしたときに食べる個数
			long temp = (N-i)*(A[i][0]-count2);

			//Kを超過してない？
			if(count1+temp<K){
				count1 += temp;
				count2 = A[i][0];
			}

			//Kを超過した場合は端数を調べてbreak
			else{
				tmp = (K-count1)%(N-i);
				count2 += (K-count1)/(N-i);
				break;
			}
		}

		//count2回ループしたときの各かごにある個数を記録
		long[] answer = new long[N];
		for(int i=0;i<N;i++){
			int ind = (int)A[i][1];
			answer[ind] = Math.max(0,A[i][0]-count2);
		}

		//端数合わせをしながら出力
		for(int i=0;i<N;i++){
			if(answer[i]==0)
				System.out.print(0);
			else if(tmp-->0)
				System.out.print(answer[i]-1);
			else
				System.out.print(answer[i]);
			if(i==N-1)
				System.out.println();
			else
				System.out.print(' ');
		}
 
		System.out.close();
	}
}
```
個人的にはDよりかは簡単でした。DP慣れてなさ過ぎでは･･･？

## 感想
A:易しい。
B:めんどくさい。
C:典型っぽい。特に悩みはしなかった。
D:難しい･･･。
E:ループ回数を特定すれば良いことに気付いてからはサクッと(ペナルティは頂いたけど)。
って感じでした。

DPね･･･難しいね･･･。精進するしかないですね。