Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 340 CsCourses

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

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

  • 動的計画法+辞書順最小経路復元
    • 状態は [month][theoreticalValue][practicalValue]
    • 経路復元付きの場合はメモ化再帰すると楽。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CsCourses {
	int len;
	int[] tv;
	int[] pv;
	int[] exp;
	int bound;
	
	int[][][] memo = new int[51][51][51];
	int[][][] memo_prev = new int[51][51][51];

	
	public int dfs(int month, int ntv, int npv) {
		if (ntv >= bound && npv >= bound) {
			return 0;
		}
		if (memo[month][ntv][npv] >= 0) {
			return memo[month][ntv][npv];
		}
		
		int min = 100000;
		int mini = -1;
		for (int i = 0 ; i < len ; i++) {
			if ((ntv >= tv[i] && npv >= pv[i]) || (ntv < tv[i] - 1 || npv < pv[i] - 1)) {
				continue;
			}
			if (month >= exp[i]) {
				continue;
			}
			int ttv = Math.max(ntv, tv[i]);
			int tpv = Math.max(npv, pv[i]);
			int rec = dfs(month+1, ttv, tpv) + 1;
			if (min > rec) {
				min = rec;
				mini = i;
			}
		}
		memo[month][ntv][npv] = min;
		memo_prev[month][ntv][npv] = mini;
		
		return min;
	}
	
	public int[] getOrder(int[] t, int[] p, int[] expire, int sb) {
		bound = sb;
		tv = t;
		pv = p;
		exp = expire;
		len = tv.length;
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				Arrays.fill(memo[i][j], -1);
				Arrays.fill(memo_prev[i][j], -1);
			}
		}
		
		int num = dfs(0, 0, 0);
		if (num >= 1000) {
			return new int[]{};
		}
		
		int nowmonth = 0;
		int nowtv = 0;
		int nowpv = 0;
		List<Integer> takecourse = new ArrayList<Integer>();
		while (nowtv < sb || nowpv < sb) {
			int c = memo_prev[nowmonth][nowtv][nowpv];
			takecourse.add(c);
			nowmonth++;
			nowtv = Math.max(nowtv, tv[c]);
			nowpv = Math.max(nowpv, pv[c]);
		}
		int[] ret = new int[takecourse.size()];
		for (int i = 0 ; i < ret.length ; i++) {
			ret[i] = takecourse.get(i);
		}
		return ret;
	}
}

SRM 341 LandAndSea

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

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

  • 実装間に合わず。
import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class LandAndSea {
	int[][] map;
	int[][] maplevel;
	int[][] islid;
	int[][] islinfo = new int[1000][4];
	int[] levels;
	int idx = 1;
	boolean[][] graph;
	boolean[][] visited;
	
	int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
	int[] dy = {0, 1, 0, -1, -1, 1, -1, 1};
	
	public int dfs(int isl) {
		int r = 0; 
		for (int i = 1 ; i < idx ; i++) {
			if (graph[isl][i]) {
				r = Math.max(r, dfs(i) + 1);
			}
		}
		return r;
	}
	
	public void paint(int x, int y, int isl) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 4 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (tx <= -1 || ty <= -1 || tx >= visited[0].length || ty >= visited.length) {
					continue;
				}
				if (islid[ty][tx] != isl && !visited[ty][tx]) {
					visited[ty][tx] = true;
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}
	
	public void island(int x, int y) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		islid[y][x] = idx;
		islinfo[idx][0] = x;
		islinfo[idx][1] = y;
		islinfo[idx][2] = x;
		islinfo[idx][3] = y;
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 8 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (map[ty][tx] == 1 && islid[ty][tx] == 0) {
					islid[ty][tx] = idx;
					islinfo[idx][0] = Math.min(islinfo[idx][0], tx);
					islinfo[idx][1] = Math.min(islinfo[idx][1], ty);
					islinfo[idx][2] = Math.max(islinfo[idx][2], tx);
					islinfo[idx][3] = Math.max(islinfo[idx][3], ty);
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}

	
	public int[] howManyIslands(String[] seaMap) {
		int w = seaMap[0].length();
		int h = seaMap.length;
		map = new int[h+2][w+2];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (seaMap[i].charAt(j) == 'x') {
					map[i+1][j+1] = 1;
					System.out.print(1);
				} else {
					System.out.print(0);
				}
			}
			System.out.println();
		}
		
		levels = new int[501];
		maplevel = new int[h+2][w+2];
		islid = new int[h+2][w+2];
		idx = 1;
		for (int i = 1 ; i <= h ; i++) {
			for (int j = 1 ; j <= w ; j++) {
				if (map[i][j] == 1 && islid[i][j] == 0) {
					island(j, i);
					idx++;
				}
			}
		}
		
		graph = new boolean[idx][idx];
		for (int i = 1 ; i < idx ; i++) {
			visited = new boolean[h+2][w+2];
			paint(0, 0, i);
			for (int y = 0 ; y < h ; y++) {
				for (int x = 0 ; x < w ; x++) {
					int idx = (islid[y][x]);
					if (idx != i && idx >= 1 && !visited[y][x]) {
						graph[i][idx] = true;
					}
				}
			}
		}
		
		for (int i = 1 ; i < idx ; i++) {
			levels[dfs(i)]++;
		}
		int maxlevel = -1;
		for (int l = 0 ; l < 500 ; l++) {
			if (levels[l] >= 1) {
				maxlevel = l;
			}
		}
		int[] ans = new int[maxlevel+1];
		for (int l = 0 ; l <= maxlevel ; l++) {
			ans[l] = levels[l];
		}
		System.out.println(Arrays.toString(ans));
		return ans;
	}
}

