ABC371A～Fの解答[Java]

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

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

## A - Jiro
問題文は[こちら](https://atcoder.jp/contests/abc371/tasks/abc371_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){

		int AB = sc.nextChar()=='<'?-1:1;
		int AC = sc.nextChar()=='<'?-1:1;
		int BC = sc.nextChar()=='<'?-1:1;
		if(AB==1){
			if(BC==1){
				out.println("B");
			}
			else if(AC==1){
				out.println("C");
			}
			else{
				out.println("A");
			}
		}
		else if(AC==1){
			out.println("A");
		}
		else if(BC==1){
			out.println("C");
		}
		else{
			out.println("B");
		}

		out.close();
	}
}
```

## B - Taro
問題文は[こちら](https://atcoder.jp/contests/abc371/tasks/abc371_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){

		int N = sc.nextInt();
		int M = sc.nextInt();
		boolean[] flag = new boolean[N+1];
		while(M-->0){
			int A = sc.nextInt();
			char B = sc.nextChar();
			if(B=='M'){
				if(flag[A]){
					out.println("No");
				}
				else{
					flag[A] = true;
					out.println("Yes");
				}
			}
			else{
				out.println("No");
			}
		}

		out.close();
	}
}
```

## C - Make Isomorphic
問題文は[こちら](https://atcoder.jp/contests/abc371/tasks/abc371_c)

順列全探索で頂点の対応を全探索しながら解を求めました。
```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){

		int N = sc.nextInt();
		int MG = sc.nextInt();
		boolean[][] pathG = new boolean[N+1][N+1];
		while(MG-->0){
			int u = sc.nextInt();
			int v = sc.nextInt();
			pathG[u][v] = true;
			pathG[v][u] = true;
		}
		int MH = sc.nextInt();
		boolean[][] pathH = new boolean[N+1][N+1];
		while(MH-->0){
			int a = sc.nextInt();
			int b = sc.nextInt();
			pathH[a][b] = true;
			pathH[b][a] = true;
		}
		int[][] A = new int[N+1][N+1];
		for(int i=1;i<=N;i++){
			for(int j=i+1;j<=N;j++){
				A[i][j] = A[j][i] = sc.nextInt();
			}
		}
		int min = Integer.MAX_VALUE;
		int[] map = new int[N+1];
		Arrays.setAll(map,i->i);
		while(map[0]==0){
			int ans = 0;
			for(int i=1;i<=N;i++){
				for(int j=i+1;j<=N;j++){
					if(pathG[i][j]!=pathH[map[i]][map[j]]){
						ans += A[map[i]][map[j]];
					}
				}
			}
			min = Math.min(min,ans);
			ArrayUtil.nextPermutation(map);
		}
		out.println(min);

		out.close();
	}
}
```

## D - 1D Country
問題文は[こちら](https://atcoder.jp/contests/abc371/tasks/abc371_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){

		int N = sc.nextInt();
		int[] X = sc.nextInt(N);
		int[] P = sc.nextInt(N);
		long[] sumP = new long[N+1];
		for(int i=0;i<N;i++)
			sumP[i+1] = sumP[i]+P[i];
		int Q = sc.nextInt();
		while(Q-->0){
			int L = sc.nextInt();
			int R = sc.nextInt();
			int indexL = Searcher.upSearch(X,L);
			int indexR = Searcher.downSearch(X,R);
			out.println(indexL<=indexR?sumP[indexR+1]-sumP[indexL]:0);
		}

		out.close();
	}
}
```

## E - I Hate Sigma Problems
問題文は[こちら](https://atcoder.jp/contests/abc371/tasks/abc371_e)

$i=1$のときをHashMapを使って求めておき、あとから$i$を$2,3,\dots$とずらしていくことで差分を求めながら数え上げました。
```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){

		int N = sc.nextInt();
		int[] A = sc.nextInt(N);
		TreeMap<Integer,ArrayDeque<Integer>> map = new TreeMap<>();
		for(int i=0;i<N;i++){
			if(!map.containsKey(A[i]))
				map.put(A[i],new ArrayDeque<>());
			map.get(A[i]).add(i);
		}
		HashSet<Integer> set = new HashSet<>();
		long ans = 0;
		for(int num:A){
			set.add(num);
			ans += set.size();
		}
		long sum = ans;
		for(int i=0;i<N;i++){
			ArrayDeque<Integer> deq = map.get(A[i]);
			deq.pollFirst();
			int index = deq.size()>0?deq.peekFirst():N;
			sum -= index-i;
			ans += sum;
		}
		out.println(ans);

		out.close();
	}
}
```

## F - Takahashi in Narrow Road
問題文は[こちら](https://atcoder.jp/contests/abc371/tasks/abc371_f)

座標が$1$だけズレている高橋君をひとまとめにし、左端の座標と連続する人数をTreeMapで保持することで必要な移動回数を高速に求めました。
```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){

		int N = sc.nextInt();
		TreeMap<Integer,Integer> map = new TreeMap<>();
		for(int x:sc.nextInt(N)){
			Integer f = map.floorKey(x);
			if(f==null){
				map.put(x,x);
			}
			else{
				int right = map.get(f);
				if(right+1<x)
					map.put(x,x);
				else
					map.put(f,x);
			}
		}
		TreeMap<Integer,Integer> mapIndex = new TreeMap<>();
		int count = 1;
		for(Entry<Integer,Integer> entry:map.entrySet()){
			mapIndex.put(count,entry.getKey());
			count += entry.getValue()-entry.getKey()+1;
		}
		int Q = sc.nextInt();
		long ans = 0;
		while(Q-->0){
			int T = sc.nextInt();
			int G = sc.nextInt();
			int key = mapIndex.floorKey(T);
			int left = mapIndex.get(key);
			int right = map.get(left);
			int X = (T-key)+left;
			if(X<G){
				if(left<X)
					map.put(left,X-1);
				else
					map.remove(left);
				long sum = right-X+1;
				ans += (G-X)*sum;
				right = (int)(G+sum-1);
				mapIndex.put(T,G);
				while(map.floorKey(right)!=null&&X<map.floorKey(right)){
					int subKey = map.floorKey(right);
					int subRight = map.get(subKey);
					ans += (long)(subRight-subKey+1)*(right+1-subKey);
					right += subRight-subKey+1;
					map.remove(subKey);
					Integer ind = mapIndex.higherKey(T);
					mapIndex.remove(ind);
				}
				map.put(G,right);
			}
			else if(G<X){
				if(X<right){
					map.put(X+1,right);
					mapIndex.put(T+1,X+1);
				}
				map.remove(left);
				mapIndex.remove(key);
				long sum = X-left+1;
				ans += (X-G)*sum;
				left = (int)(G-sum+1);
				Integer ind = key;
				while(map.floorKey(X)!=null&&left<=map.get(map.floorKey(X))){
					int subKey = map.floorKey(X);
					int subRight = map.get(subKey);
					ans += (long)(subRight-subKey+1)*(subRight-left+1);
					left -= subRight-subKey+1;
					map.remove(subKey);
					ind = mapIndex.lowerKey(T);
					mapIndex.remove(ind);
				}
				map.put(left,G);
				mapIndex.put(ind,left);
			}
		}
		out.println(ans);

		out.close();
	}
}
```

## 感想
A,B:簡単
C:気づけばサクッと
D:Dにしては易しめ？
E:ちょっと実装がめんどう
F:ギリギリ実装間に合ってよかった…
って感じでした。

毎度こんな感じのパフォを取りたいねぇ。