はじめに
今回はコンテスト中に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なのしかわからなかった…
って感じでした。
前回からの落差が大き過ぎる…。