2012-04-21SRM343, SRM344 (Practice)

SRM 344 QuantumAlchemy

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

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

  • 逆から考えていけばいいのではと思った
    • つまり、'X' だけの状態から反応を逆向きにして戻していく
  • 終了条件は、文字列が initial の subset になること。
  • TLEが不安だが他に思いつかないのでこのまま出してしまおう。

後で

  • wataさんのコード見た
    • 基本的な考え方は同じっぽい・・・
    • よく見ると、一度展開した文字は再度展開しないようにしてる
      • 無限に展開されるのを防ぐためか
    • また、状態を文字列そのものではなく残り必要な文字数で管理している
      • うまいなぁ

通ったコード

public class QuantumAlchemy {
	class Rea {
		String from;
		int flen;
		char to;
		Rea(String f, char t) {
			from = f;
			flen = from.length();
			to = t;
		}
		
		public String toString() {
			return from + ":" + to;
		}
	}

	int al;
	int[] iniset = new int[26];
	Rea[] reamap;
	boolean[] done = new boolean[512];
	
	public int dfs(char c) {
		if (reamap[c] == null) {
			return -1;
		}
		if (done[c]) {
			return -1;
		}
		int ret = 1;
		done[c] = true;
		for (char d : reamap[c].from.toCharArray()) {
			if (iniset[d] > 0) {
				iniset[d]--;
				al--;
				if (al < 0) {
					return -1;
				}
			} else {
				int tf = dfs(d);
				if (tf < 0) {
					return -1;
				}
				ret += tf;
			}
		}
		done[c] = false;
		return ret;
	}

	public int minSteps(String initial, String[] reactions) {
		int len = reactions.length;
		Rea[] r = new Rea[len];
		reamap = new Rea[512];
		for (int i = 0 ; i < len ; i++) {
			String[] data = reactions[i].split("->");
			
			char o = reactions[i].charAt(reactions[i].length()-1);
			r[i] = new Rea(data[0], o);
			reamap[o] = r[i];
		}
		
		al = initial.length();
		iniset = new int[512];
		for (int i = 0 ; i < al ; i++) {
			iniset[initial.charAt(i)]++;
		}
		if (iniset['X'] >= 1) {
			return 0;
		}
		
		return dfs('X');
	}
}

