ABC365A～Eの解答[Java]

はじめに

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

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

A - Leap Year

問題文はこちら

問題文の通りに実装しました。

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

		//Yの受け取り
		int Y = sc.nextInt();

  		//問題文の通りに実装
		if(Y%4>0){
			out.println(365);
		}
		else if(Y%100>0){
			out.println(366);
		}
		else if(Y%400>0){
			out.println(365);
		}
		else{
			out.println(366);
		}

		out.close();
	}
}

B - Second Best

問題文はこちら

$1$番目に大きい値、$2$番目に大きい値を保持しておくことで順に見ていきながら処理することができます。

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

		//N、Aの受け取り
		int N = sc.nextInt();
		int[] A = sc.nextInt(N);

  		//最大値のインデックスを記録
		int max1 = 0;
		int max2 = 1;
		if(A[0]<A[1]){
			max1 = 1;
			max2 = 0;
		}

  		//更新
		for(int i=2;i<N;i++){
			if(A[max1]<A[i]){
				max2 = max1;
				max1 = i;
			}
			else if(A[max2]<A[i]){
				max2 = i;
			}
		}

  		//2番目に大きいインデックスを出力
		out.println(max2+1);

		out.close();
	}
}

C - Transportation Expenses

問題文はこちら

上限が決まれば総和が$M$以下かは高速に判定できるため、二分探索で最大の$x$を求めることができます。

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、M、Aの受け取り
		int N = sc.nextInt();
		long M = sc.nextLong();
		int[] A = sc.nextInt(N);

  		//二分探索
		long ans = Searcher.downSearch(0,Long.MAX_VALUE>>1,M,B->{
			long sum = 0;
			for(int num:A)
				sum += Math.min(B,num);
			return sum;
		});

  		//答えの出力
		out.println(ans==Long.MAX_VALUE>>1?"infinite":ans);

		out.close();
	}
}

D - AtCoder Janken 3

問題文はこちら

DPの要領で変数を更新していくことで解を求めました。

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、Sの受け取り
		int N = sc.nextInt();
		char[] S = sc.nextCharArray();

  		//DP
		int r = 0;
		int p = 0;
		int s = 0;
		for(char c:S){
			int nr,np,ns;
			if(c=='R'){
				ns = Integer.MIN_VALUE;
				np = Math.max(r,s)+1;
				nr = Math.max(p,s);
			}
			else if(c=='P'){
				nr = Integer.MIN_VALUE;
				ns = Math.max(r,p)+1;
				np = Math.max(r,s);
			}
			else{
				np = Integer.MIN_VALUE;
				nr = Math.max(p,s)+1;
				ns = Math.max(r,p);
			}
			r = nr;
			p = np;
			s = ns;
		}

  		//答えの出力
		out.println(MathFunction.max(r,p,s));

		out.close();
	}
}

E - Xor Sigma Problem

問題文はこちら

各bit毎に、$i$からのxor和が1になる区間の長さを求めてあげることで高速に解を求めることができます。

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

		//N、Aの受け取り
		int N = sc.nextInt();
		int[] A = sc.nextInt(N);

  		//bit毎に数え上げ
		long ans = 0;
		for(int i=0;i<28;i++){

  			//xor和が1になる区間の数え上げ
			int a = 0;
			boolean flag = false;
			for(int j=0;j<N;j++){
				if((A[j]&(1<<i))>0){
					flag = !flag;
				}
				if(flag)
					a++;
			}

   			//直前の始点が1ならxor和が0になる区間と1になる区間が反転するので、それを処理しながら数え上げ
			long sum = 0;
			for(int j=0;j<N;j++){
				if((A[j]&(1<<i))>0){
					--a;
				}
				sum += a;
				if((A[j]&(1<<i))>0){
					a = (N-j-1)-a;
				}
			}

   			//今のbitに合わせて補正して加算
			ans += sum*(1<<i);
		}

  		//答えの出力
		out.println(ans);

		out.close();
	}
}

全然サンプルと合わなくて凄い時間かけてしまいました…。

感想

A,B:易しい
C:二分探索らしい問題文だった
D:易しめなDP
E:細かい実装ミスが重なって凄い大変だった…
って感じでした。

う～ん…もっと速度を出したかった…。