ABC299A～Eの解答[Java]

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

では見ていきましょう。
なお、ライブラリの内容は[提出結果](https://atcoder.jp/contests/abc299/submissions?f.Task=&f.LanguageName=Java&f.Status=AC&f.User=viral)からご覧ください。

## A - Treasure Chest
問題文は[こちら](https://atcoder.jp/contests/abc299/tasks/abc299_a)

フラグで`|`の中かどうかを管理しながら調べました。
```A.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、Sの受け取り
		int N = sc.nextInt();
		String S = sc.next();

		//|の中かどうか
		boolean flag = false;

		//*が中にあったかどうか
		boolean in = false;
		for(int i=0;i<N;i++){

			//|を見つけたらflagを反転
			if(S.charAt(i)=='|')
				flag = !flag;

			//*を見つけたら中にあったかをinに代入
			if(S.charAt(i)=='*')
				in |= flag;
		}

		//中にあった？
		out.println(in?"in":"out");
 
		out.close();
	}
}
```
正規表現で表して検索する方法もありますが([原案者の実装](https://atcoder.jp/contests/abc299/editorial/6237)より)、エスケープが必要でなんか嫌だなぁと思ったのでこっちで実装しました。

## B - Trick Taking
問題文は[こちら](https://atcoder.jp/contests/abc299/tasks/abc299_b)

HashMapで各色をkey、最大値を持っている人の番号をvalueにして保持し、$T$が含まれているかどうかで条件分岐しました。
```B.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、T、C、Rの受け取り
		int N = sc.nextInt();
		int T = sc.nextInt();
		int[] C = sc.nextInt(N);
		int[] R = sc.nextInt(N);

		//key:色の番号、value:最大値を持っている人の番号
		HashMap<Integer,Integer> map = new HashMap<>();
		for(int i=0;i<N;i++){

			//Rがより大きい方のindexをvalueに
			map.merge(C[i],i,(s,t)->{
				if(R[s]<R[t])
					return t;
				return s;
			});
		}

		//Tがあったかどうかで条件分岐(0-indexedなので+1)
		if(map.containsKey(T))
			out.println(map.get(T)+1);
		else
			out.println(map.get(C[0])+1);
 
		out.close();
	}
}
```
そこまで難しくはなかったですね。

## C - Dango
問題文は[こちら](https://atcoder.jp/contests/abc299/tasks/abc299_c)

`-`の位置をArrayListに入れていき、前後の差から長さを調べて最大値を探しました。
```C.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、Sの受け取り
		int N = sc.nextInt();
		String S = sc.next();

		//-の位置をlistに入れる
		ArrayList<Integer> list = new ArrayList<>();
		for(int i=0;i<N;i++){
			if(S.charAt(i)=='-')
				list.add(i);
		}

		//-と隣り合うoの長さを前後をみて調べる
		int before = -1;
		int ans = 0;
		for(int i=0;i<list.size();i++){
			int max = Math.max(list.get(i)-before-1,(i+1==list.size()?N:list.get(i+1))-list.get(i)-1);
			ans = Math.max(ans,max);
			before = list.get(i);
		}

		//1以上のものが見つかればそれを、見つからなければ-1を
		out.println(ans>0?ans:-1);
 
		out.close();
	}
}
```
どうだって良いですけど`-o-o-`って眼鏡っぽいですね。

## D - Find by Query
問題文は[こちら](https://atcoder.jp/contests/abc299/tasks/abc299_d)

細かい説明は[公式解説](https://atcoder.jp/contests/abc299/editorial/6245)に任せますが、二分探索で求められると思い、それを実装しました。
```D.java
final class Main {
 
	private static final boolean autoFlush = true;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//Nの受け取り
		int N = sc.nextInt();

		//上下限設定
		int a = 1;
		int b = N;

		//暫定的な答え
		int ans = 1;

		//二分探索
		while(a-b<1){
			int c = (a+b)/2;
			out.println("? "+c);
			int result = sc.nextInt();
			if(result==0)
				a = (ans=c)+1;
			else
				b = c-1;
		}

		//答えの出力
		out.println("! "+ans);
 
		out.close();
	}
}
```
`!`が抜けてないか数回確認しました(過去に経験があるので…)。

## E - Nearest Black Vertex
問題文は[こちら](https://atcoder.jp/contests/abc299/tasks/abc299_e)

頂点$p_i$から距離$d_i$であるような頂点と$d_i$未満であるような頂点をそれぞれ列挙していき、頂点$p_i$から距離$d_i$であるようないずれかの頂点を黒で塗ることが可能か調べることで判定しました。
```E.java
final class Main {
 
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
 
	public static void main ( String[] args ) {
 
		//N、M、グラフ、Kの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] graph = sc.nextGraph(N,M);
		int K = sc.nextInt();

		//黒に塗るべき頂点の候補で、keyは頂点、valueはp、dのインデックス
		HashMap<Integer,ArrayList<Integer>> ok = new HashMap<>();

		//白に塗るべき頂点
		HashSet<Integer> ng = new HashSet<>();

		//全頂点からBFS
		for(int $=0;$<K;$++){
			int p = sc.nextInt();
			int d = sc.nextInt();
			int[] dist = new int[N+1];
			Arrays.fill(dist,Integer.MAX_VALUE);
			dist[p] = 0;
			ArrayDeque<Integer> deq = new ArrayDeque<>();
			deq.add(p);
			while(deq.size()>0){
				int now = deq.pollFirst();
				for(int next:graph[now]){
					if(dist[next]>dist[now]+1){
						dist[next] = dist[now]+1;
						deq.add(next);
					}
				}
			}

			//結果に合わせてok、ngを更新
			for(int i=1;i<=N;i++){
				if(dist[i]<d){
					ng.add(i);
					if(ok.containsKey(i))
						ok.remove(i);
				}
				if(dist[i]==d){
					if(!ng.contains(i)){
						if(ok.containsKey(i)){
							ok.get(i).add($);
						}
						else{
							ArrayList<Integer> temp = new ArrayList<>();
							temp.add($);
							ok.put(i,temp);
						}
					}
				}
			}
		}

		//全インデックスが含まれているか調べる
		HashSet<Integer> set = new HashSet<Integer>();
		for(ArrayList<Integer> list:ok.values()){
			set.addAll(list);
		}

		//K個全部候補に含まれていた=条件を満たすように塗ることができる
		if(set.size()==K){
			out.println("Yes");

			//答えの構築と出力
			int[] ans = new int[N];
			if(ok.size()>0){
				for(int index:ok.keySet())
					ans[index-1] = 1;
			}else
				ans[0] = 1; //K=0の時用に適当に塗る
			out.println(ans,"");
		}

		//一個でも条件を満たさないならNo
		else
			out.println("No");
 
		out.close();
	}
}
```
書き直したり消したりを繰り返してたので結構ごちゃごちゃになって時間をかけてしまいました…。

## 感想
A,B:易しい
C:最長の`o`を求める問題だと気づけばサクッといける
D:二分探索でいけそうかな～って思えたので良かった
E:ちょっと実装が重くなってしまったかな…
って感じでした。

A問題提出しようとしたときからBad Gatewayが出てしまっていたので非常に慌てました。