ABC374A～Eの解答[Java]

はじめに

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

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

A - Takahashi san 2

問題文はこちら

endWithメソッドを使って解きました。

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){

		String S = sc.next();
		out.println(S.endsWith("san")?"Yes":"No");

		out.close();
	}
}

B - Unvarnished Report

問題文はこちら

先頭から愚直にfor文で探しました。

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){

		String S = sc.next();
		String T = sc.next();
		int N = Math.min(S.length(),T.length());
		for(int i=0;i<N;i++)
			if(S.charAt(i)!=T.charAt(i)){
				System.out.println(i+1);
				return;
			}
		out.println(S.length()!=T.length()?N+1:0);

		out.close();
	}
}

C - Separated Lunch

問題文はこちら

$A$に分類されるグループをbit全探索で探索することで解を求めました。

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[] K = sc.nextInt(N);
		int sum = (int)MathFunction.sum(K);
		int ans = sum;
		for(int i=0;i<1<<N;i++){
			int subSum = 0;
			for(int j=0;j<N;j++)
				if((i&(1<<j))>0)
					subSum += K[j];
			ans = Math.min(ans,Math.max(subSum,sum-subSum));
		}
		out.println(ans);

		out.close();
	}
}

D - Laser Marking

問題文はこちら

$N$が十分小さいので、順列全探索でどの順番に印字するか、bit全探索でどっちの端点から始めるかを探索することで解を求めました。

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 S = sc.nextInt();
		int T = sc.nextInt();
		Point[][] p = new Point[N][];
		double d = 0;
		for(int i=0;i<N;i++){
			p[i] = sc.nextPoint(2);
			d += Math.hypot(p[i][0].x-p[i][1].x,p[i][0].y-p[i][1].y)/T;
		}
		int[] map = new int[N];
		Arrays.setAll(map,i->i);
		double ans = Double.MAX_VALUE;
		do{
			for(int i=0;i<1<<N;i++){
				double sum = d;
				Point bef = new Point(0,0);
				for(int j=0;j<N;j++){
					sum += Math.hypot(p[map[j]][i>>j&1].x-bef.x,p[map[j]][i>>j&1].y-bef.y)/S;
					bef = p[map[j]][i>>j&1^1];
				}
				ans = Math.min(ans,sum);
			}
		}while(ArrayUtil.nextPermutation(map));
		out.println(ans);

		out.close();
	}
}

E - Sensor Optimization Dilemma 2

問題文はこちら

製造能力$W$を決めたとき、各工程が$W$以上になるような最小費用は高速に求めることができるため、費用が$X$以下になるように$W$の最大値を二分探索することで解を求めました。

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 X = sc.nextInt();
		int[] A = new int[N];
		int[] P = new int[N];
		int[] B = new int[N];
		int[] Q = new int[N];
		for(int i=0;i<N;i++){
			A[i] = sc.nextInt();
			P[i] = sc.nextInt();
			B[i] = sc.nextInt();
			Q[i] = sc.nextInt();
		}
		long ans = Searcher.downSearch(1L,Integer.MAX_VALUE,X,W->{
			long sum = 0;
			for(int i=0;i<N;i++){
				long min = Math.min((W+A[i]-1)/A[i]*P[i],(W+B[i]-1)/B[i]*Q[i]);
				for(long j=Math.max(0,(W-Math.max(A[i],B[i]))/A[i]-1000);j<(W+A[i]-1)/A[i];j++){
					long sub = W-A[i]*j;
					long c1 = (sub+A[i]-1)/A[i]*P[i];
					long c2 = (sub+B[i]-1)/B[i]*Q[i];
					min = Math.min(min,j*P[i]+Math.min(c1,c2));
				}
				for(long j=Math.max(0,(W-Math.max(A[i],B[i]))/B[i]-1000);j<(W+B[i]-1)/B[i];j++){
					long sub = W-B[i]*j;
					long c1 = (sub+A[i]-1)/A[i]*P[i];
					long c2 = (sub+B[i]-1)/B[i]*Q[i];
					min = Math.min(min,j*Q[i]+Math.min(c1,c2));
				}
				sum += min;
			}
			return sum;
		});
		out.println(ans);

		out.close();
	}
}

感想

A,B,C:易しい
D:ちょっとめんどいけど発想自体は易しめ？
E:二分探索らしい問題
って感じでした。

速度で誤魔化せたって感じ。あんまりレート上がった実感が無いな…。