kanetaiの二次記憶装置

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

Square Searching(AOJ No.0092), Leap Year(AOJ No.0093)

リポジトリ

Square Searching(AOJ No.0092)

 n \times nの'.'と'*'から成るマップが与えられて、
'.'だけを含む正方形の辺の長さの最大値を求める。
制約
 1\leq n \leq 10^3

アルゴリズム

dot[i+1][j+1] = 四角形map[0][0]〜map[i][j]の'.'の数
とするとmap[i-k][j-k]を左下の頂点とする一辺がkの正方形に含まれる'.'の数は
S = dot[i][j] + dot[i-k][j-k] - dot[i-k][j] - dot[i][j-k]
で求まる。
S =  k^2なら長さkの正方形が作れることがわかる。

正方形の左下の頂点座標(i,j)の選択し、さらに kを決める必要があるが、線形探索すると、
i,j,kの3重ループで O(n^3) \rightarrow 10^9になってしまう。
これでは計算量的には厳しいと思われる(シンプルだからなのか、テストケースが緩いのか知らないが O(n^3)でも通るみたい).
 kは2分探索すればよいので、 O(n^2\log n) \rightarrow 10^6 \log 10^3 \approx10^6 \log 2^{10} = 10^7なので、たぶん大丈夫。

コード

若干スパゲッティな気がする。

import java.util.*;
public class aoj0092 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N_MAX = 1001;
	public static void main(String[] args) {
		int[][] map = new int[N_MAX][N_MAX], dot = new int[N_MAX][N_MAX]; //dot[i+1][j+1], 四角形map[0][0]〜map[i][j]の.の数
		while(true){
			int n = stdin.nextInt();
			if(n==0) break;
			for(int i = 0; i<n; ++i){
				char[] line = stdin.next().toCharArray();
				for(int j = 0; j < n; ++j){
					map[i][j] = (line[j] == '.') ? 1 : 0;
				}
			}
			dot[1][1] = map[0][0];
			for(int i = 2; i <= n; ++i){
				dot[1][i] = map[0][i-1] + dot[1][i-1];
				dot[i][1] = map[i-1][0] + dot[i-1][1];
			}
			for(int i = 2; i <= n; ++i)
				for(int j = 2; j <= n; ++j)
					dot[i][j] = map[i-1][j-1] + dot[i-1][j] + dot[i][j-1] - dot[i-1][j-1];
			int max = 0, l = 1, u = n, k = (l+u)/2;
			while(l<=u){
				LOOP: for(int i=k; i<=n; ++i){
					for(int j=k; j<=n; ++j){
						if(dot[i][j] - dot[i-k][j] - dot[i][j-k] + dot[i-k][j-k] == k*k){
							max = k;
							break LOOP;
						}
					}
				}
				if(max == k) l = k + 1;
				else u = k - 1;
				k = (l+u)/2;
			}
			System.out.println(max);
		}
	}
}

Leap Year(AOJ No.0093)

a,bが与えられて、a年〜b年にある閏年を出力する。
閏年が無い場合は, NAを出力する。
データセットごとに改行する。
制約
 0 < a\leq b < 3000

コード

最後のデータセットに改行をつけて、プレゼンテーションエラー出したorz...

import java.util.*;
public class aoj0093 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		boolean ini = true;
		while(true){
			int a = stdin.nextInt(), b = stdin.nextInt();
			if(a==0 && b==0) break;
			if(!ini) System.out.println("");
			ini = false;
			boolean flag = false;
			for(int y = a; y <= b; ++y)
				if(isLeapYear(y)){
					System.out.println(y);
					flag = true;
				}
			if(!flag) System.out.println("NA");
		}
	}
	public static final boolean isLeapYear(int y){
		return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
	}
}