AtCoder Beginner Contest 096

※今回は不参加で、問題はすべてコンテスト終了後に解きました。

A - Day of Takahashi

out.println(a<=b?a:a-1);

B - Maximum Sum

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), k=sc.nextInt();
		int total = a+b+c;
		int max = max(a,b,c);
		int pow = (int)Math.pow(2,k);
		out.println((total-max)+max*pow);
	}
	
	static int max(int... ar) {
		Arrays.sort(ar);
		return ar[ar.length-1];
	}
}

一番大きい数字を2倍していけばいいのではと考え、素直に実装した。

C - Grid Repainting 2

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int[] dx = {0,1,0,-1};
	static int[] dy = {-1,0,1,0};
 
	public static void main(String[] args) {
		int h=sc.nextInt(), w=sc.nextInt();
		char[][] map = new char[h+2][w+2];
		for (int i=1; i<h+1; i++) {
			String s = sc.next();
			for (int j=0; j<w; j++) {
				map[i][j+1] = s.charAt(j);
			}
		}
 
		boolean isAchievable = true;
		loop: for (int i=1; i<h+1; i++) {
			for (int j=1; j<w+1; j++) {
				if (map[i][j]=='#') {
					boolean isBlack = false;
					for (int k=0; k<4; k++) {
						if (map[i+dy[k]][j+dx[k]]=='#') isBlack = true;
					}
					if (!isBlack) {
						isAchievable = false;
						break loop;
					}
				}
			}
		}
 
		out.println(isAchievable?"Yes":"No");
	}
}

正直に告白すると、今回の問題は4問ともすべて解説を見てから解いている。
それでこの問題だが、すべての黒マスについて「上下左右のマスのうち、少なくとも一つが黒マス」という形になっていれば、達成できる。逆に、「上下左右すべてが白マス」という黒マスがあれば、達成できないということになる。
よって、すべての黒マスについて、上下左右のマスを調べればよい。

D - Five, Five Everywhere

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		List<Integer> list = primeList(55555);
		for (int i=0; i<n; i++) {
			out.print((i==0?"":" ")+list.get(i));
		}
	}
	
	static List<Integer> primeList(int n) {
		List<Integer> list = new ArrayList<>();
		boolean[] prime = new boolean[n+1];
		Arrays.fill(prime,true);
		prime[0]=false; prime[1]=false;
		for (int i=2; i<Math.sqrt(n); i++) {
			if (!prime[i]) continue;
			for (int j=2; i*j<=n; j++) {
				prime[i*j] = false;
			}
		}
		for (int i=0; i<prime.length; i++) {
			if (prime[i] && i%5==1) list.add(i); 
		}
		return list;
	}
}

メソッド「primeList」では、「n以下かつ、5で割って1余る素数」のリストを返すようにしている。
まずメインメソッドでprimeListを引数55555で動作させ、戻り値をlistに格納する。そしてその中から、小さい順にn個を出力して解答の数列としている。

このメソッドの作成にあたって、以下のページを参考にしました。
Javaで素数を求めるプログラムを実装 - にわとりプログラマーの備忘録

まとめ

とりあえず、競プロを休止していた期間に行われたコンテストについては、これですべて解き終わった。今日開催されるABC097は１か月ぶりのコンテストということになるけれど、悲惨な結果に終わるような気がしてならない。
それと、今回使った「n以下の素数をリストとして返すメソッド」というのは便利そうなので、作って記事にしようと思った。