ABC352A～Fの解答[Java]

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

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

## A - AtCoder Line
問題文は[こちら](https://atcoder.jp/contests/abc352/tasks/abc352_a)

条件を数式に落とし込むと$\min(X,Y)<Z<\max(X,Y)$と表せるので、これを判定しました。
```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,X,Y,Zの受け取り
		int N = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int Z = sc.nextInt();

  		//条件の判定
		out.println(MathFunction.rangeCheckClose(Z,Math.min(X,Y),Math.max(X,Y))?"Yes":"No");

		out.close();
	}
}
```

## B - Typing
問題文は[こちら](https://atcoder.jp/contests/abc352/tasks/abc352_b)

$S$の各文字について、$T$の何番目に表れるかを調べることで解を構築しました。
```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){

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

  		//各文字がTの何文字目に出てくるか調べる
		int[] ans = new int[S.length()];
		int index = 0;
		for(int i=0;i<S.length();i++){
			index = T.indexOf(S.charAt(i),index);
			ans[i] = ++index;
		}

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

		out.close();
	}
}
```

## C - Standing On The Shoulders
問題文は[こちら](https://atcoder.jp/contests/abc352/tasks/abc352_c)

一番上に来る巨人の頭の大きさ($B_i-A_i$)を$C$とすると、全体の高さは$\sum{A_i}+C$なので、$B_i-A_i$を最大の最大値を求めてあげれば答えが求まります。
```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();

  		//B-Aの最大値を求めつつ、Aの総和を求める
		int max = 0;
		long sum = 0;
		while(N-->0){
			int A = sc.nextInt();
			int B = sc.nextInt();
			max = Math.max(max,B-A);
			sum += A;
		}

  		//答えの出力
		out.println(sum+max);

		out.close();
	}
}
```

## D - Permutation Subsequence
問題文は[こちら](https://atcoder.jp/contests/abc352/tasks/abc352_d)

$A'_{A_i}=i$なる$A'$を構築し、先頭から$K$個ずつTreeSetに追加することで、答えをset.last()-set.first()で求められるようになり、これは十分高速に動作します。
```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、Kの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();

  		//上記のA'の構築
		int[] invP = new int[N+1];
		for(int i=1;i<=N;i++)
			invP[sc.nextInt()] = i;

   		//順にK個ずつ入れて最小値を求める
		int index = 1;
		TreeSet<Integer> set = new TreeSet<>();
		int ans = Integer.MAX_VALUE;
		while(index<=N){

  			//最初のK個入れる部分もまとめて処理したかったのでwhileで
			while(index<=N&&set.size()<K){
				set.add(invP[index++]);
			}
			if(set.size()==K)
				ans = Math.min(ans,set.last()-set.first());
			set.remove(invP[index-K]);
		}

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

		out.close();
	}
}
```
最初$\lbrace P_{i_1}, P_{i_2}, \dots, P_{P_K} \rbrace$の意味を集合ではなく数列だと勘違いして「本問題の制約下では良い添字列が必ず$1$つ以上存在することが示せます。」が本当か…？になってしまい、時間を食いました…。注意力さん…。

## E - Clique Connect
問題文は[こちら](https://atcoder.jp/contests/abc352/tasks/abc352_e)

各操作は「$i=2,3,\dots,K_1$に対して、$A_{i-1}$と$A_i$の間に辺を張る」と言い換えられるので、辺の総数は$O(\mathrm{sum}(K_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);

	public static void main(String[] args){

		//N、M、C、Aの受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] C = new int[M];
		int[][] A = new int[M][];
		for(int i=0;i<M;i++){
			int K = sc.nextInt();
			C[i] = sc.nextInt();
			A[i] = sc.nextInt(K);
		}

  		//クラスカル法
		PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->Integer.compare(C[a],C[b]));
		for(int i=0;i<M;i++)
			queue.add(i);
		UnionFind uf = new UnionFind(N+1);
		long ans = 0;
		while(queue.size()>0){
			int index = queue.poll();
			for(int i=1;i<A[index].length;i++)
				if(uf.unite(A[index][i-1],A[index][i]))
					ans += C[index];
		}

  		//答えの出力
		out.println(uf.size(1)==N?ans:-1);

		out.close();
	}
}
```

## F - Estimate Order
問題文は[こちら](https://atcoder.jp/contests/abc352/tasks/abc352_f)

[公式解説](https://atcoder.jp/contests/abc352/editorial/9924)と[cirno3153](https://atcoder.jp/users/cirno3153)さんの[ユーザー解説](https://atcoder.jp/contests/abc352/editorial/9928)の通りです。
```F.java
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;

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

  		//N、M、条件(重み付き有向辺)の受け取り
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList<ArrayList<int[]>> list = new ArrayList<>();
		for(int i=0;i<N;i++)
			list.add(new ArrayList<>());
		while(M-->0){
			int A = sc.nextInt()-1;
			int B = sc.nextInt()-1;
			int C = sc.nextInt();
			list.get(A).add(makeArray(B,-C));
			list.get(B).add(makeArray(A,C));
		}

  		//集合ごとにまとめる
		boolean[] checked = new boolean[N];
		ArrayList<ArrayList<Integer>> subList = new ArrayList<>();
		ArrayList<ArrayList<Integer>> valList = new ArrayList<>();
		ArrayList<Integer> bit = new ArrayList<>();
		for(int i=0;i<N;i++){
			if(checked[i])
				continue;
			checked[i] = true;
			ArrayList<Integer> sub = new ArrayList<>();
			ArrayList<Integer> val = new ArrayList<>();
			sub.add(i);
			val.add(0);
			for(int j=0;j<sub.size();j++){
				int now = sub.get(j);
				int num = val.get(j);
				for(int[] path:list.get(now)){
					if(!checked[path[0]]){
						sub.add(path[0]);
						val.add(num+path[1]);
						checked[path[0]] = true;
					}
				}
			}
			int min = 0;
			for(int num:val)
				min = Math.min(min,num);
			int b = 0;
			for(int j=0;j<val.size();j++){
				int num = val.get(j)-min;
				b |= 1<<num;
				val.set(j,num);
			}
			subList.add(sub);
			valList.add(val);
			bit.add(b);
		}
		int count = 0;
		for(ArrayList<Integer> l:subList)
			count += Math.max(0,2-l.size());

   		//ユーザー解説より
		if(count>1)
			for(int i=subList.size()-1;i>=0;i--)
				if(subList.get(i).size()==1){
					subList.remove(i);
					valList.remove(i);
					bit.remove(i);
				}

		//再帰で解を求める
		ArrayList<ArrayList<Integer>> index = new ArrayList<>();
		for(int i=0;i<subList.size();i++)
			index.add(new ArrayList<>());
		dfs(0,0,bit,index,N);

  		//答えの構築&出力
		int[] ans = new int[N];
		Arrays.fill(ans,-1);
		for(int i=0;i<subList.size();i++)
			for(int j=0;j<subList.get(i).size();j++)
				if(index.get(i).size()==1)
					ans[subList.get(i).get(j)] = index.get(i).get(0)+valList.get(i).get(j)+1;
		String answer = Arrays.toString(ans);
		System.out.println(answer.substring(1,answer.length()-1).replace(",",""));
	}

 	//全探索用の再帰メソッド
	private static boolean dfs(int now,int sum,ArrayList<Integer> bit,ArrayList<ArrayList<Integer>> index,int N){
		if(now==bit.size())
			return true;
		boolean flag = false;
		for(int i=0;i<N;i++){
			int sub = bit.get(now)<<i;
			if(1<<N<=sub)
				break;
			if((sum&sub)>0)
				continue;
			if(dfs(now+1,sum|sub,bit,index,N)){
				if(!index.get(now).contains(i))
					index.get(now).add(i);
				flag = true;
			}
		}
		return flag;
	}
	private static int[] makeArray(int... nums){
		return nums;
	}
}
```

## 感想
A,B,C:易しい
D:問題文読むのに時間かかっちゃった…
E:気付けば簡単め
F:う～ん…解けなかった…
って感じでした。

Eまでの速度感はそこまで悪くない気はしますが、もっと速く解きたいですね…。