Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-17SRM371, SRM372 (Practice)

SRM371 (Practice)

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

(比較的簡単と思われる)hardが解けなかった上easyに時間を食ったので終わってる

160/637位

問題結果ポイントその他
250SpiralRouteAccepted135.90数学、場合分け
500ChessMatchupAccepted478.99最小費用流
900RaceOrderingOpened0.00グラフ

SRM 371 SpiralRoute

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

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

  • min(width, length)の偶奇で場合分け。
public class SpiralRoute {
	public int[] thronePosition(int width, int length) {
		int mld2 = (Math.min(width, length) - 1) / 2;
		int x = mld2;
		int y = mld2;
		if (width == length) {
			if (width % 2 == 1) {
				return new int[]{x, y};
			} else {
				return new int[]{x, y+1};
			}
		} else {
			int mim = Math.min(width, length) % 2;
			if (mim % 2 == 1) {
				if (length > width) {
					y = length - mld2 - 1;
				} else {
					x = width - mld2 - 1;
				}
			} else {
				y++;					
			}
			
			return new int[]{x, y};
		}
	}
}

SRM 371 ChessMatchup

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

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

  • ソートしてGreedyで行ける気がするけど安全策をとって最小費用流で。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class ChessMatchup {

// 最小費用流ライブラリは省略

	public int maximumScore(int[] us, int[] them) {
		int len = us.length;
		init(len*2+2);
		int from = len*2;
		int to = len*2+1;
		for (int i = 0 ; i < len ; i++) {
			edge(from, i, 1, 0);
			edge(len+i, to, 1, 0);
		}
		
		int maxscore = 2 * len;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (us[i] > them[j]) {
					edge(i, len+j, 1, 0);
				} else if (us[i] < them[j]) {
					edge(i, len+j, 1, 2);
				} else {
					edge(i, len+j, 1, 1);
				}
			}
		}
		return maxscore - min_cost_flow(from, to, len);
	}
}

SRM 371 RaceOrdering

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

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

  • グラフで考えればいい気がする
    • 制約条件のある頂点をグループ分けして、そのグループの配置位置をnCrしようとした

後で

  • ↑の方針で解いた。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RaceOrdering {
	int MOD = 1000003;
	int n;
	boolean[][] graph;
	boolean[] done;
	long[][] memo;
	long[][] ncr;
	List<Integer> res;
	
	public void dfs(int i) {
		if (done[i]) {
			return;
		}
		done[i] = true;
		res.add(i);
		for (int j = 0 ; j < n ; j++) {
			if (graph[i][j] || graph[j][i]) {
				dfs(j);
			}
		}
	}
	
	public long count(int left) {
		int rlen = res.size();
		int[] idx = new int[rlen];
		for (int i = 0 ; i < rlen ; i++) {
			idx[i] = res.get(i);
		}
		
		long[] dp = new long[1<<rlen];
		dp[0] = 1;
		for (int ptn = 0 ; ptn < (1<<rlen) ; ptn++) {
			if (dp[ptn] == 0) {
				continue;
			}
			for (int next = 0 ; next < rlen ; next++) {
				if ((ptn & (1<<next)) >= 1) {
					continue;
				}
				int tidx = idx[next];
				int nptn = ptn | (1<<next);
				boolean isok = true;
				for (int prv = 0 ; prv < rlen ; prv++) {
					int fidx = idx[prv];
					if (graph[fidx][tidx] && (ptn & (1<<prv)) == 0) {
						isok = false;
						break;
					}
				}
				if (isok) {
					dp[nptn] += dp[ptn];
					dp[nptn] %= MOD;
				}
			}
		}
		return (dp[(1<<rlen)-1] * ncr[left][rlen]) % MOD;
	}
	
	
	public int countOrders(int _n, int[] first, int[] second) {
		n = _n;
		int len = first.length;
		ncr = new long[41][41];
		for (int i = 0 ; i < 41 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1]) % MOD;
			}
		}
		
		graph = new boolean[n][n];
		for (int i = 0 ; i < len ; i++) {
			graph[first[i]][second[i]] = true;
		}
		
		for (int k = 0 ; k < n ; k++) {
			for (int i = 0 ; i < n ; i++) {
				for (int j = 0 ; j < n ; j++) {
					if (graph[i][k] && graph[k][j]) {
						graph[i][j] = true;
					}
				}
			}
		}
		for (int i = 0 ; i < n ; i++) {
			if (graph[i][i]) {
				return 0;
			}
		}
		done = new boolean[n];
		long ans = 1;
		int left = n;
		for (int i = 0 ; i < n ; i++) {
			if (!done[i]) {
				res = new ArrayList<Integer>();
				dfs(i);
				ans *= count(left);
				ans %= MOD;
				left -= res.size();
			}
		}
		return (int)ans;
	}
}

