ABC326A～Fの解答[Java]

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

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

## A - 2UP3DOWN
問題文は[こちら](https://atcoder.jp/contests/abc326/tasks/abc326_a)

問題文で指定されている範囲か判定して解きました。
```A.java
final class Main {

	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );

	public static void main ( String[] args ) {

		//X、Yの受け取り
		int X = sc.nextInt();
		int Y = sc.nextInt();

  		//階段で行ける範囲か調べる
		out.println(X-3<=Y&&Y<=X+2?"Yes":"No");

		out.close();
	}
}
```

## B - 326-like Numbers
問題文は[こちら](https://atcoder.jp/contests/abc326/tasks/abc326_b)

愚直に求めても十分間に合うので順に調べて解きました。
```B.java
final class Main {

	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );

	public static void main ( String[] args ) {

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

  		//愚直に調べる
		for(int i=N;;i++){

  			//問題文の通りの条件を満たしているなら出力して終了
			int a = i/100;
			int b = i/10%10;
			if(a*b==i%10){
				out.println(i);
				break;
			}
		}

		out.close();
	}
}
```
最初$N$以下の326-like numberを数える問題だと思ってしまって時間をかけてしまいました…。
ちゃんと読もう…。

## C - Peak
問題文は[こちら](https://atcoder.jp/contests/abc326/tasks/abc326_c)

$x=A_i$とするのが最適なので、$A$をソートすれば尺取り法を用いて最大個数を求めることができると思い、それを実装しました。
```C.java
final class Main {

	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );

	public static void main ( String[] args ) {

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

  		//ソート
		Arrays.sort(A);

  		//尺取りで最大区間を求める
		int ans = 0;
		int index = 0;
		for(int i=0;i<N;i++){
			while(index<N&&A[index]-A[i]<M)
				index++;
			ans = Math.max(ans,index-i);
		}

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

		out.close();
	}
}
```

## D - ABC Puzzle
問題文は[こちら](https://atcoder.jp/contests/abc326/tasks/abc326_d)

各行の左端は$R$と一致させないといけないので、$i$行目のどの位置を$R$の$i$文字目と一致させるかを全探索し、それより右側は順列全探索し、$C$に対する条件も満たしている並び方があるか探索しました。
最大ケースの$N=5$について考えると、$1$文字目を$R$と一致させると$\frac{4!}{2!}=12$通り(`BC..`の並べ替え)、$2$文字目を$R$と一致させると$3!=6$通り、$3$文字目を$R$と一致させると$2!=2$通りで、各行における探索回数は計$20$通りなので、$20^5=3.2 \times 10^6$通り探索し、それぞれの盤面で$O(N^2)$で判定しているのでなんとか間に合います。
```D.java
final class Main {

	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );

	//再帰軽量化の為にクラス変数に
	private static char[][] ans;
	private static char[] R,C;
	private static int N;

	public static void main ( String[] args ) {

		//N、R、Cの受け取り
		N = sc.nextInt();
		R = sc.nextCharArray();
		C = sc.nextCharArray();
		ans = new char[N][N];

  		//再帰全探索
		dfs(0);

  		//再帰を抜けたら解無しなのでNo
		out.println("No");

		out.close();
	}

 	//再帰用メソッド(今見ている行が引数)
	private static final void dfs(int now){

  		//全部見終わった？
		if(now==N){

  			//条件満たしてる？
			if(check(ans)){

   				//出力して終了
				out.println("Yes");
				out.println(ans);
				out.close();
				System.exit(0);
			}
		}
		else{

  			//Rと一致させる位置を全探索
			for(int i=0;i<N-2;i++){

   				//記録して自分より右側の文字を別変数に記録
				ans[now][i] = R[now];
				char[] sub = new char[N-i-1];
				sub[0] = (char)((R[now]+1-'A')%3+'A');
				sub[1] = (char)((R[now]+2-'A')%3+'A');
				for(int j=2;j<sub.length;j++)
					sub[j] = '.';

     			//順列全探索
				Arrays.sort(sub);
				do{
					for(int j=0;j<sub.length;j++)
						ans[now][i+j+1] = sub[j];
					dfs(now+1);
				}while(ArrayFunction.nextPermutation(sub));

    			//とりあえず全部.で上書きしておく
				for(int j=i;j<N;j++)
					ans[now][i] = '.';
			}
		}
	}

 	//判定メソッド
	private static final boolean check(){

		//列単位でABCがちゃんと出現してるか判定する用の配列 
		boolean[][] checkedC = new boolean[N][3];

  		//各列を見ていく
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if('A'<=ans[i][j]){

    				//既に出現済みの文字なら条件を満たさないのでfalse
					if(checkedC[j][ans[i][j]-'A'])
						return false;

      				//記録
					checkedC[j][ans[i][j]-'A'] = true;
				}
			}
		}

  		//条件を満たしているかチェック
		for(int i=0;i<N;i++){

			//全列で全文字が出現しているか確認
			for(int j=0;j<3;j++)
				if(!checkedC[i][j])
					return false;

			//一番上の文字がCを形成しているか調べる
			for(int j=0;;j++){
				if(ans[j][i]>='A'){
					if(ans[j][i]!=C[i])
						return false;
					break;
				}
			}
		}
		return true;
	}
}
```
バグりまくってかなり時間をかけてしまいました…。悲しい…。

## Revenge of "The Salary of AtCoder Inc."
問題文は[こちら](https://atcoder.jp/contests/abc326/tasks/abc326_e)

$x \lt y$の時のみ支給されるので、今$x$であるとすると$x+1$以降になったときの期待値だけ考えれば良く、各状態へは確率$\frac{1}{N}$で遷移できるので、動的計画法を用いれば$dp[x] = \frac{1}{N} \sum^{N}_{i=x+1}{dp[i]}$と遷移すれば良さそうと考えてこれを実装しました。
```E.java
final class Main {

	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );

	//mod
	private static final int MOD = 998244353;

	public static void main ( String[] args ) {

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

		//DPテーブル
		long[] dp = new long[N+1];
		dp[N] = A[N-1];

  		//累積和用変数
		long sum = A[N-1];

  		//1/N mod 99844353を求めておく
		long odd = MathFunction.modPow(N,MOD-2,MOD);

  		//遷移
		for(int i=N-1;i>0;i--){
			dp[i] = (A[i-1]+sum*odd)%MOD;
			sum += dp[i];
			if(sum>=MOD)
				sum -= MOD;
		}

  		//答えの出力
		out.println(sum*odd%MOD);

		out.close();
	}
}
```
総和が`sum`に代入されているので、各状態への遷移確率である$\frac{1}{N}$をかけてあげれば答えとなります。
これは結構早く気付きました。

## F - Robot Rotation
問題文は[こちら](https://atcoder.jp/contests/abc326/tasks/abc326_f)

※実装が汚いです()

[公式解説](https://atcoder.jp/contests/abc326/editorial/7476)の通りのはずです。
最初MapのvalueをStringにしていたんですがなんか重めだったのでLongで管理することにしたら通りました。
```F.java
final class Main {

	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner( System.in );
	private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );

	public static void main ( String[] args ) {

		//N、X、Y、Aの受け取り
		int N = sc.nextInt();
		long X = sc.nextLong();
		long Y = sc.nextLong();
		long[] A = sc.nextLong(N);


		//半分全探索パート(i mod 4毎に探索している
		HashMap<Long,Long> mapY1 = new HashMap<>();
		mapY1.put(0L,0L);
		for(int i=0;i<N;i+=4){
			HashMap<Long,Long> nextY = new HashMap<>(mapY1.size()<<1);
			for(Entry<Long,Long> subY:mapY1.entrySet()){
				long key = subY.getKey();
				long val = subY.getValue();
				nextY.putIfAbsent(key+A[i],(val<<2)|1);
				nextY.putIfAbsent(key-A[i],val<<2);
			}
			mapY1 = nextY;
		}
  
		HashMap<Long,Long> mapX1 = new HashMap<>();
		mapX1.put(0L,0L);
		for(int i=1;i<N;i+=4){
			HashMap<Long,Long> nextX = new HashMap<>(mapX1.size()<<1);
			for(Entry<Long,Long> subX:mapX1.entrySet()){
				long key = subX.getKey();
				long val = subX.getValue();
				nextX.putIfAbsent(key+A[i],(val<<2)|1);
				nextX.putIfAbsent(key-A[i],val<<2);
			}
			mapX1 = nextX;
		}
  
		HashMap<Long,Long> mapY2 = new HashMap<>();
		mapY2.put(0L,0L);
		for(int i=2;i<N;i+=4){
			HashMap<Long,Long> nextY = new HashMap<>(mapY2.size()<<1);
			for(Entry<Long,Long> subY:mapY2.entrySet()){
				long key = subY.getKey();
				long val = subY.getValue();
				nextY.putIfAbsent(key+A[i],(val<<2)|1);
				nextY.putIfAbsent(key-A[i],val<<2);
			}
			mapY2 = nextY;
		}
  
		HashMap<Long,Long> mapX2 = new HashMap<>();
		mapX2.put(0L,0L);
		for(int i=3;i<N;i+=4){
			HashMap<Long,Long> nextX = new HashMap<>(mapX2.size()<<1);
			for(Entry<Long,Long> subX:mapX2.entrySet()){
				long key = subX.getKey();
				long val = subX.getValue();
				nextX.putIfAbsent(key+A[i],(val<<2)|1);
				nextX.putIfAbsent(key-A[i],val<<2);
			}
			mapX2 = nextX;
		}


		//x座標側の答えが存在するか調べる
		String SX = null;
		for(long num:mapX1.keySet()){
			if(mapX2.containsKey(X-num)){

   				//二進数を文字列に変換
				StringBuilder sb = new StringBuilder();
				long subX = (N>>1)%2==0?
					(mapX1.get(num)<<1)|mapX2.get(X-num):
					mapX1.get(num)|(mapX2.get(X-num)<<1);
				for(int i=1;i<N;i+=2){
					sb.append((subX&1)>0?'U':'D');
					subX >>>= 1;
				}
				SX = sb.reverse().toString();
				break;
			}
		}

  		//見つからなかったらNo
		if(SX==null){
			System.out.println("No");
			return;
		}

  		//y座標側の答えが存在するか調べる
		String SY = null;
		for(long num:mapY1.keySet()){
			if(mapY2.containsKey(Y-num)){

   				//二進数を文字列に変換
				StringBuilder sb = new StringBuilder();
				long subY = (N+1>>1)%2==0?
					(mapY1.get(num)<<1)|mapY2.get(Y-num):
					mapY1.get(num)|(mapY2.get(Y-num)<<1);
				for(int i=0;i<N;i+=2){
					sb.append((subY&1)>0?'U':'D');
					subY >>>= 1;
				}
				SY = sb.reverse().toString();
				break;
			}
		}

  		//見つからなかったらNo
		if(SY==null){
			System.out.println("No");
			return;
		}

		//復元パート
		StringBuilder ans = new StringBuilder();
		char bef = 'U';
		for(int i=0;i<N;i++){
			if(i%2==1){
				ans.append(SX.charAt(i>>1)!=bef?'L':'R');
				bef = SX.charAt(i>>1);
			}
			else{
				ans.append(SY.charAt(i>>1)==bef?'L':'R');
				bef = SY.charAt(i>>1);
			}
		}

  		//答えの出力
		out.println("Yes");
		out.println(ans.toString());

		out.close();
	}
}
```
全然気付けなかった…。仮に気付いたとして正しい解法と思えたかは謎ですが…。

## 感想
A,B:易しい
C:尺取り久々に書いた気がする
D:めちゃくちゃ難しかった
E:気付けばそんなに難しくない
F:何も思いつけなかった…
って感じでした。

青には留まれているけど、やっぱり維持キツいですね…次回取り返さなきゃ。