arc の日記

はてなダイアリーから引っ越してきました。さらに新しい記事は https://junkato.jp/ja/blog/ で書いています。

Google CodeJam 2010 Round 1C 問題C

programming

年に一度、Googleが主催するプログラミングコンテストCode Jam - Google’s Coding Competitionsの季節がやってきました。先日は24時間の間に3問を解くQualification Roundが開かれ、ここ数日は2時間半の間に3問を解くRound 1が開かれていました。
解答を提出した全員の用いたソースコードを閲覧できるのが面白いところで、上位陣のコードは非常に洗練されており、本当に参考になります。
僕はというとRound 1Cでゆっくりしすぎてあえなく敗退（去年より落ちてるという悲しい事実…）しましたが、負け惜しみでゆっくりした成果を貼っておきます。

Round 1C 問題C

この問題は、白と黒のまだら模様になっている大きな盤面から、チェスボードとして使えるなるべく大きな部分をできるだけ多く切り出した結果を解答として提出します。
まだら模様になっている大きな盤面とは、例えば次のような板です。チェスボードとして使える、というのは、白と黒が交互に現れる正方形を意味します。板のなかで赤で囲まれた部分が条件に合致します。注意しなければいけないのは、白および黒の単位一枚でも、幅1高さ1のチェスボードとして使えるということです。
Share photos on twitter with Twitpic
このケースでは、幅6のチェスボードが2枚、幅4が3枚…取れるので、次のような出力を提出すれば正解です。

Case #1: 5
6 2
4 3
3 7
2 16
1 53

で、出力を得るだけなら画像として見える形にしなくてもいいんですが、僕は状況をうまくつかみたくて、コンテスト中にこの可視化のコードを書いていました。
正しい出力が得られるようになったところで時間切れになったのでかっこ悪いことこの上ないのですが…こういうことをする人はあまりいないと思ったので、わざわざ記事にしているわけです。

今現在 Practice Modeで問題Cを閲覧できるようになっており、 試しに C-large-practice.out の100個目のケースを可視化したらこうなりました。

#GCJ 100th input case of C-large-practice.in of Round1-C visu... on Twitpic

大きなチェスボードを切り出せるよう、問題の盤面が意図的に敷かれている様子を見て取れます。だから何って言われると悲しいけど！
Round 2に進んだ皆様におかれましては、僕のぶんまでぜひぜひ頑張ってください!!

以下、問題を解きつつ解答を可視化するソースコードが続きます。


本番ではクラスを二つに分け、一つは全問題に共通して使える基底クラス、もう一つがこの問題のためだけのクラスとしていましたが、 gcj2010.R1_C_MakingChessBoards.java にこの内容を保存すればコンパイルが通るように、一つのクラスにまとめました。

$ java gcj2010.R1_C_MakingChessBoards C-large-practice.in C-large-practice.out

というふうに実行してやると、解答が C-large-practice.out に出力される他、各ケース[t]について画像が images フォルダ内に case_[t].png として保存されます。（プログラム実行前に空の images フォルダを作っておく必要があります。）

アルゴリズム的にはごく素直な実装です。これでも充分、ノートPCで実行して C-large-practice.in をダウンロードしてから8分の提出時限に間に合いましたが、高速な処理をお望みの方は上位の方のコードを参考にしてみてください。

package gcj2010;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.awt.image.WritableRaster;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;

import javax.imageio.ImageIO;

public class R1_C_MakingChessBoards {
	private int M, N;
	private final int zoom = 10;

	public void doSolve(BufferedReader reader, BufferedWriter writer)
			throws IOException {
		String line = reader.readLine();
		try {
			int T = Integer.parseInt(line);
			for (int t = 1; t <= T; t++) {
				TreeMap<Integer, Set<Board>> results =
						new TreeMap<Integer, Set<Board>>();

				// Setup data.
				String[] mn = reader.readLine().split(" ");
				M = Integer.parseInt(mn[0]);
				N = Integer.parseInt(mn[1]);
				int index = 0;
				boolean[] bits = new boolean[M*N];
				for (int m = 0; m < M; m ++) {
					line = reader.readLine();
					for (int n = 0; n < N/4; n ++) {
						char c = line.charAt(n);
						int b = c >= '0' && c <= '9' ? (c - '0') : c - 'A' + 10;
						for (int i = 3; i >= 0; i --) {
							bits[index ++] = ((b >> i) & 1) == 1;
						}
					}
				}

				// Cut out boards.
				boolean[] cutBits = new boolean[M*N];
				for (int size = min(M, N); size > 0; size --) {
					for (int m = 0; m <= M-size; m ++) {
						for (int n = 0; n <= N-size; n ++) {
							if (boardAvailableAt(bits, cutBits, m, n, size)) {
								cut(cutBits, m, n, size);
								Set<Board> boards = results.get(size);
								if (boards == null) {
									boards = new HashSet<Board>();
									results.put(size, boards);
								}
								boards.add(new Board(n, m, size));
							}
						}
					}
				}

				// Visualize the data.
				saveImageRepresentation(bits, results, N, t);

				// Print the answer.
				writer.write("Case #" + t + ": " + results.keySet().size());
				writer.newLine();
				for (Entry<Integer, Set<Board>> e :
						results.descendingMap().entrySet()) {
					writer.write(String.valueOf(e.getKey()));
					writer.write(" ");
					writer.write(String.valueOf(e.getValue().size()));
					writer.newLine();
				}
			}
		} catch (NumberFormatException nfe) {}
	}

