kanetaiの二次記憶装置

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

Rectangular Searching(AOJ No.0116), A reward for a Carpenter(AOJ No.0117), Property Distribution(AOJ No.0118)

Online Judge

リポジトリ

Rectangular Searching(AOJ No.0116)

Square Searching(AOJ No.0092)
と同じような問題だが、縦横が n\times nではなく、(H,W)で与えられ、
求めるのは、最大の正方形ではなく、最大の長方形。
制約
1 < H,W < 500

アルゴリズム

http://www.ipsj.or.jp/07editj/promenade/4304.pdfと本質的には同じ問題なので、
これの２番目の解き方でやってみたが、Memory Limit Exceededになってしまった。
javaでしかも、 H\times WのHashSetしかも要素がint i,jを持つオブジェクトだったためだと思われる。
上(プログラム・プロムナード)の解説では、 O(n^2)と書いていたが、そもそも、
リストの生成が定数オーダで計算できるとは思わないので、 O(n^2)になっていないと思う。
三番目に書いてあった、ナノピコ流のやり方は、ちゃんと読んでいないので分からない。

今回は、
まず、右に何個○('.')が続いているかを覚えておく2次元配列rowCountを作った。
これに対して、位置(i,j)を左上の頂点, 左下の頂点を(i,k)の長方形の面積は、
(i-k+1) \times \min_{i\leq k < H} \{ rowCount_{k, j} \}
で求まる。
せいぜい、 O(WH^2)。 500^3 = 125,000,000すこし、大きいけど、十分シンプルなのでこれでもとおる。

コード

ちょっとだけ、枝刈りしてる。

import java.util.*;
public class aoj0116 {
	static final Scanner stdin = new Scanner(System.in);
	static final int MAX = 500;
	static final int[][] rowCount = new int[MAX][MAX];
	public static void main(String[] args) {
		while(true){
			int H = stdin.nextInt(), W = stdin.nextInt(); stdin.nextLine();
			if(H == 0 && W == 0) break;
			for(int i = 0; i < H; ++i){
				char[] line = stdin.nextLine().toCharArray();
				for(int j = W-1; j >= 0; --j){
					if(line[j] == '.') rowCount[i][j] = 1 + (j == W - 1 ? 0 : rowCount[i][j+1]);
					else rowCount[i][j] = 0;
				}
			}
			int ans = 0;
			for(int i = 0; i < H; ++i){
				for(int j = 0; j < W; ++j){
					if(rowCount[i][j] == 0) continue;
					int m = Integer.MAX_VALUE;
					for(int k = i; k < W; ++k){
						m = Math.min(m, rowCount[k][j]);
						if(m==0) break;
						ans = Math.max(ans, (k-i+1)*m);
					}
				}
			}
			System.out.println(ans);
		}
	}
}

A reward for a Carpenter(AOJ No.0117)

重み付き有向グラフと、固定コスト、報酬、出発地点、中継地点が与えられる。
出発地点から中継地点を間で行き、出発地点に帰ってきたときの、
最大の利益 = 報酬 - 合計重み(移動コスト) - 固定コストを求める。
制約
0<ノード数≦20

コード

あいかわらず、もんだいが、あいまいだなあ。
わーしゃるせんせい、ふろいどせんせい、ありがとう。

