ABC298A～Eの解答[Java]

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

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

なお、用いられている自作ライブラリは[提出結果](https://atcoder.jp/contests/abc298/submissions?f.Task=&f.LanguageName=&f.Status=AC&f.User=viral)からご確認ください。

## A - Job Interview
問題文は[こちら](https://atcoder.jp/contests/abc298/tasks/abc298_a)

`o`が含まれていたか、`x`が含まれていなかったかがわかれば良いので、forで全部見ていきました。
```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();

		//oとxの存在確認用
		boolean isGood = false;
		boolean isBad = false;
		for(char c:sc.nextCharArray()){
			isGood |= c=='o';
			isBad |= c=='x';
		}

		//条件満たしてる？
		out.println(isGood&&!isBad?"Yes":"No");
 
		out.close();
	}
}
```
String型で受け取ってcontainsメソッドを用いる方が簡潔に書けましたね。

## B - Coloring Matrix
問題文は[こちら](https://atcoder.jp/contests/abc298/tasks/abc298_b)

問題文そのままを二重for分で実装しました。
```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();

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

		//各状態で条件を満たしているか管理する用の変数
		boolean isTrue1 = true;
		boolean isTrue2 = true;
		boolean isTrue3 = true;
		boolean isTrue4 = true;

		//全部確認していく
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				isTrue1 &= A[i][j]==1?B[i][j]==1:true;
				isTrue2 &= A[N-j-1][i]==1?B[i][j]==1:true;
				isTrue3 &= A[N-i-1][N-j-1]==1?B[i][j]==1:true;
				isTrue4 &= A[j][N-i-1]==1?B[i][j]==1:true;
			}
		}

		//どれか一個は条件を満たしたか？
		out.println(isTrue1||isTrue2||isTrue3||isTrue4?"Yes":"No");
 
		out.close();
	}
}
```
forの中はコピペして書いたんですが、書き換え忘れてペナルティを頂いてしまいました…。
確認、大事。

## C - Cards Query Problem
問題文は[こちら](https://atcoder.jp/contests/abc298/tasks/abc298_c)

`TreeMap<Integer,Integer>`を用いて各値が何個ずつ入っているかを管理しました。
各値が入っている箱も、`HashMap<Integer,TreeSet<Integer>>`で管理しました。
```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、Qの受け取り
		int N = sc.nextInt();
		int Q = sc.nextInt();

		//箱の中身用
		ArrayList<TreeMap<Integer,Integer>> box = new ArrayList<>();

		//各値が入っている箱の番号用
		HashMap<Integer,TreeSet<Integer>> map = new HashMap<>();

		//箱の準備
		for(int i=0;i<=N;i++)
			box.add(new TreeMap<>());

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

			//クエリ1
			if(q==1){

				//i、jの受け取り
				int i = sc.nextInt();
				int j = sc.nextInt();

				//箱に追加
				box.get(j).merge(i,1,(s,t)->s+t);

				//iが出現するのが初めてなら追加しておく
				if(!map.containsKey(i)){
					map.put(i,new TreeSet<>());
				}

				//箱の情報を追記
				map.get(i).add(j);
			}

			//クエリ2
			else if(q==2){

				//iの受け取り
				int i = sc.nextInt();

				//各値を昇順に取り出し
				for(Map.Entry<Integer,Integer> e:box.get(i).entrySet()){

					//含まれている数だけ出力
					int num = e.getValue();
					while(num-->0)
						out.print(e.getKey()+" ");
				}
				out.println();
			}

			//クエリ3
			else{

				//iの受け取り
				int i = sc.nextInt();

				//箱の番号を昇順に出力
				for(Integer num:map.get(i))
					out.print(num+" ");
				out.println();
			}
		}
 
		out.close();
	}
}
```
ちょっと重めの実装になってしまった…。
TreeMap、TreeSetで管理しなくても、その都度ソートすれば良いということにコンテスト後に気付きました。

## D - Writing a Numeral
問題文は[こちら](https://atcoder.jp/contests/abc298/tasks/abc298_d)

加えられる、削除されるを`ArrayDeque<Integer>`で管理し、ローリングハッシュみたいにクエリ3で出力すべき値を更新していくことで解きました。
```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 ) {
 
		//Qの受け取り
		int Q = sc.nextInt();

		//初期値1
		long now = 1;

		//あまり取る用
		final int mod = 998244353;

		//追加、削除される値を管理する用
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		deq.add(1);

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

			//クエリ1
			if(q==1){

				//xの受け取り
				int x = sc.nextInt();

				//追加
				deq.add(x);

				//元の値を10倍してxを足した値と同じなのでそれを求めておく
				now = (now*10+x)%mod;
			}

			//クエリ2
			else if(q==2){

				//先頭の値の取り出し
				int x = deq.pollFirst();

				//x*1000...%modで引く
				now -= x*MathFunction.modPow(10,deq.size(),mod)%mod;

				//負の値になっている可能性があるのでその時はmodを加算
				if(now<0)
					now += mod;
			}

			//クエリ3
			else
				out.println(now);
		}
 
		out.close();
	}
}
```
これは比較的早く思いつきました。

## E - Unfair Sugoroku
問題文は[こちら](https://atcoder.jp/contests/abc298/tasks/abc298_e)

動的計画法で解きました。
$\mathrm{dp}[i][j]$を$i$回サイコロを振ったときに$j$にいる確率とし、以下のように遷移しました。

$\mathrm{dp1}[i+1][j] = \sum_{k=j-P}^{j-1}{\mathrm{dp1}[i][k]} \times P^{-1}$
$\mathrm{dp2}[i+1][j] = \sum_{k=j-Q}^{j-1}{\mathrm{dp2}[i][k]} \times Q^{-1}$

求める答えは$\sum_{i=1}^N{dp1[i][N]} \times \sum_{j=i}^N{dp2[j][N]}$です。
```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、A、B、P、Qの受け取り
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int P = sc.nextInt();
		int Q = sc.nextInt();

		final int mod = 998244353;

		//dp(1が高橋君、2が青木君)
		long[][] dp1 = new long[N+1][N+1];
		long[][] dp2 = new long[N+1][N+1];

		//今いる場所を初期設定(絶対いるので確率は1)
		dp1[0][A] = 1;
		dp2[0][B] = 1;

		//N回投げる(N回投げれば絶対マスNにはたどり着けるのでこれで良い)
		for(int i=0;i<N;i++){

			//遷移
			for(int j=1;j<N;j++){
				for(int k=1;k<=P;k++){
					if(j+k<=N){
						dp1[i+1][j+k] += dp1[i][j]*MathFunction.modPow(P,mod-2,mod);
						dp1[i+1][j+k] %=mod;
					}
					else{
						dp1[i+1][N] += dp1[i][j]*MathFunction.modPow(P,mod-2,mod);
						dp1[i+1][N] %=mod;
					}
				}
				for(int k=1;k<=Q;k++){
					if(j+k<=N){
						dp2[i+1][j+k] += dp2[i][j]*MathFunction.modPow(Q,mod-2,mod);
						dp2[i+1][j+k] %=mod;
					}
					else{
						dp2[i+1][N] += dp2[i][j]*MathFunction.modPow(Q,mod-2,mod);
						dp2[i+1][N] %=mod;
					}
				}
			}
		}

		//求めるべき確率を求める
		long sum = 0;
		for(int i=0;i<=N;i++){
			for(int j=i;j<=N;j++){
				sum += (long)dp1[i][N]*dp2[j][N]%mod;
				sum %= mod;
			}
		}

		//答えの出力
		out.println(sum);
 
		out.close();
	}
}
```
思っていたより早く思いつけました。

## 感想
A:易しい
B:ちょっと面倒。問題文通りに変換するメソッドを作れば良かったか…？
C:ちょっとだけ重い
D:気付けば早く解ける
E:[公式解説](https://atcoder.jp/contests/abc298/editorial/6216)のDPのやり方全然思いつかなかった
という感じでした。

Unratedになってしまいましたが、面白い問題だったなと思いました。