ABC364A～Eの解答[Java]

はじめに

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

なお、僕のライブラリはGitHubよりご確認ください。
では、見ていきましょう。

A - Glutton Takahashi

問題文はこちら

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

問題文はこちら

制約上そこまで行動回数が多くないので、愚直にシミュレーションすることで解きました。

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

問題文はこちら

甘さとしょっぱさそれぞれ大きい順に並べて貪欲に食べることでどちらかが最適解になります。

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

問題文はこちら

予め$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

問題文はこちら

公式解説の通りです。

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なのしかわからなかった…
って感じでした。

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