ABC280A～Eの解答[Java]

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

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

※テンプレ等、実際の提出が見たい方は[こちら](https://atcoder.jp/contests/abc280/submissions?f.Task=&f.LanguageName=&f.Status=AC&f.User=viral)からどうぞ

## A - Pawn on a Grid
問題文は[こちら](https://atcoder.jp/contests/abc280/tasks/abc280_a)

`#`の位置を数え上げれば良いですね。
```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){
 
		//H、Wの受け取り
		int H = System.in.nextInt();
		int W = System.in.nextInt();

		//#の数え上げ
		int count = 0;
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)
				if(System.in.nextChar()=='#')
					count++;

		//答えの出力
		System.out.println(count);
 
		System.out.close();
	}
}
```
二重forは以下のように書き換えても良いかもしれません。
```A改.java
		//H行分繰り返す
		for(int i=0;i<H;i++){
			//Siを受け取って拡張for文で探す
			char[] S = System.in.next().toCharArray();
			for(char c:S)count += c=='#'?1:0;
		}
```
まぁ特に悩みはしなかったです。

## B - Inverse Prefix Sum
問題文は[こちら](https://atcoder.jp/contests/abc280/tasks/abc280_b)

$i$番目までの総和を記録しながら、$A_{i+1}$を計算して総和に加算する、というのを順に繰り返しました。
```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、Sの受け取り
		int N = System.in.nextInt();
		int[] S = System.in.nextInt(N);

		//これまでの総和を記録する変数
		long now = 0;

		//順に条件を満たすAiを求めて出力
		for(int num:S){
			System.out.print((num-now)+" ");
			now += num-now;
		}

		//念のため改行
		System.out.println();
 
		System.out.close();
	}
}
```
これもそこまで難しくないですね。

## C - Extra Character
問題文は[こちら](https://atcoder.jp/contests/abc280/tasks/abc280_c)

$i$番目に挿入された=$S$の$i$番目と$T$の$i$番目が異なるので、そのような$i$を探しました。
```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){
 
		//S、Tの受け取り
		String S = System.in.next();
		String T = System.in.next();

		//別変数に記録しておく
		int len = S.length();

		//0～lenまでに相違点が見つかったか記録する変数
		boolean find = false;

		//順に比較して探す
		for(int i=0;i<len;i++){
			if(S.charAt(i)!=T.charAt(i)){
				System.out.println(i+1);
				find = true;
				break;
			}
		}

		//Sの末尾に挿入されている時用
		if(!find)
			System.out.println(len+1);
 
		System.out.close();
	}
}
```
$S$を`S+" "`にしておけば最後の場合分けがいりませんでしたね。

## D - Factorial and Multiple
問題文は[こちら](https://atcoder.jp/contests/abc280/tasks/abc280_d)

事前に$K$の素因数を列挙してHashMapに記録して(keyは素因数、valueは個数)、各素因数が個数分表れる最小の$N!$を探し、それぞれの素因数での$N$の最大値を求めました。
```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){
 
		//Kの受け取り
		long K = System.in.nextLong();

		//素因数とその個数を記録するmap
		HashMap<Long,Integer> list = new HashMap<>();

		//素因数候補
		long div = 2;
		//√Kまで試す
		while(div*div<=K){

			//素因数ならKをそれで割っておく&listに記録
			if(K%div==0){
				list.merge(div,1,(i,j) -> i+j);
				K /= div;
			}else
				div++;
		}
		//最後のKも入れておく
		list.merge(K,1,(i,j) -> i+j);

		//答えを記録する変数(なんとなく2にしただけで、0でも-1でも良い)
		long ans = 2;

		//各素因数を個数分だけ持つN!を探す
		for(Long key:list.keySet()){

			//mult番目のkeyの倍数まで使う
			int mult = 0;
			//keyの数
			int count = 0;
			//mult番目のkeyの倍数の値
			long now = key;
			//countが目的の個数に達するまで繰り返す
			while(count<list.get(key)){
				mult++;
				//nowのkeyの個数をcountに加算
				while(now%key==0){
					now /= key;
					count++;
				}
				//nowを更新
				now = (mult+1)*key;
			}
			//temp!でちょうど条件を満たす
			long temp = key*mult;
			//ansより大きかったら更新
			if(ans<temp)
				ans = temp;
		}

		//答えの出力
		System.out.println(ans);
 
		System.out.close();
	}
}
```
素因数の数を数える方法がなかなか浮かばなくてペナルティを頂いてしまいました･･･。

## E - Critical Hit
問題文は[こちら](https://atcoder.jp/contests/abc280/tasks/abc280_e)

動的計画法で解きました。
$dp[i]:$残りの体力が$i$の時の攻撃回数の期待値の$\mathrm{mod}\ 998244353$
として$0$から順に更新して$dp[N]$を求めました。
```E.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、Pの受け取り
		int N = System.in.nextInt();
		int P = System.in.nextInt();

		//dp[i]:体力がiの時の攻撃回数の期待値
		long[] dp = new long[N+1];

		//0の時は操作しないので0、1の時は絶対1回なので1
		dp[0] = 0;
		dp[1] = 1;

		int mod = 998244353;

		//ダメージが1の時、2の時の確率を事前計算
		long div = System.modPow(100,mod-2,mod);
		long d1 = (100-P)*div%mod;
		long d2 = P*div%mod;

		//遷移
		for(int i=2;i<=N;i++){
			//2ダメージ与えたときの期待値
			long sum = (dp[i-2]+1)*d2%mod;
			//1ダメージ与えたときの期待値
			sum += (dp[i-1]+1)*d1%mod;
			//和の%modをdp[i]に
			dp[i] = sum%mod;
		}

		//体力がNの時の期待値をしゅつりょく
		System.out.println(dp[N]);
 
		System.out.close();
	}
}
```
想像よりサクッと解けました。

## 感想
A:グリッドに苦手意識があるのでAから出てくるのか･･･と面食らったが、そんなに難しくはなかった
B:理解するのに時間がかかってしまったが、これも易しい
C:Cにしては易しい？
D:ペナルティをいっぱい頂いたのが心残り･･･
E:Eにしては易しい？
って感じでした。

入水･･･ってなるはずが、ペナルティのせいかレートが5足りませんでした。非常に悔しい･･･。