	private int min(int a, int b) {
		return a>b?b:a;
	}

	private void cut(boolean[] cutBits, int m, int n, int size) {
		for (int y = m; y < m+size; y ++) {
			int i = y*N;
			for (int x = n; x < n+size; x ++) {
				cutBits[i+x] = true;
			}
		}
	}

	private boolean boardAvailableAt(
			boolean[] bits, boolean[] cutBits, int m, int n, int size) {

		// Scan for x
		int i = m*N;
		boolean b = !bits[i+n];
		for (int x = n; x < n+size; x ++) {
			if (bits[i+x] == b || cutBits[i+x]) {
				return false;
			}
			b = !b;
		}

		// Scan for y
		for (int y = m+1; y < m+size; y ++) {
			int j = y*N;
			b = bits[j+n-N];
			for (int x = n; x < n+size; x ++) {
				if (bits[j+x] == b || cutBits[j+x]) {
					return false;
				}
				b = !b;
			}
		}
		return true;
	}

	private void saveImageRepresentation(
			boolean[] bin, Map<Integer,Set<Board>> results, final int width, int t) {
		final BufferedImage sourceImage = getImageRepresentation(bin, width);
		final int w = width*zoom, h = sourceImage.getHeight()*zoom;
		BufferedImage image = new BufferedImage(w, h, BufferedImage.TYPE_INT_ARGB);
		Graphics2D g2 = image.createGraphics();
		g2.drawImage(sourceImage, 0, 0, w, h, null);
		g2.setColor(Color.red);
		for (Set<Board> bs : results.values()) {
			for (Board b : bs) {
				g2.drawRect(b.x*zoom, b.y*zoom,
						b.size*zoom-1, b.size*zoom-1);
			}
		}
		g2.dispose();
		try {
			ImageIO.write(image, "PNG",
					ImageIO.createImageOutputStream(new File(
							"images"+File.separator+"case_"+t+".png")));
		} catch (IOException e) {}
	}

	private static BufferedImage getImageRepresentation(boolean[] bin, int width) {
		int length = bin.length;
		int height = length / width;
		int[] binData = new int[length];
		for (int i = 0; i < length; i++) {
			binData[i] = bin[i] ? 0xffffffff : 0xff000000;
		}
		BufferedImage image = new BufferedImage(width, height,
				BufferedImage.TYPE_INT_ARGB);
		WritableRaster raster = image.getRaster();
		raster.setDataElements(0, 0, width, height, binData);
		return image;
	}

	private class Board {
		public int x, y, size;
		public Board(int x, int y, int size) {
			this.x = x;
			this.y = y;
			this.size = size;
		}
	}

	public static void main(String[] args) {
		R1_C_MakingChessBoards solver = new R1_C_MakingChessBoards();
		solver.solve(args);
	}

	public void solve(String[] args) {

		// Check arguments.
		if (args == null || args.length != 2) {
			System.out.println(
					"Usage: "+getClass().getSimpleName()+
					" [input file name] [output file name]");
			return;
		}

		// Open file streams.
		File inputFile = new File(args[0]);
		File outputFile = new File(args[1]);
		BufferedReader reader = null;
		BufferedWriter writer = null;
		try {
			reader = new BufferedReader(
					new FileReader(inputFile));
			writer = new BufferedWriter(
					new FileWriter(outputFile));
			doSolve(reader, writer);
		} catch (FileNotFoundException e) {
			System.out.println("File not found: "+
					inputFile.getPath());
		} catch (IOException e) {
			e.printStackTrace();
		}

		// Close streams.
		finally {
			try {
				if (reader != null) {
					reader.close();
				}
				if (writer != null) {
					writer.close();
				}
			} catch (Exception e) {}
		}
	}

}