ABC364A～Eの解答[Java]

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

なお、僕のライブラリは[GitHub](https://github.com/viral8code/viral-Library)よりご確認ください。
では、見ていきましょう。

## A - Glutton Takahashi
問題文は[こちら](https://atcoder.jp/contests/abc364/tasks/abc364_a)

2個連続で甘いものを食べたときに最後じゃなければ`No`、それ以外は`Yes`と判定することで本問題を解きました。
```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 = sc.nextInt();

  		//順に判定
		boolean flag = false;
		while(N-->0){
			String S = sc.next();
			if(S.charAt(1)=='w'&&flag&&N>0){
				System.out.println("No");
				return;
			}
			flag = S.charAt(1)=='w';
		}
		out.println("Yes");

		out.close();
	}
}
```

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

		//H、W、Si、Sj、C、Xの受け取り
		int H = sc.nextInt();
		int W = sc.nextInt();
		int Si = sc.nextInt()-1;
		int Sj = sc.nextInt()-1;
		char[][] C = sc.nextCharArray(H);
		char[] X = sc.nextCharArray();

  		//シミュレーション
		for(char c:X){
			switch(c){
				case 'U' ->{
					if(Si>0&&C[Si-1][Sj]!='#')
						Si--;
				}
				case 'D' ->{
					if(Si+1<H&&C[Si+1][Sj]!='#')
						Si++;
				}
				case 'L' ->{
					if(Sj>0&&C[Si][Sj-1]!='#')
						Sj--;
				}
				case 'R' ->{
					if(Sj+1<W&&C[Si][Sj+1]!='#')
						Sj++;
				}
			}
		}

  		//答えの出力
		out.println((Si+1)+" "+(Sj+1));

		out.close();
	}
}
```

## C - Minimum Glutton
問題文は[こちら](https://atcoder.jp/contests/abc364/tasks/abc364_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){

		//N、X、Y、料理の受け取り
		int N = sc.nextInt();
		long X = sc.nextLong();
		long Y = sc.nextLong();
		int[][] dishes = new int[N][2];
		for(int i=0;i<N;i++)
			dishes[i][0] = sc.nextInt();
		for(int i=0;i<N;i++)
			dishes[i][1] = sc.nextInt();

   		//甘さでソートして貪欲に選ぶ
		Arrays.sort(dishes,(a,b)->-Integer.compare(a[0],b[0]));
		long sum = 0;
		int index = 0;
		while(index<N&&sum<=X)
			sum += dishes[index++][0];
		int ans = index;

  		//しょっぱさでソートして貪欲に選ぶ
		Arrays.sort(dishes,(a,b)->-Integer.compare(a[1],b[1]));
		sum = 0;
		index = 0;
		while(index<N&&sum<=Y)
			sum += dishes[index++][1];

   		//答えの出力
		out.println(Math.min(ans,index));

		out.close();
	}
}
```

## D - K-th Nearest
問題文は[こちら](https://atcoder.jp/contests/abc364/tasks/abc364_d)

予め$A$をソートしておくことで、$B_i$との距離が$d$以内の点の個数を高速に求めることができるので、距離が$d$以内の点の個数が$k$個となる最小の$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、Q、aの受け取り
		int N = sc.nextInt();
		int Q = sc.nextInt();
		int[] a = sc.nextInt(N);

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

  		//クエリに答える
		while(Q-->0){

  			//b、kの受け取り
			int b = sc.nextInt();
			int k = sc.nextInt();

   			//二分探索で答えを求める
			int l = 0;
			int r = 1_000_000_000;
			int ans = r;
			while(l-r<1){
				int mid = (l+r)/2;
				int indexL = Searcher.upSearch(a,b-mid);
				int indexR = Searcher.downSearch(a,b+mid);
				if(indexR-indexL+1<k)
					l = mid+1;
				else
					r = (ans=mid)-1;
			}
			out.println(ans);
		}

		out.close();
	}
}
```

## E - Maximum Glutton
問題文は[こちら](https://atcoder.jp/contests/abc364/tasks/abc364_e)

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

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

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

  		//DPテーブルの構築
		int[][] dp = new int[N+1][X+1];
		final int max = Integer.MAX_VALUE>>1;
		for(int[] temp:dp)
			Arrays.fill(temp,max);
		dp[0][0] = 0;

  		//遷移
		for(int i=0;i<N;i++){
			for(int j=N;j>0;j--){
				for(int k=A[i];k<=X;k++){
					dp[j][k] = Math.min(dp[j][k],dp[j-1][k-A[i]]+B[i]);
				}
			}
		}

  		//答えを求める
		for(int i=N;;i--){
			int min = max;
			for(int num:dp[i])
				min = Math.min(min,num);
			if(min<=Y){
				System.out.println(Math.min(i+1,N));
				return;
			}
		}
	}
}
```
全然思いつかなかった…。

## 感想
A:ちょっと手間取った
B,C:易しい
D:二分探索らしい見た目
E:DPなのしかわからなかった…
って感じでした。

前回からの落差が大き過ぎる…。