ABC355A～Dの解答[Java]

はじめに

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

なお、僕のライブラリは提出結果をご確認ください。
では、見ていきましょう。

A - Who Ate the Cake?

問題文はこちら

$A$と$B$が異なるなら答えが定まりますが、$A=B$なら答えが求まりません。また、$1 \le A,B \le 3$より、答えは$A \ \mathrm{xor} \ B$で求まります。

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

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

  		//答えの構築(A==BならA^B==0)
		int ans = A^B;
		out.println(ans>0?ans:-1);

		out.close();
	}
}

B - Piano 2

問題文はこちら

$C$を$N+M$行$2$列の二次元配列として考え、$1$列目に$A$や$B$の値を、$2$列目に$A$の値なのか$B$の値なのかを保持してArrays::sortでソートすることで$A$の値が連続するかどうかを判定することができます。

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、M、A、Bの受け取り(AとBはCにまとめる)
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] C = new int[N+M][];
		for(int i=0;i<N;i++)
			C[i] = new int[]{sc.nextInt(),0};
		for(int i=N;i<N+M;i++)
			C[i] = new int[]{sc.nextInt(),1};

   		//Cの構築(ソート)
		Arrays.sort(C,Arrays::compare);

  		//隣接するAがあるか調べる
		boolean flag = false;
		for(int i=1;i<C.length;i++)
			flag |= C[i-1][1]+C[i][1]==0;

		//答えの出力
		out.println(flag?"Yes":"No");

		out.close();
	}
}

C - Bingo 2

問題文はこちら

各行、列、斜めで、あといくつ開けるとビンゴになるかを保持することで高速に処理できます。

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の受け取り
		int N = sc.nextInt();

  		//各行、列、ななめの状態を記録する用の配列
		int[] R = new int[N];
		int[] C = new int[N];
		int[] RC = new int[2];
		Arrays.fill(R,N);
		Arrays.fill(C,N);
		Arrays.fill(RC,N);

  		//Tの受け取り
		int T = sc.nextInt();
		for(int t=1;t<=T;t++){

  			//Aの受け取り
			int A = sc.nextInt()-1;

   			//状態を反映してビンゴができたか調べる
			int i = A/N;
			int j = A%N;
			if(--R[i]==0){
				System.out.println(t);
				return;
			}
			if(--C[j]==0){
				System.out.println(t);
				return;
			}
			if(i==j&&--RC[0]==0){
				System.out.println(t);
				return;
			}
			if(i+j+1==N&&--RC[1]==0){
				System.out.println(t);
				return;
			}
		}

  		//ループを抜けた=ビンゴが無かったので-1
		out.println(-1);

		out.close();
	}
}

D - Intersecting Intervals

問題文はこちら

$l$でソートして順にPriorityQueueに入れていき、PriorityQueueの中で$r$が今見ている区間の$l$よりも小さいものを削除することで、PriorityQueueの要素数を用いて数え上げを高速に行なうことができます。

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の受け取り
		int N = sc.nextInt();

  		//区間の受け取りとソート
		int[][] range = sc.nextInt(N,2);
		Arrays.sort(range,Arrays::compare);

  		//数え上げ用変数
		long ans = 0;

  		//rの値を昇順に並べる用
		PriorityQueue<Integer> queue = new PriorityQueue<>();

  		//先頭から順に見ていく
		for(int[] r:range){

  			//自身と共通部分を持たない区間は取り出す
			while(queue.size()>0&&queue.peek()<r[0])
				queue.poll();

    		//自身と共通部分を持つ区間を足す
			ans += queue.size();

   			//rの記録
			queue.add(r[1]);
		}

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

		out.close();
	}
}

感想

A,B:易しい
C:そんなに難しくはない
D:ちょっと手間取った
という感じでした。

う～ん…速解き回で2ペナは大きな痛手でした…。