Square Searching(AOJ No.0092), Leap Year(AOJ No.0093)
Square Searching(AOJ No.0092)
の'.'と'*'から成るマップが与えられて、
'.'だけを含む正方形の辺の長さの最大値を求める。
制約
アルゴリズム
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の正方形が作れることがわかる。
正方形の左下の頂点座標(i,j)の選択し、さらにを決める必要があるが、線形探索すると、
i,j,kの3重ループでになってしまう。
これでは計算量的には厳しいと思われる(シンプルだからなのか、テストケースが緩いのか知らないがでも通るみたい).
は2分探索すればよいので、なので、たぶん大丈夫。
コード
若干スパゲッティな気がする。
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を出力する。
データセットごとに改行する。
制約
コード
最後のデータセットに改行をつけて、プレゼンテーションエラー出した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; } }