ABC289A～Eの解答[Java]

## はじめに
今回はコンテスト中にDまで、コンテスト後にEまで解けたのでそれを載せようと思います。

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

## A - flip
問題文は[こちら](https://atcoder.jp/contests/abc289/tasks/abc289_a)

先頭から文字を見ていって`1`と`0`を反転させて出力しました。
```A.java
class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//Sの受け取り
		String S = System.in.next();

		//反転させて出力
		for(char c:S.toCharArray())
			System.out.print(c=='0'?1:0);

		//お気持ち程度の改行
		System.out.println();
 
		System.out.close();
	}
}
```
xorで解く方法とかもあるそうですが、そこまでは発想が出来ませんでした。

## B - レ
問題文は[こちら](https://atcoder.jp/contests/abc289/tasks/abc289_b)

ArrayDequeを二つ用いて、$i=1,2,...$について一つ目のArrayDequeの先頭に追加し、$a$に無ければ二つ目のArrayDequeの末尾に一つ目のArrayDequeを追加することでレ点を再現しました。
```B.java
class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、M、aの受け取り
		int N = System.in.nextInt();
		int M = System.in.nextInt();
		int[] a = System.in.nextInt(M);

		//aの添え字(aの今見ている箇所を指す)
		int index = 0;

		//全体の答え
		ArrayDeque<Integer> ans = new ArrayDeque<>();

		//レ点による反転を管理する方
		ArrayDeque<Integer> now = new ArrayDeque<>();

		//1から順に
		for(int i=1;i<=N;i++){

			//aにiがあればnowの先頭に追加
			if(index<M&&i==a[index]){
				index++;
				now.addFirst(i);
			}
			else{

				//とりあえず先頭に追加して、nowをansの末尾に
				now.addFirst(i);
				while(!now.isEmpty())
					ans.addLast(now.pollFirst());
			}
		}

		//ansを先頭から出力
		while(!ans.isEmpty())
			System.out.print(ans.pollFirst()+" ");

		//お気持ち程度の改行
		System.out.println();
 
		System.out.close();
	}
}
```
非常に悩んでしまいました…。こういう問題は苦手ですね…。

## C - Coverage
問題文は[こちら](https://atcoder.jp/contests/abc289/tasks/abc289_c)

問題文と制約からbit全探索で解ける物だと判断して解きました。
集合はboolean型配列で管理しています。
```C.java
class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、Mの受け取り
		int N = System.in.nextInt();
		int M = System.in.nextInt();

		//各集合を表す配列
		boolean[][] contain = new boolean[M][N+1];
		for(int i=0;i<M;i++){

			//aに合わせてtrueに
			int C = System.in.nextInt();
			while(C-->0){
				int a = System.in.nextInt();
				contain[i][a] = true;
			}
		}

		//答え
		int ans = 0;

		//bit全探索
		for(int i=0;i<1<<M;i++){

			//iに合わせてそれぞれの論理和を作製
			boolean[] sum = new boolean[N+1];
			for(int j=0;j<M;j++){
				if((i&(1<<j))>0){
					for(int k=1;k<=N;k++){
						sum[k] |= contain[j][k];
					}
				}
			}

			//全部trueならansに加算
			boolean isGood = true;
			for(int j=1;j<=N;j++){
				isGood &= sum[j];
			}
			if(isGood){
				ans++;
			}
		}

		//答えの出力
		System.out.println(ans);
 
		System.out.close();
	}
}
```
今になってint型で集合を管理できたなと思いました。

## D - Step Up Robot
問題文は[こちら](https://atcoder.jp/contests/abc289/tasks/abc289_d)

動的計画法で解きました。
$\mathrm{dp}[i]$:$i$段目に到達可能か
という感じで管理して遷移させました。
```D.java
class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、A、Mの受け取り
		int N = System.in.nextInt();
		int[] A = System.in.nextInt(N);
		int M = System.in.nextInt();

		//モチがある場所をsetに追加
		HashSet<Integer> mochi = new HashSet<Integer>();
		while(M-->0)
			mochi.add(System.in.nextInt());

		//Xの受け取り
		int X = System.in.nextInt();

		//dpテーブル
		boolean[] dp = new boolean[X+1];
		dp[0] = true;

		//0段目から順に、行ける場所に対して論理和を取る(配るDP)
		for(int i=0;i<X;i++){

			//到達不可なら弾く
			if(mochi.contains(i))
				continue;

			for(int j=0;j<N&&i+A[j]<=X;j++){
				dp[i+A[j]] |= dp[i];
			}
		}

		//X段目に到達可能だった？
		System.out.println(dp[X]?"Yes":"No");
 
		System.out.close();
	}
}
```
これは比較的早く思いつきました。

## E - Swap Places
問題文は[こちら](https://atcoder.jp/contests/abc289/tasks/abc289_e)

各ケースに対して、高橋君、青木君が同時にどこにいるかという情報を持ってBFSを行ないました。
何故間に合うかの説明は[公式解説](https://atcoder.jp/contests/abc289/editorial/5726)にあります。
```E.java
import java.util.Scanner;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.awt.Point;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		//Tの受け取り
		int T = sc.nextInt();

		//出力高速化用
		StringBuilder ans = new StringBuilder();
		Test:while(T-->0){

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

			//隣接リストの構築
			ArrayList<ArrayList<Integer>> route = new ArrayList<>();
			for(int i=0;i<=N;i++)
				route.add(new ArrayList<>());
			while(M-->0){
				int u = sc.nextInt();
				int v = sc.nextInt();
				route.get(u).add(v);
				route.get(v).add(u);
			}

			//特に効力は無いが、自明なものは弾く
			if(C[0]!=C[N-1]){

				//set[高橋君][青木君]:高橋君と青木君の位置が探索済みか？
				boolean[][] set = new boolean[N+1][N+1];

				//Point用のArrayDequeとそこまでのコスト用のArrayDeque
				ArrayDeque<Point> bfsP = new ArrayDeque<>();
				ArrayDeque<Integer> bfsC = new ArrayDeque<>();

				//初期状態を追加
				bfsP.add(new Point(1,N));
				bfsC.add(0);
				set[1][N] = true;

				//BFS
				while(bfsP.size()>0){

					//今の状態とそこまでのコストを取り出す
					Point now = bfsP.pollFirst();
					int cost = bfsC.pollFirst();

					//到達できたなら出力して次のケースへ
					if(now.x==N&&now.y==1){
						ans.append(cost);
						ans.append("\n");
						continue Test;
					}

					//今いる所から移動できる場所を探す
					for(int nextT:route.get(now.x)){
						for(int nextA:route.get(now.y)){

							//二点の色が違う？
							if(C[nextT-1]!=C[nextA-1]){

								//到達済みでない？
								if(!set[nextT][nextA]){

									//setに記録してArrayDequeに追加
									set[nextT][nextA] = true;
									bfsP.add(new Point(nextT,nextA));
									bfsC.add(cost+1);
								}
							}
						}
					}
				}
			}

			//ここまで来た=移動できなかったので-1を出力
			ans.append(-1);
			ans.append("\n");
		}

		//答えの出力
		System.out.println(ans.toString());
	}
}
```
本番中に気づけなかったのが悔しいです…。

## 感想
A:易しい
B:超大変
C:bit全探索を知っていれば比較的早く発想出来そう
D:DPを知っていれば(以下同文)行けない段に注意
E:BFSで間に合うと思わなかった…
って感じでした。

いやぁ…精進不足ですね。もっと頑張ります。