ABC288A～Dの解答[Java]

はじめに

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

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

A - Many A+B Problems

問題文はこちら

普通にA+Bを出力するだけですね。

A.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){

		//Nの受け取り 
		int N = System.in.nextInt();

		//N回A+Bを出力する
		while(N-->0){
			System.out.println(System.in.nextInt()+System.in.nextInt());
		}
 
		System.out.close();
	}
}

普段のAもこれくらいで良い気がしてます…。

B - Qualification Contest

問題文はこちら

上位$K$人の情報しか必要でないので$K$個文字列を受け取ってソートし、それを順に出力しました。
重複するハンドルネームは制約上無いのでソートするのにTreeSetを使いました。

B.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、Kの受け取り
		int N = System.in.nextInt();
		int K = System.in.nextInt();

		//昇順で並べ替える用
		TreeSet<String> set = new TreeSet<>();

		//上位K人のハンドルネームを入れる
		while(K-->0)
			set.add(System.in.next());

		//先頭から順に出力する
		for(String str:set)
			System.out.println(str);
 
		System.out.close();
	}
}

これもそこまで難しくなかったですね。
$K$人のハンドルネームを固定長配列で受け取ってArrraysのsortメソッドを使っても良いかと思います。

C - Don’t be cycle

問題文はこちら

公式解説の通り、全域木を作ることを考えれば良いかなと思って、UnionFindを用いて解きました。

C.java

class Main{
 
	static final boolean autoFlush = false;
	static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
 
	public static void main(String[] args){
 
		//N、Mの受け取り
		int N = System.in.nextInt();
		int M = System.in.nextInt();

		//UnionFind
		UnionFind uf = new UnionFind(N+1);

		//消す辺の数
		int ans = 0;
		while(M-->0){
			int A = System.in.nextInt();
			int B = System.in.nextInt();

			//既に同一の木に存在するならその辺を消す
			if(!uf.unite(A,B))
				ans++;
		}

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

気付くのが早かったので助かりました。

D - Range Add Query

問題文はこちら

解法は公式解説の通りなので詳しい説明はそちらに任せます(手抜き)。

D.java

import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

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

		//先頭、末尾に0を挿入したAを受け取る
		int[] A = new int[N+2];
		for(int i=1;i<=N;i++)
			A[i] = sc.nextInt();

		//階差数列の構築
		int[] subA = new int[N+1];
		for(int i=0;i<=N;i++)
			subA[i] = A[i+1]-A[i];

		//階差数列の累積和(添え字modKで分ける)
		//sum[i][j]:添え字modK=iのみでのj個までの総和
		long[][] sum = new long[K][N+2];
		for(int i=0;i<=N;i++){
			for(int j=0;j<K;j++){
				if(i%K==j)
					sum[j][i+1] = subA[i];
				sum[j][i+1] += sum[j][i];
			}
		}

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

		//出力高速化用
		StringBuilder ans = new StringBuilder();

		while(Q-->0){
			int l = sc.nextInt();
			int r = sc.nextInt();

			//各あまりの累積和から良い数列に出来るか検証
			boolean isGood = true;
			for(int i=0;i<K;i++){

				//累積和の添え字が解説のものと+1ズレてるので注意

				long temp1 = sum[i][r+1];
				if(r%K==i)
					temp1 -= A[r+1];//端っこの調整

				long temp2 = sum[i][l-1];
				if((l-1)%K==i)
					temp2 -= A[l-1];//端っこの調整

				//総和が0になり得るか論理積を取る
				isGood &= temp1==temp2;
			}

			//良い数列に出来そうかをansに
			ans.append(isGood?"Yes":"No");
			ans.append("\n");
		}

		//答えの出力
		System.out.print(ans.toString());
	}
}

添え字が永遠に合わなくてすんごい理解に時間がかかりました…。

感想

A:すごく易しい
B:これも易しい
C:発想が比較的早かったのに救われた
D:手も足も出なかった…
って感じでした。

3完でもこの回ではレートが上がりました。良かった…。