import java.util.*;
public class aoj0117 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2;
	public static void main(String[] args) {
		int n = stdin.nextInt(), m = stdin.nextInt(); stdin.nextLine();
		int[][] G = new int[n][n];
		for(int i = 0; i < n; ++i){
			Arrays.fill(G[i], INF);
			G[i][i] = 0;
		}
		for(int i = 0; i < m; ++i){
			String[] line = stdin.nextLine().split(",");
			int a1 = Integer.parseInt(line[0])-1, b1 = Integer.parseInt(line[1])-1;
			G[a1][b1] = Integer.parseInt(line[2]);
			G[b1][a1] = Integer.parseInt(line[3]);
		}
		String[] line = stdin.nextLine().split(",");
		int x1 = Integer.parseInt(line[0])-1, x2 = Integer.parseInt(line[1])-1;
		int y1 = Integer.parseInt(line[2]), y2 = Integer.parseInt(line[3]);
		APSPResult ret = FloydWarshall(G);
		System.out.println(y1 - ret.getDist(x1, x2) - ret.getDist(x2,x1) - y2);
	}
	@SuppressWarnings("unused") public static class APSPResult{
		private int[][] dist; // dist[d]:= shortest path to d
		private int[][] prev; // back pointers
		private boolean hasNegativeCycle;
		public APSPResult(int[][] dist, int[][] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); }
		final private void set(int[][] dist, int[][] prev, boolean hasNegativeCycle){ this.dist = dist; this.prev = prev; this.hasNegativeCycle = hasNegativeCycle; }
		final public int getDist(int i, int j){ return dist[i][j]; }
	}
	public static APSPResult FloydWarshall(int[][] G){
		int n = G.length;
		int[][] prev = new int[n][n], dist = new int[n][n];
		for(int i = 0; i < n; ++i){
			System.arraycopy(G[i], 0, dist[i], 0, n);
			dist[i][i] = 0;
			for(int j = 0; j < n; ++j) prev[i][j] = (G[i][j] != INF ? i : -1);
		}
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				if(dist[i][k] >= INF) continue;
				for(int j = 0; j < n; ++j){
					int newDist = dist[i][k] + dist[k][j];
					if(dist[i][j] > newDist){
						dist[i][j] = newDist;
						prev[i][j] = prev[k][j];
					}
				}
			}
		}
		boolean hasNegativeCycle = false;
		for(int i = 0; i < n; ++i) if(dist[i][i] < 0){ hasNegativeCycle = true; break; }
		return new APSPResult(dist, prev, hasNegativeCycle);
	}
}

Property Distribution(AOJ No.0118)

三種類の文字からなる H\times Wのマップが与えられる。
四近傍連結でエリア分けしたとき、いくつのエリアに分かれるかな？
制約
0 < H ,W \leq 100

アルゴリズム

AOJ No.0118に着いたぞ
100\times 100 = 10^4なら再帰DFSでおkだろうｖ(*´∀｀*)ｖ。→Runtime Error (スタックオーバーフロー)ガ―(´･ω･|||)―ン!!
「Javaのstackはdefaultで小さいのよ。そんなことも分からないなんて、貴方って、本当に最低の屑だわ！」
こんなにJavaとC++で制約に差があるとは思わなかった…！
これじゃ、俺…Javaを使いたくなくなっちまうよ…
こんな言語、使う価値なんかない！俺はもう練習のためにJavaを使いたくない！
使うなら勝手にやってくれ！　俺はJavaをやめる！
この記事はアンチJava臭いけどそれくらいは、どんな記事だってあるさ。俺だってそういう経験はあるしね。
でも今は、そんな事はどうでもいいんだ。 重要なことじゃない。
C++であれば俺だってDFSしますよ、猿渡さん！

もうBFSでいいや...(´･ω･｀)

コード

C++なら再帰DFSで勝てます。
いやあ…AOJ No.0118は強敵でしたね

import java.util.*;
public class aoj0118 {
	static final Scanner stdin = new Scanner(System.in);
	static class Point{ int i,j; Point(int i, int j){ this.i = i; this.j = j; }}
	public static void main(String[] args) {
		while(true){
			int H = stdin.nextInt(), W = stdin.nextInt(); 
			if(H == 0 && W == 0) break;
			stdin.nextLine();
			char[][] map = new char[H+2][W+2];
			for(int i = 0; i < H+2; ++i) Arrays.fill(map[i], ' ');
			for(int i = 0; i < H; ++i){
				char[] line = stdin.nextLine().toCharArray();
				for(int j = 0; j < W; ++j) map[i+1][j+1] = line[j];
			}
			int ans = 0;
			for(int i = 1; i <= H; ++i){
				for(int j = 1; j <= W; ++j){
					if(map[i][j] != ' '){
						BFS(i,j, map);
						ans++;
					}
				}
			}
			System.out.println(ans);
		}
	}
	static void BFS(int i, int j, char[][] map){
		char c = map[i][j];
		LinkedList<Point> q = new LinkedList<Point>();
		q.add(new Point(i,j));
		while(!q.isEmpty()){
			Point p = q.poll();
			map[p.i][p.j] = ' ';
			if(map[p.i+1][p.j] == c) q.push(new Point(p.i+1, p.j));
			if(map[p.i-1][p.j] == c) q.push(new Point(p.i-1, p.j));
			if(map[p.i][p.j+1] == c) q.push(new Point(p.i, p.j+1));
			if(map[p.i][p.j-1] == c) q.push(new Point(p.i, p.j-1));
		}
	}
}