Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-18SRM396 (Practice)

easyが早めに出せたのは良かった

279/547位

問題結果ポイントその他
250DNAStringAccepted232.23全探索
500FixImageTLE0.00方針は正しかったが実装がまずかった
1000 MoreNimOpened0.00斜め読みしただけ

SRM 396 DNAString

|  SRM 396 DNAString - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 396 DNAString - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8584

コーディングフェーズ

  • 最大で周期pにするとき、最小で何文字変える必要があるか
  • 方針を検討
    • 周期pで作る時、最初のp文字が決まれば生成すべき文字列は決まる
      • これだと最大で 4^p (p <= 2500)の検証が必要になり、間に合わない
    • 周期pにするとき、{a, a+p, a+2p , ...} (0 <= a <= p-1) で文字の登場回数を数え、一番多いものを採用する
      • 必要な変更回数は ∑(count({a, a+p, a+2p, ...}) - max(登場回数))
    • すべての周期を確かめ、一番小さいものを採用する。
    • 計算量はO(n^4+α) (n <= 50)
  • テスト
    • 通った。念のためランダム文字列2500, p=2500で確かめる
    • 間に合った(1.2s)。ちょっと不安だけどこれで提出

システムテスト

  • 最大ケースで1.9sかかる。あぶない!

public class DNAString {
	public int minChanges(int mp, String[] dna) {
		String line = "";
		for (String x : dna) {
			line += x;
		}
		
		int len = line.length();
		int min = Integer.MAX_VALUE;
		for (int p = 1 ; p <= mp ; p++) {
			int cnt = 0;
			for (int md = 0 ; md < p ; md++) {
				char[] clist = new char[512];
				int idx = md;
				int max = 0;
				int total = 0;
				while (idx < len) {
					char c = line.charAt(idx);
					clist[c]++;
					max = Math.max(max, clist[c]);
					idx += p;
					total++;
				}
				cnt += (total - max);
			}
			min = Math.min(min, cnt);
		}
		return min;
	}
}




SRM 396 FixImage

|  SRM 396 FixImage - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 396 FixImage - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8615

コーディングフェーズ

  • 方針を検討
    • 同じグループに属する#に対して、縦or横で # と # に挟まれた部分を塗りつぶしていけばよさそう
  • 実装開始
    • whileループでマスの状態に変化がない間以下を繰り返す
      • 同じグループに属する#を調べ、map[y][x] に保存
        • その際、各グループに対して、同じrow or column で#の出現位置の最大最小を覚えておく
      • 各row or column で、覚えさせておいた最大最小の間を # で塗りつぶす
    • しばらく配列外アクセスなどでハマる
  • テスト
    • サンプル通った。
    • ランダムに 50x50 を配置したケースでテスト
    • 1.4sかかる。不安・・・
      • 改善方法を考える。思い浮かばない
    • まあいいや、とりあえず提出

システムテスト後

  • TLEを食らう
    • そう単純ではなかったか。
    • グループの併合に多くのステップを要するケースでTLEしている模様
    • 何か効率的な方法がある?グループをunion-findかなんかで管理して探索コスト(ループ回数)を減らすのか?
  • Javaで書かれた他の人のコードを見る
    • 基本的な方針は正しいっぽい
    • そういえば塗りつぶす操作を全グループの処理が終わった後にしてるけど内側にしても挙動は変わらんよね。あわよくばループ回数減らせるかも
      • あ、それっぽい
      • メモリの節約にもなるし・・・
    • 修正したら通った
      • 最大ケースで0.2s。劇的に変わるもんだなー
import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class FixImage {

	
	int[] dx = {0, 1, -1, 0};
	int[] dy = {1, 0, 0, -1};
	
	public String[] originalImage(String[] ai) {
		int row = ai.length;
		int col = ai[0].length();
		
		boolean[][] paint = new boolean[row][col];
		for (int i = 0 ; i < row ; i++) {
			for (int j = 0 ; j < col ; j++) {
				if (ai[i].charAt(j) == '#') {
					paint[i][j] = true;
				}
			}
		}
		
		boolean[][] added = new boolean[row][col];
		for (int r = 0 ; r < row ; r++) {
			Arrays.fill(added[r], true);
		}
		
		while (true) {
			int[][] map = new int[row][col];
			int gidx = 0;
			int[][] xrange = new int[51][2]; // 提出時は int[][][] xrange = new int[3000][51][2]
			int[][] yrange = new int[51][2]; // としていたがこれを内側(各グループの処理内)に持ってきた

			boolean proc = false;
			for (int i = 0 ; i < row ; i++) {
				for (int j = 0 ; j < col ; j++) {
					if (map[i][j] == 0 && paint[i][j]) {
						gidx++;
						for (int d = 0 ; d < 51 ; d++) {
							xrange[d][0] = 51; // fromx
							xrange[d][1] = -1; // tox
							yrange[d][0] = 51; // fromy
							yrange[d][1] = -1; // toy						
						}
						
						Queue<Integer> q = new ArrayBlockingQueue<Integer>(3000);
						q.add(i*100+j);
						while (q.size() >= 1) {
							int stat = q.poll();
							int r = stat / 100;
							int c = stat % 100;
							if (r < 0 || c < 0 || r >= row || c >= col) {
								continue;
							}
							if (!paint[r][c]) {
								continue;
							}
							if (map[r][c] != 0) {
								continue;
							}

							xrange[r][0] = Math.min(xrange[r][0], c);
							xrange[r][1] = Math.max(xrange[r][1], c);
							yrange[c][0] = Math.min(yrange[c][0], r);
							yrange[c][1] = Math.max(yrange[c][1], r);
							map[r][c] = gidx;
							
							
							for (int d = 0 ; d < 4 ; d++) {
								q.add((r+dy[d])*100+(c+dx[d]));
							}
						}
						
						for (int c = 0 ; c < col ; c++) {
							for (int r = yrange[c][0] ; r <= yrange[c][1] ; r++) {
								if (!paint[r][c]) {
									proc = true;
								}
								paint[r][c] = true;
							}
						}
						for (int r = 0 ; r < row ; r++) {
							for (int c = xrange[r][0] ; c <= xrange[r][1] ; c++) {
								if (!paint[r][c]) {
									proc = true;
								}
								paint[r][c] = true;
							}
						}
					}
				}
			}
			if (!proc) {
				break;
			}
		}
		
		String[] ret = new String[row];
		for (int i = 0 ; i < row ; i++) {
			String line = "";
			for (int j = 0 ; j < col ; j++) {
				if (paint[i][j]) {
					line += '#';
				} else {
					line += '.';
				}
			}
			ret[i] = line;
		}
		return ret;
	}
}