ABC311A～Eの解答[Java]

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

僕のライブラリは[提出結果](https://atcoder.jp/contests/abc311/submissions?f.Task=&f.LanguageName=Java&f.Status=AC&f.User=viral)よりご確認ください。
では、見ていきましょう。

## A - First ABC
問題文は[こちら](https://atcoder.jp/contests/abc311/tasks/abc311_a)

一文字ずつ受け取って、HashSet<Character>のsizeが3になったところを出力しました。
```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の受け取り
		int N = sc.nextInt();

		//出現した種類数を数える用
		HashSet<Character> set = new HashSet<>();

		//先頭から一文字ずつ受け取る
		for(int i=1;i<=N;i++){
			set.add(sc.nextChar());

			//ABC全部出たら出力して終了
			if(set.size()==3){
				out.println(i);
				break;
			}
		}
 
		out.close();
	}
}
```
今思えば、indexOfを使って最大値を答える方が楽だったかもしれません。
```A改.java
import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

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

		//各文字の出現位置の最大値を取る
		int ans = S.indexOf("A");
		ans = Math.max(ans,S.indexOf("B"));
		ans = Math.max(ans,S.indexOf("C"));

		//1-indexedに修正して出力
		System.out.println(ans+1);
	}
}
```

## B - Vacation Together
問題文は[こちら](https://atcoder.jp/contests/abc311/tasks/abc311_b)

最初に、一人でも`x`なら`x`で、全員`o`なら`o`である文字列を作り、一番`o`が連続している箇所を探しました。
```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、Dの受け取り
		int N = sc.nextInt();
		int D = sc.nextInt();

		//一人以上ダメな日を記録
		boolean[] isBad = new boolean[D];
		for(int i=0;i<N;i++){
			for(int j=0;j<D;j++){
				isBad[j] |= sc.nextChar()=='x';
			}
		}

		//今見ているところまでの連続しているoの数
		int now = 0;

		//最大値
		int ans = 0;

		//先頭から見ていく
		for(boolean flag:isBad){

			//全員暇なら加算
			if(!flag){
				now++;
			}

			//一人以上ダメなら直前までのoの長さをansに記録して0に
			else{
				ans = Math.max(ans,now);
				now = 0;
			}
		}

		//末尾のoも考慮する必要があるのでnowとansで大きい方を出力
		out.println(Math.max(ans,now));
 
		out.close();
	}
}
```
これはそんなに難しくないですね。

## C - Find it!
問題文は[こちら](https://atcoder.jp/contests/abc311/tasks/abc311_c)

[公式解説](https://atcoder.jp/contests/abc311/editorial/6820)にも書いてありますが、どこから探索しても閉路にたどり着くので頂点1からDFSをし、閉路を検出して出力しました。
```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、Aの受け取り
		int N = sc.nextInt();
		int[] A = sc.nextInt(N);

		//非再帰用Deque
		ArrayDeque<Integer> deq = new ArrayDeque<>();

		//頂点1からの距離
		int[] count = new int[N];
		Arrays.fill(count,-1); //初期化

		//頂点1から探索
		deq.add(0);
		int p = -1; //閉路の先頭を記録するための変数
		count[0] = 0;

		//DFS
		while(deq.size()>0){
			int now = deq.peekLast();

			//次の頂点は探索済み？
			if(count[A[now]-1]>-1){
				p = A[now]; //閉路先頭の記録
				break;//DFS終了
			}

			//更新
			count[A[now]-1] = count[now]+1;
			deq.add(A[now]-1);
		}

		//距離の差が閉路の頂点の数
		int[] ans = new int[count[deq.peekLast()]-count[p-1]+1];

		//後ろから埋めていけばそのままBの条件を満たす順序に格納できる
		for(int i=ans.length;i>0;i--)
			ans[i-1] = deq.pollLast()+1;
		out.println(ans.length);
		out.println(ans);
 
		out.close();
	}
}
```
おまけですが、UnionFindを使って解いたやつも載せときます。
```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、Aの受け取り
		int N = sc.nextInt();
		int[] A = sc.nextInt(N);

		//UnionFind
		UnionFind uf = new UnionFind(N+1);

		//今見ている頂点(なんとなく1で)
		int now = 1;

		//閉路が形成されるまでunite
		while(uf.unite(now,A[now-1]))
			now = A[now-1];

		//閉路先頭に
		now = A[now-1];

		//Bの作成用
		ArrayList<Integer> ans = new ArrayList<>();
		ans.add(now);

		//閉路先頭に戻るまで移動しながら格納
		while(A[now-1]!=ans.get(0))
			ans.add(now = A[now-1]);

		//出力するのに都合が良いのでint型配列に入れ直し
		int[] ans2 = new int[ans.size()];
		for(int i=0;i<ans.size();i++)
			ans2[i] = ans.get(i);

		//答えの出力
		out.println(ans.size());
		out.println(ans2);
 
		out.close();
	}
}
```

## D - Grid Ice Floor
問題文は[こちら](https://atcoder.jp/contests/abc311/tasks/abc311_d)

[公式解説](https://atcoder.jp/contests/abc311/editorial/6821)の省略されている$O(NM(N+M))$解法に当たるかと思います([ユーザー解説](https://atcoder.jp/contests/abc311/editorial/6834)のBFS版)。
```D.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、Sの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		char[][] S = sc.nextCharArray(N);

		//停止、通過したことがあるマスの記録
		boolean[][] checked = new boolean[N][M];
		checked[1][1] = true;

		//BFS用Deque
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		deq.add(1);
		deq.add(1);

		//BFS
		while(deq.size()>0){
			int x = deq.pollFirst();
			int y = deq.pollFirst();

			//上下左右に移動できるなら移動する(通過したところも記録しておく)
			//停止する箇所が探索済みでないならDequeに格納する
			if(S[x+1][y]=='.'){
				int nx = x+1;
				while(S[nx+1][y]=='.')
					checked[nx++][y] = true;
				if(!checked[nx][y]){
					deq.add(nx);
					deq.add(y);
					checked[nx][y] = true;
				}
			}
			if(S[x-1][y]=='.'){
				int nx = x-1;
				while(S[nx-1][y]=='.')
					checked[nx--][y] = true;
				if(!checked[nx][y]){
					deq.add(nx);
					deq.add(y);
					checked[nx][y] = true;
				}
			}
			if(S[x][y+1]=='.'){
				int ny = y+1;
				while(S[x][ny+1]=='.')
					checked[x][ny++] = true;
				if(!checked[x][ny]){
					deq.add(x);
					deq.add(ny);
					checked[x][ny] = true;
				}
			}
			if(S[x][y-1]=='.'){
				int ny = y-1;
				while(S[x][ny-1]=='.')
					checked[x][ny--] = true;
				if(!checked[x][ny]){
					deq.add(x);
					deq.add(ny);
					checked[x][ny] = true;
				}
			}
		}

		//通過、停止済みのマスの数え上げ
		int count = 0;
		for(int i=0;i<N;i++)
			for(int j=0;j<M;j++)
				if(checked[i][j])
					count++;

		//答えの出力
		out.println(count);
 
		out.close();
	}
}
```
実装汚い…。

## E - Defect-free Squares
問題文は[こちら](https://atcoder.jp/contests/abc311/tasks/abc311_e)

[公式解説](https://atcoder.jp/contests/abc311/editorial/6819)では左、上、左上のテーブルの最小値で更新していますが、左と左上、上と左上に分解して解きました。
```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 ) {
 
		//H、W、Nの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int N = sc.nextInt();

		//穴空きマスの記録
		boolean[][] isEmpty = new boolean[H+1][W+1];
		while(N-->0){
			int a = sc.nextInt();
			int b = sc.nextInt();
			isEmpty[a][b] = true;
		}

		//縦方向への空きマスの寄与のみを考えた時の、自分を右下とする最大の正方形の大きさ(辺の長さ)
		int[][] sumH = new int[H+1][W+1];
		for(int i=1;i<=H;i++)
			Arrays.fill(sumH[i],Integer.MAX_VALUE);
		for(int i=1;i<=H;i++)
			for(int j=1;j<=W;j++)
				if(!isEmpty[i][j])
					sumH[i][j] = Math.min(sumH[i-1][j],sumH[i-1][j-1])+1;
				else
					sumH[i][j] = 0;

		//横方向への空きマスの寄与のみを考えた時の、自分を右下とする最大の正方形の大きさ(辺の長さ)
		int[][] sumW = new int[H+1][W+1];
		for(int i=1;i<=H;i++)
			for(int j=1;j<=W;j++)
				if(!isEmpty[i][j])
					sumW[i][j] = Math.min(sumW[i-1][j-1],sumW[i][j-1])+1;

		//数え上げ用変数
		long sum = 0;

		//全マスの最大の正方形の大きさを加算
		//n×nが作れるなら(n-1)×(n-1)も作れるはずで、その要領で数え上げると
		//そのマスを右下とした正方形はn個作れるので
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				sum += Math.min(sumH[i][j],sumW[i][j]);
			}
		}

		//総和の出力
		out.println(sum);
 
		out.close();
	}
}
```
なんかいろいろとぐちゃぐちゃしちゃってますが、コンテスト中の焦り故の結果です…。

## 感想
A,B:易しい
C:最初びっくりしたけど非再帰DFSと気付いてからはサクッと
D:制約的に間に合うかな～とか思って実装した
E:なかなか思いつかなかった…
って感じでした。

Fねぇ…DPで、右側から更新したら良さそうだなぁ～とかは思いついたんですが、遷移の仕方とか持つべき状態とか思いつかなくてダメダメでした…。