ABC350A～Fの解答[Java]

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

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

## A - Past ABCs
問題文は[こちら](https://atcoder.jp/contests/abc350/tasks/abc350_a)

$S$の末尾$3$文字の数字だけ見れば良いので、substringで切り出して数値に変換し、条件を満たすか判定しました。
```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){

		//Nの受け取り
		int N = Integer.parseInt(sc.next().substring(3));

  		//判定
		out.println(0<N&&N!=316&&N<350?"Yes":"No");

		out.close();
	}
}
```
`000`を省くのを忘れてて$1$ペナ…。

## B - Dentist Aoki
問題文は[こちら](https://atcoder.jp/contests/abc350/tasks/abc350_b)

今歯が生えているかどうかをBitSetを使って保持して解きました。
```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();

  		//歯の状態を保持するBitSet
		var bit = new java.util.BitSet(N+1);
		bit.set(1,N+1);

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

  		//クエリ処理
		while(Q-->0){

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

   			//反転
			bit.flip(T);
		}

  		//総和を求める
		out.println(bit.cardinality());

		out.close();
	}
}
```

## C - Sort
問題文は[こちら](https://atcoder.jp/contests/abc350/tasks/abc350_c)

先頭から条件を満たすように貪欲に操作を行なえば$N-1$回以下で構築可能なので、これを実装しました。
```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の受け取り
		int N = sc.nextInt();

  		//Aに対する位置、位置に対するAを記録するMap
		HashMap<Integer,Integer> mapA = new HashMap<>();
		HashMap<Integer,Integer> indexA = new HashMap<>();

  		//記録
		for(int i=1;i<=N;i++){
			int A = sc.nextInt();
			mapA.put(A,i);
			indexA.put(i,A);
		}

  		//貪欲に操作
		ArrayList<int[]> ans = new ArrayList<>();
		for(int i=1;i<=N;i++){
			if(mapA.get(i)!=i){
				int index = mapA.get(i);
				int val = indexA.get(i);
				mapA.put(val,index);
				indexA.put(index,val);
				mapA.put(i,i);
				indexA.put(i,i);
				ans.add(new int[]{i,index});
			}
		}

  		//答えの出力
		out.println(ans.size());
		for(int[] answer:ans)
			out.println(answer);

		out.close();
	}
}
```

## D - New Friends
問題文は[こちら](https://atcoder.jp/contests/abc350/tasks/abc350_d)

操作は同一の連結成分内でしか行えず、頂点数$V$に対して辺は$\frac{1}{2}V(V-1)$本張れることに着目すれば、UnionFindで各連結成分を管理し、その中の辺の本数から追加で張れる本数を求めながら答えを数え上げました。
```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、Mの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();

  		//UnionFindの構築
		UnionFind uf = new UnionFind(N+1);
		while(M-->0){
			int A = sc.nextInt();
			int B = sc.nextInt();
			uf.unite(A,B);
		}

  		//各連結成分のrootを求める
		HashSet<Integer> set = new HashSet<>();
		for(int i=1;i<=N;i++)
			set.add(uf.root(i));

   		//各連結成分ごとに張れる辺の本数を求めて数え上げ
		long ans = 0;
		for(int r:set){
			long s = uf.size(r);
			long p = uf.pathCount(r);
			ans += s*(s-1)/2-p;
		}

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

		out.close();
	}
}
```

## E - Toward 0
問題文は[こちら](https://atcoder.jp/contests/abc350/tasks/abc350_e)

[公式解説](https://atcoder.jp/contests/abc350/editorial/9812)の通りです。
```E.java
import java.util.Scanner;
import java.util.HashMap;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

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

  		//メモ化再帰で求める
		System.out.println(dfs(N,A,X,Y));
	}
	private static final HashMap<Long,Double> map = new HashMap<>();
	private static double dfs(long N,int A,int X,int Y){

 		//Nが0なら終わり
		if(N==0){
			return 0L;
		}

  		//すでに答えがわかってるならそれを返す
		if(map.containsKey(N)){
			return map.get(N);
		}

  		//答えを求める
		double ans = Y;
		for(int i=2;i<7;i++){
			ans += dfs(N/i,A,X,Y)+Y;
		}
		ans /= 5.0;
		double sum = 0;
		long num = N;
		while(num>0){
			num /= A;
			sum += X;
		}

  		//記録
		map.put(N,Math.min(ans,sum));

  		//答えを返す
		return Math.min(ans,sum);
	}
}
```
う～ん…再帰で実装するという判断になれず…無念…。

## F - Transpose
問題文は[こちら](https://atcoder.jp/contests/abc350/tasks/abc350_f)

直前までの`(`の数と`)`の数の差が偶数か奇数かで文字列が反転するかは求められるので、再帰的に処理することで答えを構築しました。
文字列同士の連結は`ArrayDeque<Character>`で保持しておいて連結するときに文字数が少ない方を多い方に加えることで全体で$O(\log |S|)$回の処理で構築できます。
```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);

	private static final HashMap<Integer,Integer> map = new HashMap<>();

	public static void main(String[] args){

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

  		//各'('の位置を保持しながら、"()"で括られた区間を求める
		ArrayDeque<Integer> d = new ArrayDeque<>();
		for(int i=0;i<S.length();i++){
			if(S.charAt(i)=='(')
				d.add(i);
			if(S.charAt(i)==')')
				map.put(d.pollLast(),i);
		}

  		//答えを求める
		ArrayDeque<Character> deq = dfs(0,0,S);

  		//答えの出力
		StringBuilder ans = new StringBuilder();
		for(char c:deq)
			ans.append(c);
		out.println(ans);

		out.close();
	}

 	//再帰用メソッド
	private static ArrayDeque<Character> dfs(int now,int depth,String S){
		ArrayDeque<Character> deq = new ArrayDeque<>();

  		//"()"の中を処理
		while(now<S.length()){

			//"()"の中に入るなら深さを1加算して再帰
			if(S.charAt(now)=='('){
				ArrayDeque<Character> sub = dfs(now+1,depth+1,S);
				now = map.get(now)+1; //終点にポインタを移動

    			//反転させるか否かで順番を入れ替える
				if(depth%2==0)
					deq = merge(deq,sub);
				else
					deq = merge(sub,deq);
			}

   			//"()"を抜けたら復帰させる
			else if(S.charAt(now)==')'){
				return deq;
			}

   			//文字は反転させるか否かで場合分けしながら記録
			else{
				if(depth%2==0)
					deq.addLast(S.charAt(now++));
				else{
					char c = S.charAt(now++);
					if(c<'a')
						deq.addFirst((char)(c+'a'-'A'));
					else
						deq.addFirst((char)(c-'a'+'A'));
				}
			}
		}

  		//答えを返す
		return deq;
	}

 	//マージテク用メソッド
	private static ArrayDeque<Character> merge(ArrayDeque<Character> d1, ArrayDeque<Character> d2){
		if(d1.size()>d2.size()){
			while(d2.size()>0)
				d1.addLast(d2.pollFirst());
			return d1;
		}
		else{
			while(d1.size()>0)
				d2.addFirst(d1.pollLast());
			return d2;
		}
	}
}
```
なんとか解けて良かった…。

## 感想
A:しょうもないミスを…
B,C,D:易しい
E:難しい…><
F:構文解析っぽくて面白かった
って感じでした。

う～ん…あまりにも精進不足が響いてる…。