ABC304A～Fの解答[Java]

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

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

## A - First Player
問題文は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_a)

最年少をforで探してそこから$N$行出力しました。
```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、Aの受け取り
		int N = sc.nextInt();
		String[] S = new String[N];
		int[] A = new int[N];
		for(int i=0;i<N;i++){
			S[i] = sc.next();
			A[i] = sc.nextInt();
		}

		//最年少のindexを探す
		int index = -1;
		int min = Integer.MAX_VALUE;
		for(int i=0;i<N;i++){
			if(min>A[i]){
				min = A[i];
				index = i;
			}
		}

		//最年少から時計回りに
		for(int i=0;i<N;i++)
			out.println(S[(i+index)%N]);
 
		out.close();
	}
}
```
特に難しくはないですね。

## B - Subscribers
問題文は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_b)

$N$の桁数を$K$とすると、$\lfloor \frac{N}{\mathrm{max}(1,10^{K-3})} \rfloor \times \mathrm{max}(1,10^{K-3})$が答えです。
```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の受け取り
		int N = sc.nextInt();

		//上記の式の計算
		out.println(N/MathFunction.pow(10,String.valueOf(N).length()-3)*MathFunction.pow(10,String.valueOf(N).length()-3));
 
		out.close();
	}
}
```
$K$を入れる変数作ればもうちょっと見やすかったかな…。

## C - Virus
問題文は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_c)

BFSで解きました。
$N$が小さいので、感染している人と距離が$D$以下の人を$O(N)$で求めても十分高速です。
```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、D、座標の受け取り
		int N = sc.nextInt();
		int D = sc.nextInt();
		Point[] p = sc.nextPoint(N);

		//BFS
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		boolean[] isBad = new boolean[N];
		deq.add(0);
		isBad[0] = true;
		while(deq.size()>0){
			int now = deq.pollFirst();
			for(int i=0;i<N;i++){
				if(i==now||(p[i].x-p[now].x)*(p[i].x-p[now].x)+(p[i].y-p[now].y)*(p[i].y-p[now].y)>D*D)
					continue;
				if(!isBad[i]){
					isBad[i] = true;
					deq.add(i);
				}
			}
		}

		//感染してるか否かを出力
		for(boolean bool:isBad)
			out.println(bool?"Yes":"No");
 
		out.close();
	}
}
```
UnionFindを使った解法もあるそうですね。計算量の話が[ユーザー解説](https://atcoder.jp/contests/abc304/editorial/6520)にあるのでそれと合わせて読むと良いかも？

## D - A Piece of Cake
問題文は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_d)

上から何番目で左から何番目かをキーとしたHashMapで個数を数えて最大最小を探しました。
Mapのsizeが$(A+1)(B+1)$未満の時は最小値が0になることに注意しましょう。
```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 ) {
 
		//W、H、N、座標の受け取り
		int W = sc.nextInt();
		int H = sc.nextInt();
		int N = sc.nextInt();
		Point[] p = sc.nextPoint(N);

		//A、aの受け取り
		int A = sc.nextInt();
		int[] a = sc.nextInt(A);

		//B、bの受け取り
		int B = sc.nextInt();
		int[] b = sc.nextInt(B);

		//各イチゴがどこの区画に属するか記録
		HashMap<Point,Integer> map = new HashMap<>();
		for(Point point:p){
			int indexA = Searcher.downSearch(a,point.x);
			int indexB = Searcher.downSearch(b,point.y);
			map.merge(new Point(indexA,indexB),1,Integer::sum);
		}

		//各区画の最大最小値を探す
		int min = Integer.MAX_VALUE;
		int max = 0;
		for(int sum:map.values()){
			min = Math.min(min,sum);
			max = Math.max(max,sum);
		}

		//もし何も無い区画があれば最小値は0
		if(map.size()<(long)(A+1)*(B+1))
			min = 0;

		//答えの出力
		out.println(min+" "+max);
 
		out.close();
	}
}
```
最初`(A+1)*(B+1)`を`A*B`と書いてしまって1ペナです…悔しい…。

## E - Good Graph
問題文は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_e)

UnionFindを使って解きました。
先にグラフ$G$を構築し、$(\mathrm{root}(x_i),\mathrm{root}(y_i))$をHashSetに記録して、$(\mathrm{root}(p_i),\mathrm{root}(q_i))$がSetに含まれているかで判定しました。
```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の受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

		//Gの構築
		UnionFind uf = new UnionFind(N+1);
		while(M-->0){
			int u = sc.nextInt();
			int v = sc.nextInt();
			uf.unite(u,v);
		}

		//各組み合わせをsetに記録
		int K = sc.nextInt();
		HashSet<Point> set = new HashSet<>();
		while(K-->0){
			int x = uf.root(sc.nextInt());
			int y = uf.root(sc.nextInt());

			//入れ替えた組み合わせも記録しておく
			set.add(new Point(x,y));
			set.add(new Point(y,x));
		}

		//各クエリに対して答える
		int Q = sc.nextInt();
		while(Q-->0){
			int p = uf.root(sc.nextInt());
			int q = uf.root(sc.nextInt());

			//setに含まれていたらダメな組み合わせ
			out.println(set.contains(new Point(p,q))?"No":"Yes");
		}
 
		out.close();
	}
}
```
これは比較的早く気づけました。

## F - Shift Table
問題文は[こちら](https://atcoder.jp/contests/abc304/tasks/abc304_f)

[公式解説](https://atcoder.jp/contests/abc304/editorial/6511)の通りです。
```F.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();

		final int mod = 998244353;

		//約数の記録
		TreeSet<Integer> set = new TreeSet<>();
		set.add(1);
		for(int i=2;i*i<=N;i++){
			if(N%i==0){
				set.add(i);
				set.add(N/i);
			}
		}

		//数え上げ用
		long ans = 0;

		//重複削除用map
		HashMap<Integer,Long> map = new HashMap<>();

		//約数を小さい方から
		for(int num:set){

			//必ず働く必要のある日を記録
			boolean[] mustWork = new boolean[num];
			for(int i=0;i<N;i++)
				mustWork[i%num] |= S.charAt(i)=='.';

			//働かなくて良い日を数え上げ
			int count = 0;
			for(boolean flag:mustWork)
				if(!flag)
					count++;

			//重複を引いた総数
			long sum = MathFunction.modPow(2,count,mod)-map.getOrDefault(num,0L);

			//重複して数えてしまう候補をmapに記録
			for(int i=num;i<N;i+=num)
				map.merge(i,sum,(a,b)->(a+b)%mod);

			//答えを記録
			ans += sum;
			ans %= mod;
		}

		//重複を引く時に負数になる可能性があるので調製して出力
		out.println((mod+ans)%mod);
 
		out.close();
	}
}
```
最後あたりに気づきはしましたが、実装が間に合わなかった上にバグらせたので完敗です…。

## 感想
A:易しい
B:ちょっとウッってなった
C:BFSがCで出るようになったんだな～とか思った(過去にもあったような気がするけど)
D:最初解法が見えなくて焦った
E:UnionFindで解く問題はもう慣れてきたかも？
F:難しい…
って感じでした。

unratedになってしまったのは悲しいですが、次回以降への勉強になったのでヨシ！