SRM372 (Practice)

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

3完。全問簡単だった 19/589位

問題結果ポイントその他
250RoadConstructionAccepted167.04シミュレーション
500RoundOfElevenAccepted335.61DP
1000RadarGunsAccepted794.95最小費用流

SRM 372 RoadConstruction

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

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

  • 問題分の通りに愚直にシミュレーションする
    • それだけなのだが、20分もかかってしまった
import java.util.ArrayList;
import java.util.List;

public class RoadConstruction {
	class Car {
		int id;
		boolean yielded;
		boolean isd;
		Car(int i, char x) {
			id = i;
			yielded = false;
			isd = (x == 'D');
		}
	}
	
	public int getExitTime(String[] currentLanes) {
		int len = currentLanes.length;
		Car[] cars = new Car[2510];
		int caridx = 0;
		int[][] lanes = new int[52][52];
		int[] laneidx = new int[52];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < currentLanes[i].length() ; j++) {
				char c = currentLanes[i].charAt(j);
				cars[caridx] = new Car(caridx, c);
				lanes[i][j] = caridx;
				caridx++;
			}
			lanes[i][currentLanes[i].length()] = -1;
		}
		int turn = 0;
		while (true) {
			List<Integer> candidates = new ArrayList<Integer>();
			int willexit = -1;
			for (int i = 0 ; i < len ; i++) {
				int cid = lanes[i][laneidx[i]];
				if (cid >= 0) {
					if (cars[cid].yielded) {
						willexit = i;
						break;
					} else {
						candidates.add(i);
					}
				}
			}
			if (candidates.size() > 0) {
				if (willexit == -1) {
					willexit = candidates.get(candidates.size()-1);
					candidates.remove(candidates.size()-1);
				}
				for (int c : candidates) {
					cars[lanes[c][laneidx[c]]].yielded = true;
				}
			}
			if (willexit == -1) {
				break;
			} else {
				int exitid = lanes[willexit][laneidx[willexit]];
				if (cars[exitid].isd) {
					break;
				}
				laneidx[willexit]++;
			}
			turn++;
		}
		return turn;
	}
}

SRM 372 RoundOfEleven

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

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

  • どの桁をいくつ動かすか選択しながらDPする
    • k(0-indexed)桁目でx数字を増やすと、mod 11が (10^k*x) % 11 ずれる
    • あらかじめ (10^k) % 11 の値を求めておけば計算の手間が減らせそうだ
  • 状態は dp[桁数][残り使えるお金][mod11]
import java.util.Arrays;

public class RoundOfEleven {
	
	
	int len;
	String strn;
	long[][][] memo;
	int[] pow11;
	
	public long dfs(int digits, int leftmoney, int mod) {
		if (leftmoney < 0) {
			return 0;
		}
		if (digits == len) {
			if (mod == 0) {
				return leftmoney;
			}
			return 0;
		}
		if (memo[digits][leftmoney][mod] >= 0) {
			return memo[digits][leftmoney][mod];
		}
		
		
		long total = 0;
		int digit = strn.charAt(len-digits-1) - '0';
		for (int i = 0 ; i <= 9 ; i++) {
			int change = Math.abs(digit - i);
			int tomod = (mod + (pow11[digits] * (i - digit) + 1100)) % 11;
			total += dfs(digits+1, leftmoney-change, tomod);
		}
		memo[digits][leftmoney][mod] = total;
		
		return total;
	}

