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

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