TLEするコード

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class QuantumAlchemy {
	class Rea {
		String from;
		int flen;
		char to;
		Rea(String f, char t) {
			from = f;
			flen = from.length();
			to = t;
		}
		
		public String toString() {
			return from + ":" + to;
		}
	}
	
	class State implements Comparable<State> {
		String now;
		int step;
		State(String n, int s) {
			char[] arr = n.toCharArray();
			Arrays.sort(arr);
			now = String.valueOf(arr);
			step = s;
		}
		public int compareTo(State arg0) {
			return step - arg0.step;
		}
	}

	public int minSteps(String initial, String[] reactions) {
		int len = reactions.length;
		Rea[] r = new Rea[len];
		Rea[] reamap = new Rea[512];
		for (int i = 0 ; i < len ; i++) {
			String[] data = reactions[i].split("->");
			
			char o = reactions[i].charAt(reactions[i].length()-1);
			r[i] = new Rea(data[0], o);
			reamap[o] = r[i];
		}
		
		int al = initial.length();
		Queue<State> q = new PriorityQueue<State>(10000000);
		int[] iniset = new int[26];
		for (int i = 0 ; i < al ; i++) {
			iniset[initial.charAt(i)-'A']++;
		}
		
		
		Map<String, Integer> dp = new HashMap<String, Integer>();
		q.add(new State("X", 0));
		dp.put("X", 0);
		
		while (q.size() >= 1) {
			State s = q.poll();
			int bl = s.now.length();
			
			int[] chcnt = new int[26];
			for (int i = 0 ; i < bl ; i++) {
				chcnt[s.now.charAt(i)-'A']++;
			}
			
			boolean isans = true;
			for (int c = 0 ; c < 26 ; c++) {
				if (chcnt[c] >= 1 && iniset[c] < chcnt[c]) {
					isans = false;
				}
			}
			if (isans) {
				return s.step;
			}
			
			for (int i = 0 ; i < bl ; i++) {
				char c = s.now.charAt(i);
				if (reamap[c] != null) {
					if (bl - 1 + reamap[c].flen > al) {
						continue;
					}
					
					StringBuffer tob = new StringBuffer();
					for (int j = 0 ; j < bl ; j++) {
						if (j == i) {
							tob.append(reamap[s.now.charAt(i)].from);
						} else {
							tob.append(s.now.charAt(j));
						}
					}

					String to = tob.toString();
					int ts = s.step + 1;
					if (!dp.containsKey(to)) {
						dp.put(to, ts);
						q.add(new State(to, ts));
					} else {
						int beststep = dp.get(to);
						if (beststep > ts) {
							dp.put(to, ts);
							q.add(new State(to, ts));
						}
					}
				}
			}
		}
		return -1;
	}
}

2012-04-02SRM353, SRM354 (Practice)

SRM 353 PlatformJumper

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

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

  • ある台からある台に飛び降り可能な時、元の台に戻ることはできないはず。
    • なので、状態として「今どこにいるか」だけ分かっていればよい
  • グラフにしてダイクストラ。
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PlatformJumper {
	class P {
		int x, y, c;
		P(int _x, int _y, int _c) {
			x = _x;
			y = _y;
			c = _c;
		}
	}
	
	class State {
		int now;
		int coin;
		State(int n, int c) {
			now = n;
			coin = c;
		}
	}
	
	public int maxCoins(String[] pl, int v, int g) {
		int len = pl.length;
		P[] p = new P[len];
		for (int i = 0 ; i < len ; i++) {
			String[] data = pl[i].split(" ");
			int x = Integer.valueOf(data[0]);
			int y = Integer.valueOf(data[1]);
			int c = Integer.valueOf(data[2]);
			p[i] = new P(x, y, c);
		}
		
		boolean[][] graph = new boolean[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				long dx = Math.abs(p[i].x - p[j].x);
				int dy = p[i].y - p[j].y;
				if (dy < 0) {
					continue;
				}
				if (dx * dx * g <= 2L * dy * v * v) {
					graph[i][j] = true;
				}
			}
		}
		
		int[] dp = new int[len];
		Queue<State> q = new PriorityQueue<State>(100000, new Comparator<State>(){
			public int compare(State arg0, State arg1) {
				return arg1.coin - arg0.coin;
			}
		});
		for (int i = 0 ; i < len ; i++) {
			q.add(new State(i, p[i].c));
			dp[i] = p[i].c;
		}
		while (q.size() >= 1) {
			State s = q.poll();
			for (int t = 0 ; t < len ; t++) {
				if (graph[s.now][t]) {
					int ton = t;
					int tocoin = s.coin + p[t].c;
					if (dp[ton] < tocoin) {
						dp[ton] = tocoin;
						q.add(new State(ton, tocoin));
					}
				}
			}
		}
		
		
		int ma = 0;
		for (int i = 0 ; i < len ; i++) {
			ma = Math.max(ma, dp[i]);
		}
		return ma;
	}
}

