ABC300A～Gの解答[Java]

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

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

## A - N-choice question
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_a)

$A+B$を、$C$を受け取りながら探しました。
```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、A、Bの受け取り
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();

		//探すもの
		int ans = A+B;

		//順に受け取って探す
		for(int i=1;i<=N;i++){
			if(sc.nextInt()==ans){
				out.println(i);
				break;
			}
		}
 
		out.close();
	}
}
```
まぁ問題は無さそうですね。

## B - Same Map in the RPG World
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_b)

縦方向のシフト、横方向のシフトを全通り試しながら一致するか調べました。
```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 ) {
 
		//H、Wの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();

		//A、Bの受け取り
		char[][] A = sc.nextCharArray(H);
		char[][] B = sc.nextCharArray(H);

		//シフト回数全探索
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){

				//一致しているか調べる
				boolean isSame = true;
				for(int k=0;k<H;k++){
					for(int l=0;l<W;l++){
						isSame &= A[(i+k)%H][(j+l)%W]==B[k][l];
					}
				}

				//一致してたら終わり
				if(isSame){
					System.out.println("Yes");
					return;
				}
			}
		}

		//ループを抜けた=解が見つからなかったのでNo
		out.println("No");
 
		out.close();
	}
}
```
これもそこまで難しくはないですね。

## C - Cross
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_c)

全マスを調べて、`#`であるならそこを中心とするバツ印の大きさを調べました。
```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 ) {
 
		//H、Wの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();

		//Cの受け取り
		char[][] C = sc.nextCharArray(H);

		//答え用の配列
		int[] ans = new int[Math.min(H,W)];

		//全探索
		for(int i=1;i<H-1;i++){
			for(int j=1;j<W-1;j++){

				//#のマスならバツ印の大きさを求める
				if(C[i][j]=='#'){
					int k = 1;
					for(;;k++){
						if(i-k<0||H<=i+k||j-k<0||W<=j+k)
							break;
						boolean isTrue = true;
						isTrue &= C[i-k][j-k]=='#';
						isTrue &= C[i+k][j+k]=='#';
						isTrue &= C[i-k][j+k]=='#';
						isTrue &= C[i+k][j-k]=='#';
						if(!isTrue)
							break;
					}

					//バツ印ならansに加算
					if(k>1){
						ans[k-2]++;
					}
				}
			}
		}

		//答えの出力(空白区切り)
		out.println(ans);
 
		out.close();
	}
}
```
これもそこまで悩まないですね。ちょっとだけめんどくさいですけど。

## D - AABCC
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_d)

適当に$\sqrt{N}$までの素数を予め列挙しておき、$a$、$b$、$c$を全探索しました。
```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の受け取り
		long N = sc.nextLong();

		//適当な大きさまでの素数を列挙
		int[] primes = MathFunction.primes((int)Math.sqrt(N));

		//数え上げ
		int ans = 0;
		for(int i=0;function(primes[i],primes[i],primes[i])<=N;i++){
			for(int j=i+1;function(primes[i],primes[j],primes[j])<=N;j++){
				for(int k=j+1;function(primes[i],primes[j],primes[k])<=N;k++){
					ans++;
				}
			}
		}

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

	//メソッド化した方が楽そうだったので書いた
	private static long function(long a,long b,long c){
		return a*a*b*c*c;
	}
}
```
入力例2からそんなに数が多くないと気づけたので早めに実装できました。

## E - Dice Product 3
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_e)

