ABC336A～Fの解答[Java]

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

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

## A - Long Loong
問題文は[こちら](https://atcoder.jp/contests/abc336/tasks/abc336_a)

`o`はrepeatメソッドで繰り返せるので、それを使って解きました。
```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の受け取り
		int X = sc.nextInt();

  		//答えを構築して出力
		out.println("L"+"o".repeat(X)+"ng");

		out.close();
	}
}
```

## B - CTZ
問題文は[こちら](https://atcoder.jp/contests/abc336/tasks/abc336_b)

Javaには`Integer::numberOfTrailingZeros`でそのまま答えが求められるのでこれを使いました。
```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();

  		//答えの出力
		out.println(Integer.numberOfTrailingZeros(N));

		out.close();
	}
}
```

## C - Even Digits
問題文は[こちら](https://atcoder.jp/contests/abc336/tasks/abc336_c)

答えは5進数表記表記した数字を10進数として2倍した値と一致するので、一度5進数の文字列に変換した後に10進数として数値に変換して2倍して解きました。
```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の受け取り(0-indexedにするため-1)
		long N = sc.nextLong()-1;

  		//5進数変換して10進数と解釈
		long value = Long.parseLong(Long.toString(N,5));

  		//2倍して出力
		System.out.println(value<<1);

		out.close();
	}
}
```

## D - Pyramid
問題文は[こちら](https://atcoder.jp/contests/abc336/tasks/abc336_d)

ちょっとごちゃごちゃ書いてしまいましたが、片側から見たときに山半分を作れる最大値を記録していき、それを元に尺取で解きました。
山の幅が奇数でなんかやりにくかったので、偶数番目と奇数番目で分けて解きました。
```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);

	public static void main(String[] args){

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

  		//後ろから見て構築できる最大の山半分を求める
		int[] backFollow = new int[N];
		int l = N-1;
		for(int r=N-1;r>=0;r--){
			while(0<=l&&r-l<A[l])
				l--;
			backFollow[r] = r-l;
		}

  		//前からも
		int[] frontFollow = new int[N];
		int r = 0;
		for(l=0;l<N;l++){
			while(r<N&&r-l<A[r])
				r++;
			frontFollow[l] = r-l;
		}

  		//偶奇で分けて答えを求める
		int ans = 1;
		r = 0;
		for(l=0;l<N;l+=2){
			while(r<N&&(r-l)/2<backFollow[r]&&(r-l)/2<=frontFollow[l])
				r += 2;
			ans = Math.max(ans,(r-l+1)/2);
		}
		r = 1;
		for(l=1;l<N;l+=2){
			while(r<N&&(r-l)/2<backFollow[r]&&(r-l)/2<=frontFollow[l])
				r += 2;
			ans = Math.max(ans,(r-l+1)/2);
		}
  
		out.println(ans);

		out.close();
	}
}
```

## E - Digit Sum Divisible
問題文は[こちら](https://atcoder.jp/contests/abc336/tasks/abc336_e)

[公式解説](https://atcoder.jp/contests/abc336/editorial/9055)の通りです。
```E.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
	public static void main(String[] args){
		final Scanner sc = new Scanner(System.in);

  		//Nの受け取り
		final String N = sc.next();

  		//桁数を別変数に
		final int len = N.length();
		long ans = 0;

  		//高速化のために配列使い回し
		long[][] dp1 = new long[len*9+1][len*9];
		long[][] dp2 = new long[len*9+1][len*9];
		long[][] next1 = new long[len*9+1][len*9];
		long[][] next2 = new long[len*9+1][len*9];

  		//遷移
		for(int s=1;s<=len*9;s++){
			for(final long[] temp:dp1)
				Arrays.fill(temp,0);
			for(final long[] temp:dp2)
				Arrays.fill(temp,0);
			dp2[0][0] = 1;
			for(char c:N.toCharArray()){
				for(final long[] temp:next1)
					Arrays.fill(temp,0);
				for(final long[] temp:next2)
					Arrays.fill(temp,0);
				final int nextValue = c-'0';
				for(int j=0;j<=len*9;j++){
					for(int k=0;k<len*9;k++){
						final long val1 = dp1[j][k];
						final long val2 = dp2[j][k];
						if(val1>0){
							final int max1 = Math.min(len*9-j+1,10);
							for(int i=0;i<max1;i++)
								next1[i+j][(k*10+i)%s] += val1;
						}
						if(val2>0){
							final int max2 = Math.min(len*9-j+1,nextValue);
							for(int i=0;i<max2;i++)
								next1[i+j][(k*10+i)%s] += val2;
						}
					}
				}
				for(int i=0;i+c-'0'<=len*9;i++){
					for(int j=0;j<len*9;j++){
						next2[i+nextValue][(j*10+nextValue)%s] += dp2[i][j];
					}
				}
				long[][] temp = dp1;
				dp1 = next1;
				next1 = temp;
				temp = dp2;
				dp2 = next2;
				next2 = temp;
			}
			ans += dp1[s][0]+dp2[s][0];
		}

  		//数え上げた答えを出力
		System.out.println(ans);
	}
}
```
む～ん…桁DPなんだろうなくらいにしか思えず、それ以上の進展が無かった…。

## F - Rotation Puzzle
問題文は[こちら](https://atcoder.jp/contests/abc336/tasks/abc336_f)

ほとんど[公式解説](https://atcoder.jp/contests/abc336/editorial/9077)の通りですが、高速化がそこまで行なわれていませんので、実行時間が結構ギリギリです。
```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){

		//H、W、Sの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] S = sc.nextInt(H,W);

  		//状態を保持するクラス
		class Node{
			int[][] map;
			int hash;
			BigInteger bigHash;
			Node(int[][] m){
				map = m;
				hash = 0;
				bigHash = BigInteger.ZERO;
				for(int i=0;i<H;i++){
					for(int j=0;j<W;j++){
						hash = hash*(H*W+1)+map[i][j];
						bigHash = bigHash.shiftLeft(7).or(BigInteger.valueOf(map[i][j]));
					}
				}
			}
			@Override
			public int hashCode(){
				return hash;
			}
			@Override
			public boolean equals(Object o){
				if(o instanceof Node n){
					return bigHash.equals(n.bigHash);
				}
				return false;
			}
		}

  		//作りたい最終形を構築しておく
		int[][] origin = new int[H][W];
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)
				origin[i][j] = i*W+j+1;

    	//最終形から逆算
		HashMap<Node,Integer> map = new HashMap<>();
		map.put(new Node(origin),0);
		ArrayDeque<Node> deq = new ArrayDeque<>();
		deq.add(new Node(origin));
		for(int s=1;s<=10;s++){
			ArrayDeque<Node> next = new ArrayDeque<>();
			while(deq.size()>0){
				Node now = deq.pollFirst();
				int[][] next1 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next1[i][j] = now.map[H-i-2][W-j-2];
				for(int i=0;i<H;i++)
					next1[i][W-1] = now.map[i][W-1];
				for(int i=0;i<W;i++)
					next1[H-1][i] = now.map[H-1][i];
				if(map.putIfAbsent(new Node(next1),s)==null)
					next.add(new Node(next1));

				int[][] next2 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next2[i][j+1] = now.map[H-i-2][W-j-1];
				for(int i=0;i<H;i++)
					next2[i][0] = now.map[i][0];
				for(int i=0;i<W;i++)
					next2[H-1][i] = now.map[H-1][i];
				if(map.putIfAbsent(new Node(next2),s)==null)
					next.add(new Node(next2));

				int[][] next3 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next3[i+1][j] = now.map[H-i-1][W-j-2];
				for(int i=0;i<H;i++)
					next3[i][W-1] = now.map[i][W-1];
				for(int i=0;i<W;i++)
					next3[0][i] = now.map[0][i];
				if(map.putIfAbsent(new Node(next3),s)==null)
					next.add(new Node(next3));

				int[][] next4 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next4[i+1][j+1] = now.map[H-i-1][W-j-1];
				for(int i=0;i<H;i++)
					next4[i][0] = now.map[i][0];
				for(int i=0;i<W;i++)
					next4[0][i] = now.map[0][i];
				if(map.putIfAbsent(new Node(next4),s)==null)
					next.add(new Node(next4));
			}
			deq = next;
		}

  		//今の状態からも遷移
		deq = new ArrayDeque<>();
		HashMap<Node,Integer> map2 = new HashMap<>();
		map2.put(new Node(S),0);
		deq.add(new Node(S));
		for(int s=1;s<=10;s++){
			ArrayDeque<Node> next = new ArrayDeque<>();
			while(deq.size()>0){
				Node now = deq.pollFirst();
				int[][] next1 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next1[i][j] = now.map[H-i-2][W-j-2];
				for(int i=0;i<H;i++)
					next1[i][W-1] = now.map[i][W-1];
				for(int i=0;i<W;i++)
					next1[H-1][i] = now.map[H-1][i];
				if(map2.putIfAbsent(new Node(next1),s)==null)
					next.add(new Node(next1));

				int[][] next2 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next2[i][j+1] = now.map[H-i-2][W-j-1];
				for(int i=0;i<H;i++)
					next2[i][0] = now.map[i][0];
				for(int i=0;i<W;i++)
					next2[H-1][i] = now.map[H-1][i];
				if(map2.putIfAbsent(new Node(next2),s)==null)
					next.add(new Node(next2));

				int[][] next3 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next3[i+1][j] = now.map[H-i-1][W-j-2];
				for(int i=0;i<H;i++)
					next3[i][W-1] = now.map[i][W-1];
				for(int i=0;i<W;i++)
					next3[0][i] = now.map[0][i];
				if(map2.putIfAbsent(new Node(next3),s)==null)
					next.add(new Node(next3));

				int[][] next4 = new int[H][W];
				for(int i=0;i<H-1;i++)
					for(int j=0;j<W-1;j++)
						next4[i+1][j+1] = now.map[H-i-1][W-j-1];
				for(int i=0;i<H;i++)
					next4[i][0] = now.map[i][0];
				for(int i=0;i<W;i++)
					next4[0][i] = now.map[0][i];
				if(map2.putIfAbsent(new Node(next4),s)==null)
					next.add(new Node(next4));
			}
			deq = next;
		}

  		//半分全列挙が出来ているので答えをもとめｒ
		int min = 21;
		for(Entry<Node,Integer> entry:map.entrySet())
			min = Math.min(map2.getOrDefault(entry.getKey(),21)+entry.getValue(),min);
		out.println(min<21?min:-1);

		out.close();
	}
}
```
気づけないなぁ…。

## 感想
A,B,C:これらはライブラリでどうとでもなったので良かった
D:かなり手こずった…
E:遷移ミスって地獄
F:何も見えてこなかった…
って感じでした。

う～ん…ダメダメ過ぎる…。