読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Twin Prime(AOJ No.0150), Grid(AOJ No.0151), Bowling(AOJ No.0152)

リポジトリ

Twin Prime(AOJ No.0150)

nが与えられて、 \max\{q | q\leq n, q-p=2, p q素数 \}となる (p, q)を求める
制約
 5\leq n \leq 10,000

コード

その場で求めても十分間に合う

import java.util.*;
public class aoj0150 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 10001;
	public static final boolean[] sieve(int n){
		boolean[] ret = new boolean[n]; Arrays.fill(ret, true);
		ret[0] = ret[1] = false;
		for(int i = 2; i*i < n; ++i)
			if(ret[i]) for(int j = i*i; j < n; j+=i) ret[j] = false;
		return ret;
	}
	public static void main(String[] args) {
		boolean[] prime = sieve(N);
		int n;
		while((n = stdin.nextInt()) != 0){
			int pre = -1;
			for(int i = n; i >= 2; --i){
				if(prime[i]){
					if(pre-i == 2){
						System.out.println(i + " " + pre);
						break;
					}
					pre = i;
				}
			}
		}
	}
}

Grid(AOJ No.0151)

 n\times nの01マップが与えられて、縦横斜めの直線の1連続数の最大値を求める
制約
 2 \leq n \leq 255

コード

枝刈りしなくておk

import java.util.*;
public class aoj0151 {
	static final Scanner stdin = new Scanner(System.in);
	static int dx[] = {1, 0, 1, -1};
	static int dy[] = {0, 1, 1, 1};
	static int search(boolean[][] map, int y, int x, int d){
		int ret = 0;
		while(true){
			if(map[y][x]) ++ret;
			else break;
			y += dy[d]; x += dx[d];
		}
		return ret;
	}
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			boolean[][] map = new boolean[n+2][n+2];
			for(boolean[] x: map) Arrays.fill(x, false);
			for(int i = 1; i <= n; ++i){
				String l = stdin.next();
				for(int j = 0; j < l.length(); ++j) if(l.charAt(j) == '1') map[i][j+1] = true;
			}
			int ans = 0;
			for(int i = 1; i <= n; ++i)
				for(int j = 1; j <= n; ++j)
					for(int d = 0; d < 4; ++d) ans = Math.max(ans, search(map, i, j, d));
			System.out.println(ans);
		}
	}
}

Bowling(AOJ No.0152)

ボーリングしますた。スコア順に並べてください。スコアが同じ場合は、学籍番号の若い順に並べてください。

コード

実装ゲー

import java.util.*;
public class aoj0152 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n;
		while((n=stdin.nextInt()) != 0){
			stdin.nextLine();
			T[] record = new T[n];
			for(int i = 0; i < n; ++i) record[i] = new T(stdin.nextLine().split(" "));
			Arrays.sort(record);
			for(T t: record) System.out.println(t.id + " " + t.sum);
		}
	}
	static class T implements Comparable<T>{
		int sum, id;
		@Override public int compareTo(T o2) { return sum != o2.sum ? o2.sum - sum : id - o2.id; }
		T(String[] in){
			int[] frame = new int[10];
			id = Integer.parseInt(in[0]);
			int[] input = new int[in.length-1];
			for(int i = 0; i < input.length; ++i) input[i] = Integer.parseInt(in[i+1]);
			sum = 0;
			for(int i = 0, p = 0; p < 10; ++p){
				frame[p] = input[i] + input[i+1];
				if(p == 9){ //第10フレーム
					if(frame[p] >= 10) frame[p] += input[i+2]; //スペア or ストライク
				}else if(input[i] == 10){ //ストライク
					frame[p] += input[i+2];
					++i;
				}else{
					if(frame[p] == 10) frame[p] += input[i+2]; //スペア
					i+=2;
				}
				sum += frame[p];
			}
		}
	}
}