Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-26SRM360, SRM361 (Practice)

SRM360 (Practice)

SRM360 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM360 (Practice) - hama_DU@TopCoderへの道

寝落ち。

問題結果ポイントその他
250SumOfSelectedCellsOpened0.00難しい。editorial読んで解いた
500PrinceOfPersiaOpened0.00最大流。BruteForceしてもいいはず
1000ConvexArrayOpened0.00あとでやる

SRM 360 SumOfSelectedCells

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

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

  • editorial読んで実装。
    • 納得はした。
import java.util.HashSet;
import java.util.Set;

public class SumOfSelectedCells {
	static final String ok = "CORRECT";
	static final String ng = "INCORRECT";
	
	public int[][] rotate(int[][] tbl) {
		int w = tbl[0].length;
		int h = tbl.length;
		int[][] newtbl = new int[w][h];
		for (int i = 0 ; i < w ; i++) {
			for (int j = 0 ; j < h ; j++) {
				newtbl[i][j] = tbl[j][i];
			}
		}
		return newtbl;
	}
	
	public String hypothesis(String[] table) {
		int h = table.length;
		int w = table[0].split(" ").length;
		
		int[][] number = new int[h][w];
		for (int i = 0 ; i < h ; i++) {
			String[] l = table[i].split(" ");
			for (int j = 0 ; j < w ; j++) {
				int val = Integer.valueOf(l[j]);
				number[i][j] = val;
			}
		}
		if (h < w) {
			number = rotate(number);
			int t = w;
			w = h;
			h = t;
		}
		
		if (h != w) {
			for (int i = 0 ; i < w ; i++) {
				Set<Integer> set = new HashSet<Integer>();
				for (int j = 0 ; j < h ; j++) {
					set.add(number[j][i]);
				}
				if (set.size() >= 2) {
					return ng;
				}
			}
			return ok;
		} else {
			for (int i = 0 ; i < w ; i++) {
				for (int j = 0 ; j < h ; j++) {
					for (int k = i+1 ; k < w ; k++) {
						for (int l = j+1 ; l < h ; l++) {
							if (number[j][i] + number[l][k] != number[l][i] + number[j][k]) {
								return ng;
							}
						}
					}					
				}
			}
			return ok;
		}
	}
}

SRM 360 PrinceOfPersia

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

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

  • 最大流っぽい
    • 蟻本を見ながらグラフ構築。
    • この問題は「頂点に流量の制約がある場合」に相当する。
  • 出した。
    • WA。あれ?
    • グラフの作り方が違ってた・・・あとノード最大数は100じゃ足りない。
  • 修正したら通った。
  • ちなみに、Pの周りを#で囲めば必ず到達不可になるので、必要なブロックの数は高々4。
    • このことから、ブロックの置き方をすべて試すBruteForce解もあるんじゃないかと思う
      • 100C1 + 100C2 + 100C3 + 100C4 = 4M+α ぐらい。
      • 未検証
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class PrinceOfPersia {

	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, 1, 0, -1};
	
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}
	
	public int minObstacles(String[] maze) {
		int h = maze.length;
		int w = maze[0].length();
		
		// 最大流
		boolean[][] done = new boolean[200][200];
		int nodes = h * w;
		init(500);
		
		int sx = 0, sy = -1;
		int gx = 0, gy = -1;
		int fromid = 0;
		int toid = 0;
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (maze[i].charAt(j) == 'P') {
					if (sy == -1) {
						sx = j;
						sy = i;
						fromid = i*w+j;
					} else {
						gx = j;
						gy = i;
						toid = i*w+j;
					}
				}
				if (maze[i].charAt(j) != '#') {
					int id1 = i*w+j;
					edge(id1, id1+200, 1);
				}
				
				for (int d = 0 ; d < 4 ; d++) {
					int tx = j+dx[d];
					int ty = i+dy[d];
					if (tx < 0 || tx >= w || ty < 0 || ty >= h) {
						continue;
					}
					if (maze[i].charAt(j) != '#' && maze[ty].charAt(tx) != '#') {
						int id1 = i*w+j;
						int id2 = ty*w+tx;
						edge(id1+200, id2, 100);
						edge(id2+200, id1, 100);
					}
				}
			}
		}
		
		// 直接行けるかチェック
		int dd = Math.abs(sx - gx) + Math.abs(sy - gy);
		if (dd == 1) {
			return -1;
		}	
		return max_flow(fromid+200, toid);
	}
}