2012-04-01SRM355 (Practice)

SRM 355 MixingLiquids

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

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

  • 一度すべての溶液を混ぜる。
    • 濃度がぴったりだったら、合計をそのまま返す。
    • 濃度が薄すぎたら、一番薄いものから減らしていく。
    • 濃度が濃すぎたら、一番濃いものから減らしていく。
import java.util.Arrays;
import java.util.Comparator;

public class MixingLiquids {
	class Cup {
		int pcnt;
		int amnt;
		Cup(int p, int a) {
			pcnt = p;
			amnt = a;
		}
	}
	
	public double howMuch(int[] percent, int[] amount, int need) {
		int len = percent.length;
		Cup[] cup = new Cup[len];
		int ttl = 0;
		int cnt = 0;
		for (int i = 0 ; i < len ; i++) {
			ttl += amount[i];
			cnt += amount[i] * percent[i];
			cup[i] = new Cup(percent[i], amount[i]);
		}
		Arrays.sort(cup, new Comparator<Cup>(){
			public int compare(Cup a, Cup b) {
				return a.pcnt - b.pcnt;
			}
		});
		
		int from = 0;
		int to = len - 1;
		while (from <= to) {
			int newttl = ttl, newcnt = cnt;
			if (cnt == ttl * need) {
				return ttl;
			} else if (cnt < ttl * need) {
				newttl -= cup[from].amnt;
				newcnt -= cup[from].amnt * cup[from].pcnt;
				if (newttl * need < newcnt) {
					return ttl - (double)(cnt - ttl * need) / (cup[from].pcnt - need);
				} else {
					from++;
					ttl = newttl;
					cnt = newcnt;
				}
			} else {
				newttl -= cup[to].amnt;
				newcnt -= cup[to].amnt * cup[to].pcnt;
				if (newttl * need > newcnt) {
					return ttl - (double)(cnt - ttl * need) / (cup[to].pcnt - need);
				} else {
					to--;
					ttl = newttl;
					cnt = newcnt;
				}				
			}
		}
		return 0.0d;
	}
}

2012-03-29SRM357 (Practice)

SRM 357 WebsiteRank

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

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

  • めちゃくちゃ簡単なのに解けなかった、(自分に対して)訴訟
    • 素直に実装するだけ
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class WebsiteRank {

	boolean[][] graph, link;
	int len;
	
	public long countVotes(String[] votes, String website) {
		Map<String, Integer> namemap = new HashMap<String, Integer>();
		for (String v : votes) {
			String[] data = v.split(" ");
			int l = data.length;
			for (int i = 0 ; i < l ; i++) {
				if (!namemap.containsKey(data[i])) {
					namemap.put(data[i], namemap.size());
				}
			}
		}
		
		len = namemap.size();
		graph = new boolean[len][len];
		link = new boolean[len][len];
		for (String v : votes) {
			String[] data = v.split(" ");
			int l = data.length;
			int toid = namemap.get(data[0]);
			for (int i = 1 ; i < l ; i++) {
				int fromid = namemap.get(data[i]);
				graph[fromid][toid] = true;
				link[fromid][toid] = true;
			}
		}
		
		for (int k = 0 ; k < len ; k++) {
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < len ; j++) {
					if (graph[i][k] && graph[k][j]) {
						graph[i][j] = true;
					}
				}
			}
		}
		
		int[] indeg = new int[len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (link[i][j] && graph[j][i]) {
					link[i][j] = false;
				}
			}
		}

		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (link[i][j]) {
					indeg[j]++;
				}
			}
		}
		
		long[] val = new long[len];
		Arrays.fill(val, 1);
		
		while (true) {
			boolean done = false;
			for (int i = 0 ; i < len ; i++) {
				if (indeg[i] == 0) {
					for (int j = 0 ; j < len ; j++) {
						if (link[i][j]) {
							done = true;
							link[i][j] = false;
							indeg[j]--;
							val[j] += val[i];
						}
					}
				}
			}
			if (!done) {
				break;
			}
		}
		return val[namemap.get(website)];
	}
}