	public long maxIncome(int n, int money) {
		memo = new long[100][501][12];
		pow11 = new int[100];
		pow11[0] = 1;
		for (int i = 1 ; i < 100 ; i++) {
			pow11[i] = (pow11[i-1] * 10) % 11;
		}
		
		
		for (int i = 0 ; i < 100 ; i++) {
			for (int j = 0 ; j < 501 ; j++) {
				Arrays.fill(memo[i][j], -1);
			}
		}
		strn = String.valueOf(n);
		len = strn.length();
		
		return dfs(0, money, n % 11);
	}
}

SRM 372 RadarGuns

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

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

  • え、何これ
    • 罰金の最小値は最小費用流そのもの。
    • 得られる罰金の最大値は各辺のコストを(適当にでかい数 - 罰金)として、(適当にでかい数) * 車の数 - 最小費用流 とすればいい
  • ライブラリをはっつけゲーでした
    • 今のするめ環境ではこんな見え見えなのは出たりしないはず・・・
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class RadarGuns {

	public class State implements Comparable {
		int dist;
		int now;
		public State(int _n, int _d) {
			now = _n;
			dist = _d;
		}
		public int compareTo(Object arg0) {
			State a = (State) arg0;
			return dist - a.dist;
		}
	}
	public class Edge {
		int to;
		int cap;
		int rev;
		int cost;
		public Edge(int _to, int _cap, int _cost, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
			cost = _cost;
		}
	}
	public int INF = 10000000;
	public int V;
	public int[] h;
	public int[] dist;
	public int[] prevv, preve;
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		dist = new int[size];
		prevv = new int[size];
		preve = new int[size];
		h = new int[size];
		V = size;
		
	}
	public void edge(int from, int to, int cap, int cost) {
		graph.get(from).add(new Edge(to, cap, cost, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, -cost, graph.get(from).size() - 1));
	}
	public int min_cost_flow(int s, int t, int f) {
		int res = 0;
		Arrays.fill(h, 0);
		while (f > 0) {
			Queue<State> q = new PriorityQueue<State>(10000);
			Arrays.fill(dist, INF);
			dist[s] = 0;
			q.add(new State(s, 0));
			while (q.size() >= 1) {
				State stat = q.poll();
				int v = stat.now;
				if (dist[v] < stat.dist) {
					continue;
				}
				for (int i = 0 ; i < graph.get(v).size() ; i++) {
					Edge e = graph.get(v).get(i);
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						q.add(new State(e.to, dist[e.to]));
					}
				}
			}
			if (dist[t] == INF) {
				return -1;
			}
			for (int v = 0 ; v < V ; v++) {
				h[v] += dist[v];
			}
			int d = f;
			for (int v = t ; v != s ; v = prevv[v]) {
				d = Math.min(d, graph.get(prevv[v]).get(preve[v]).cap);
			}
			f -= d;
			res += d * h[t];
			for (int v = t ; v != s ; v = prevv[v]) {
				Edge e = graph.get(prevv[v]).get(preve[v]);
				e.cap -= d;
				graph.get(v).get(e.rev).cap += d;
			}
		}
		return res;
	}
	
	public int[] getRange(int[] enterTimes, int[] exitTimes, int speedTime, int fineCap) {
		int len = enterTimes.length;
		int[] ans = new int[2];
		for (int d = 0 ; d <= 1 ; d++) {
			init(len*2+2);
			int from = len*2;
			int to = len*2+1;
			for (int i = 0 ; i < len ; i++) {
				edge(from, i, 1, 0);
				edge(i+len, to, 1, 0);
			}
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < len ; j++) {
					int enter = enterTimes[i];
					int exit = exitTimes[j];
					int spd = exit - enter;
					if (spd >= 1) {
						int fine = 0;
						if (spd < speedTime) {
							fine = Math.min(fineCap, (speedTime - spd) * (speedTime - spd));
						}
						if (d == 1) {
							fine = 1000000 - fine;
						}
						edge(i, len+j, 1, fine);
					}
				}
			}
			ans[d] = min_cost_flow(from, to, len);
			if (d == 1) {
				ans[1] = 1000000 * len - ans[1];
			}
		}
		if (ans[0] == -1) {
			return new int[]{};
		}
		return ans;
	}
}