SRM 360 ConvexArray

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

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

  • 幾何っぽい絵が出てきたのでそっと問題を閉じた

SRM361 (Practice)

SRM361 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM361 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250WhiteHatsAccepted225.46矛盾をチェック
500ReverseDistanceAccepted150.00再帰、全探索
1000WeighingScaleOpened0.00全然分からん

SRM 361 WhiteHats

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

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

  • 方針検討しながら行き当たりばったりで書いた
    • まず、各人が報告した数は2種類か1種類のはず
    • 1種類の時
      • 被ってる帽子は全て同じ色
      • 数が0なら全員黒、数が(人数-1)のときは全員白
    • 2種類の時
      • (報告した数の最大) - (最小) = 1 で、最大が白い帽子を被ってる人の数
      • さらに、大きな数を報告した人は全員黒、小さい数を報告した人は全員白
      • 以上を数えて検証する
import java.util.HashSet;
import java.util.Set;

public class WhiteHats {
	public int whiteNumber(int[] count) {
		int people = count.length;
		int many = -1;
		int less = 50;
		Set<Integer> a = new HashSet<Integer>();
		for (int i = 0 ; i < people ; i++) {
			many = Math.max(many, count[i]);
			less = Math.min(less, count[i]);
			a.add(count[i]);
		}
		if (a.size() >= 3) {
			return -1;
		} else if (a.size() == 1) {
			if (many == 0) {
				return 0;
			} else if (many == people - 1) {
				return people;
			} else {
				return -1;
			}
		}
		
		int black = 0;
		int white = 0;
		for (int i = 0 ; i < people ; i++) {
			if (count[i] == many) {
				black++;
			} else {
				white++;
			}
		}
		if (white == many && white - 1 == less) {
			return white;
		}
		return -1;
	}
}

SRM 361 ReverseDistance

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

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

  • 方針を検討
    • DP?状態の持ち方がわからない・・・
    • よく考えると求めるべき数の左半分が決まれば右半分も自動的に決まるので全探索でよさそう
      • 証明はできないけど求めるべき数の桁数は最大でもdifferenceの2倍程度な気がする
      • なので計算すべき量は O(10^6+α) ぐらいだろう
  • 実装。
    • 文字列インデックス指定ミスでしばらくハマる・・・
    • サンプル通った。
  • 最大ケース(900000?)を突っ込んでみる
    • 0.5sで終わる。答えも正しそう。
    • これは大丈夫だろ、出しちゃえ!
  • 再度戻ってくる。コード見直し
    • 繰り下がり処理ミスってる!
      • 繰り下がりフラグを立てたまま再帰から戻ってくるときに戻してない
    • 修正して再提出。なんでこれでサンプル通ったの・・・?
public class ReverseDistance {
	long diff;
	String dif;
	int dlen;
	int len;
	int[] arr;
	int[] flg;
	long min;
	
	public void dfs(int i) {
		if (i >= (len)/2) {
			long number = 0;
			for (int j = len-1 ; j >= 0 ; j--) {
				number *= 10;
				number += arr[j];
			}
			String rev = new StringBuffer(String.valueOf(number)).reverse().toString();
			long revnumber = Long.valueOf(rev);
			if (number - revnumber == diff) {
				min = Math.min(min, number);
			}
			return;
		}
		for (int d = (i == 0) ? 1 : 0 ; d <= 9 ; d++) {
			arr[len-i-1] = d;
			arr[i] = d + (dif.charAt(dif.length()-i-1) - '0') + flg[i];
			if (arr[i] >= 10) {
				flg[i+1] = 1;
				arr[i] -= 10;
			} else {
				flg[i+1] = 0;
			}
			dfs(i+1);
		}
	}
	public String find(int difference) {
		diff = difference; 
		dif = String.valueOf(difference);
		dlen = dif.length();
		dif = "000000000000000000000000000000" + dif;
		for (int i = dlen ; i <= Math.min(12, dlen*2) ; i++) {
			arr = new int[i];
			flg = new int[i];
			len = i;
			min = Long.MAX_VALUE;
			dfs(0);
			if (min != Long.MAX_VALUE) {
				return String.valueOf(min);
			}
		}
		return "NONE";
	}
}

SRM 361 WeighingScale

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

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

  • 全く分からん・・・
    • 250と500の見直しに戻る