ABC272A～Eの解答[Java]

はじめに

今回はA～Dがコンテスト中のものを、Eはコンテスト後に解いたものを載せます。

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

A - Integer Sum

問題文はこちら

ただ足すだけですね。

A.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{

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

		//数列を受け取って加算する
		int answer = 0;
		while(N-->0)
			answer += System.in.nextInt();

		//総和の出力
		System.out.println(answer);
 
		System.out.close();
	}
}

まぁ問題無いですね。

B - Everyone is Friends

問題文はこちら

これも全探索すれば良いですね。

B.java

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

		//joined[i][j]:i番目の人がj番目に参加したか
		boolean[][] joined = new boolean[N+1][M+1];

		//受け取って処理
		for(int i=1;i<=M;i++){
			int k = System.in.nextInt();
			while(k-->0){
				int person = System.in.nextInt();
				joined[person][i] = true;
			}
		}

		//全探索
		for(int i=1;i<=N;i++){
			for(int j=i+1;j<=N;j++){

				//どっかで同じ舞踏会に参加したか管理する変数
				boolean ok = false;

				//探索
				for(int k=1;k<=M;k++){
					if(joined[i][k]&&joined[j][k]){
						ok = true;
						break;
					}
				}

				//同一の舞踏会に参加してないなら終了
				if(!ok){
					System.out.println("No");
					System.exit(0);
				}
			}
		}

		//forを抜けた=全員条件を満たしているのでYesを出力
		System.out.println("Yes");
 
		System.out.close();
	}
}

変数がごちゃごちゃしてていろいろとミスってしまいました。もうちょっとスマートに書きたいですね。

C - Max Even

問題文はこちら

二つの整数を足して偶数ができるのは偶数と偶数、奇数と奇数の二通りです。
ということで、偶数だけ、奇数だけでArrayListに格納し、それぞれの最大値二つの大きい方が答えとなります。
偶数、奇数が$1$個以下の時もあるので注意しましょう。

C.java

class Main{
 
	static Library System = new Library(java.lang.System.in,java.lang.System.out);
 
	public static void main(String[] args)throws IOException{
 
		//Nの受け取り
		int N = System.in.nextInt();

		//偶奇を格納するリスト
		ArrayList<Integer> odd = new ArrayList<Integer>();
		ArrayList<Integer> even = new ArrayList<Integer>();
 
		//各要素を分類
		while(N-->0){
			int A = System.in.nextInt();
			if(A%2==0)
				even.add(A);
			else
				odd.add(A);
		}

		//ソート
		Collections.sort(even);
		Collections.sort(odd);

		//2個以上あるなら最大値二つの和を、1個以下なら-1
		int ev = even.size()>1?even.get(even.size()-1)+even.get(even.size()-2):-1;
		int od = odd.size()>1?odd.get(odd.size()-1)+odd.get(odd.size()-2):-1;

		//大きい方を出力
		System.out.println(Math.max(ev,od));
 
		System.out.close();
	}
}

思いのほかサクッと解けました。

D - Root M Leaper

問題文はこちら

BFSで解きました。
先に移動できるマスを調べてからでも良かったんですが、コンテスト中は思いつかなかったので毎度移動できる$i$を全探索する方法をとりました。

D.java

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

		//各マスの答えを格納する配列
		int[][] ans = new int[N][N];
		//初期値は-1で
		for(int i=0;i<N;i++)Arrays.fill(ans[i],-1);

		//bfs用
		LinkedList<Integer> bfs = new LinkedList<Integer>();

		//最初の位置を記録
		bfs.add(0);
		bfs.add(0);
		ans[0][0] = 0;

		//bfs
		while(bfs.size()>0){
			int x = bfs.pollFirst();
			int y = bfs.pollFirst();

			//次の座標のiを全探索
			for(int i=0;i<N;i++){
				int temp = M-(x-i)*(x-i);

				//iが適切な値でないならスキップ
				if(temp<0)
					continue;

				//平方数か調べる
				int j = (int)Math.sqrt(temp);
				if(j*j==temp){

					//平方数なら次の座標をbfsに加える
					if(y+j<N&&ans[i][y+j]==-1){
						ans[i][y+j] = ans[x][y]+1;
						bfs.add(i);
						bfs.add(y+j);
					}
					if(y-j>=0&&ans[i][y-j]==-1){
						ans[i][y-j] = ans[x][y]+1;
						bfs.add(i);
						bfs.add(y-j);
					}
				}
			}
		}

		//最終結果を出力
		System.out.println(ans," ");
 
		System.out.close();
	}
}

やってること自体はシンプルなんですが、いろいろと変数を間違えたりしてペナルティを頂いてしまいました･･･。ちゃんと変数名は考えよう！

E - Add and Mex

問題文はこちら

各操作後での最小の非負整数を考えると、要素の数が$N$個なので答えは$0～N$の中にあるはずです。なので、各要素が$0～N$であるとき以外は考えなくても良さそうだと考えられます。
各操作後での値の存在判定はHashSetで行ないました。

E.java

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

		//各操作後の整数の存在判定をする用のList
		ArrayList<HashSet<Integer>> list = new ArrayList<HashSet<Integer>>();
		for(int i=0;i<M;i++)list.add(new HashSet<Integer>());

		//各要素の操作後の値を記録
		for(int i=1;i<=N;i++){
			int A = System.in.nextInt();

			//負数なら0以上になるまで操作をすっ飛ばす
			int s = Math.max(1,-(A-i+1)/i);
			A += s*i;

			//N以下になるかM回操作が終わるまで記録
			for(int j=s-1;j<M&&A<=N;j++,A+=i)
				list.get(j).add(A);
		}

		//各操作後の最小の非負整数を探して出力
		for(HashSet<Integer> nums:list){
			int ans = 0;
			while(nums.contains(ans))ans++;
			System.out.println(ans);
		}
 
		System.out.close();
	}
}

コンテスト中はめんどくさそう･･･って思って飛ばしてしまいました。ちょっと後悔･･･。

感想

A:簡単
B:ちょっとめんどくさいけど比較的簡単
C:すぐ気づける内容だった
D:内容自体は簡単(実装力が足りなかった･･･)
E:言われてみれば確かに･･･
って感じでした。

ペナルティを頂いての4完だとレート下がりますね･･･。悲しい･･･。