動的計画法で解きました。
TreeMapを用いて、keyになる確率をvalueに持つようにして保持し、小さい方から取り出して遷移しました。
なお$\frac{1}{5}$をかけている理由は、1が0回出て遷移する確率、1が1回出て遷移する確率、1が2回出て遷移する確率、…という風に考えて確率を求めると
$$\sum_{k=0}^{\infty}{\frac{1}{6} \times \frac{1}{6^k}}=\frac{1}{5}$$
になるからです。
```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の受け取り
		long N = sc.nextLong();

		//DP用のMap
		TreeMap<Long,Long> map = new TreeMap<>();
		map.put(1L,1L);

		final int mod = 998244353;

		//事前に5^-1 mod 998244353を求めておく
		final long div = MathFunction.modPow(5,mod-2,mod);

		//遷移
		while(map.size()>0&&map.firstKey()<N){
			Map.Entry<Long,Long> entry = map.pollFirstEntry();
			long num = entry.getKey();
			long p = entry.getValue();
			for(int i=2;i<7;i++){
				if(num*i>N)
					break;
				map.merge(num*i,p*div%mod,(s,t)->(s+t)%mod);
			}
		}

		//Nに到達できたならその確率を出力
		if(map.size()>0)
			out.println(map.pollFirstEntry().getValue());

		//Nに到達できなかったなら確率は0
		else
			out.println(0);
 
		out.close();
	}
}
```
最初$\frac{1}{6}$をかけていたので答えが合わなくて混乱してました…。

## F - More Holidays
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_f)

[公式解説](https://atcoder.jp/contests/abc300/editorial/6274)の通りです。
```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、M、K、Sの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		long K = sc.nextLong();
		String S = sc.next();

		//xの数の累積和
		int[] count = new int[N+1];
		for(int i=0;i<N;i++)
			count[i+1] = count[i]+(S.charAt(i)=='x'?1:0);

		//答え用変数
		long ans = 0;

		//始点を決めて終点を求める
		for(int i=1;i<=N;i++){
			final int index = i;
			long sum = Searcher.downSearch(i,(long)N*M,K,s->s/N*count[N]+count[(int)(s%N)]-count[index-1]);
			ans = Math.max(ans,sum-i+1);
		}

		//最大値を出力
		out.println(ans);
 
		out.close();
	}
}
```
全然気づけませんでした…。他の解説も読んで身につけたいです。

## G - P-smooth number
問題文は[こちら](https://atcoder.jp/contests/abc300/tasks/abc300_g)

[公式解説](https://atcoder.jp/contests/abc300/editorial/6275)の通りです。
高速化のためにArrayListではなく長めの配列を用いています。
```G.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、Pの受け取り
		long N = sc.nextLong();
		int P = sc.nextInt();

		//P以下の素数の列挙
		int[] primes = MathFunction.primes(P);

		//半分全列挙用の配列
		long[] list1 = new long[10000000];
		long[] list2 = new long[10000000];
		int tail1 = 0; //末尾
		int tail2 = 0; //末尾
		list1[tail1++] = 1; //初期値代入
		list2[tail2++] = 1; //初期値代入

		//順に素数を見ていく
		for(int p:primes){

			//小さい方にかけていく
			if(tail2<tail1){
				int len = tail2;
				for(int i=0;i<len;i++){
					long num = list2[i]*p;
					while(num<=N){
						list2[tail2++] = num;
						num *= p;
					}
				}
			}
			else{
				int len = tail1;
				for(int i=0;i<len;i++){
					long num = list1[i]*p;
					while(num<=N){
						list1[tail1++] = num;
						num *= p;
					}
				}
			}
		}

		//ソート
		Arrays.sort(list1,0,tail1);
		Arrays.sort(list2,0,tail2);

		//数え上げ
		long ans = 0;
		int index = tail2;
		for(int i=0;i<tail1;i++){
			while(0<index&&list1[i]>N/list2[index-1])
				index--;
			ans += index;
		}

		//答えのしゅつりょく
		out.println(ans);
 
		out.close();
	}
}
```
半分全列挙自体は知っていましたが、コンテスト中に使えたことが無い…まだまだ身についてない証拠ですね…。

## 感想
A,B,C:易しい
D:答えがそんなに大きくないことに気付けば難しくない
E:1が出たときは考えなくて良いと発想できれば簡単めかも？
F:いろいろ考えたけど思いつけなかった…
G:何も思いつかなかった…
って感じでした。

今回は何事も無く終わって良かったです。これまでの平和のありがたみを感じました。