Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-15SRM300台を練習していく part9

SRM 322 GroupWork

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

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

スキルが低い人は他の出来る人の足を引っ張ってしまう。あるあるな話。

解法はグループ内でのスキルの最小値を固定して、それぞれについて何人参加できるか調べるだけ。


public class GroupWork {

	public long bestGroup(int[] p, int[] s) {
		long max = 0;
		for (int i = 0 ; i < p.length ; i++) {
			long minv = s[i];
			long num = 0;
			for (int j = 0 ; j < p.length ; j++) {
				if (s[j] >= minv) {
					num += p[j];
				}
			}
			max = Math.max(max, minv * num);
		}
		return max;
	}
}

SRM 322 ExtendedDominoes

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

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

閉路を全部検出して、閉路のつながり方を全部調べようとして分けわかんなくなった。

editorialを見て解法を理解。自力では解けなかった。



public class ExtendedDominoes {
	public long countCycles(String[] pieces) {
		boolean[][] edges = new boolean[10][10];
		for (String line : pieces) {
			int a = line.charAt(0) - '0';
			int b = line.charAt(1) - '0';
			edges[a][b] = true;
			edges[b][a] = true;
		}
		
		long answer = 1L;
		for (int a = 0 ; a <= 9 ; a++) {
			int cnt = 0;
			for (int b = 0 ; b <= 9 ; b++) {
				if (edges[a][b]) {
					cnt++;
				}
			}
			if (cnt % 2 == 1) {
				return 0;
			}
			long rec = 1L;
			for (int i = 1 ; i <= cnt ; i += 2) {
				rec = rec * i;
			}
			answer *= rec;
		}
		return answer;
	}
}

SRM 325 FenceRepairing

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

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

DPするだけ。div1easyとだけあって簡単。

300だが恐るるに足らず。


public class FenceRepairing {

	public String _bd;
	public int _l;
	
	public double[] memo;
	
	
	public double dfs(int idx) {
		if (idx >= _l - 1) {
			return 0.0d;
		}
		if (idx >= 0) {
			if (memo[idx] >= 0.0d) {
				return memo[idx];
			}
		}
		
		double mincost = -1;
		int from = idx;
		for (int i = from + 1 ; i < _l ; i++) {
			if (_bd.charAt(i) == '.') {
				from++;
			} else {
				break;
			}
		}
		
		for (int i = idx + 1 ; i < _l ; i++) {
			if (_bd.charAt(i) == 'X') {
				double cost = Math.sqrt(i - from) + dfs(i);
				if (mincost < 0 || mincost > cost) {
					mincost = cost;
				}
			}
		}
		if (mincost < 0) {
			mincost = 0;
		}
		if (idx >= 0) {
			memo[idx] = mincost;
		}
		return mincost;
	}
	
	
	public double calculateCost(String[] boards) {
		String board = "";
		for (String b : boards) {
			board += b;
		}
		
		_l = board.length();
		_bd = board;
		memo = new double[5000];
		java.util.Arrays.fill(memo, -1.0d);
		
		int start = -1;
		for (; start < _l - 1 ; start++) {
			if (_bd.charAt(start+1) == 'X') {
				break;
			}
		}
		return dfs(start);
	}
}

SRM 324 PalindromeDecoding

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

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

問題文の通りに素直に実装するだけ。200でもいいんじゃないかと思った


public class PalindromeDecoding {

	public String decode(String code, int[] position, int[] length) {
		int len = position.length;
		for (int i = 0 ; i < len ; i++) {
			StringBuffer sub = new StringBuffer(code.substring(position[i], position[i] + length[i]));
			sub.reverse();
			String st = sub.toString();
			code = code.substring(0, position[i] + length[i]) + st + code.substring(position[i] + length[i], code.length());
		}
		return code;
	}
}

SRM 324 TournamentPlan

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

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

プレイヤーが2回以上移動するのは損なので、全てのプレイヤーが一堂に会する形にしたい。

はじめは最小全域木作るだけかなと思ったけど、それだとサンプルが通らない。

各プレイヤーの初期位置のXとYにそれぞれついて、

地点の候補として各プレイヤーからの距離を計算し、和を返すだけだった。


public class TournamentPlan {
	public int getTravelDistance(int[] street, int[] avenue) {
		int len = street.length;
		int dx = 999999999;
		int dy = 999999999;
		for (int i = 0 ; i < len ; i++) {
			int d = 0;
			for (int j = 0 ; j < len ; j++) {
				d += Math.abs(street[i] - street[j]);
			}
			dx = Math.min(dx, d);
		}
		for (int i = 0 ; i < len ; i++) {
			int d = 0;
			for (int j = 0 ; j < len ; j++) {
				d += Math.abs(avenue[i] - avenue[j]);
			}
			dy = Math.min(dy, d);
		}
		return dx + dy;
	}
}

SRM 323 RoadsAndFools

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

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

散々悩んだ挙句、普通にDPして何通りあるか数えることにした。

2通り以上か0通りだったら終わり。

1通りの場合、ある箇所が逆順になっていたら、どちらかを全長から引いて、を繰り返してsequenceを求める。


public class RoadsAndFools {
	int[] _f;
	int _l;
	int _ll;
	int _ans = 0;
	
	int[][] memo = new int[51][1002];
	
	public int dfs(int a, int now) {
		if (a >= _l - 1) {
			return 1;
		}
		if (memo[a][now] >= 1) {
			return memo[a][now];
		}

		int ret = 0;
		if (now < _f[a+1]) {
			ret += dfs(a+1, _f[a+1]);
		}
		if (now < _ll - _f[a+1] && _f[a+1] != _ll - _f[a+1]) {
			ret += dfs(a+1, _ll - _f[a+1]);
		}
		memo[a][now] = ret;
		
		return ret;
	}
	
	public String determineOrientation(int length, int[] frontSides) {
		int len = frontSides.length;
		_l = len;
		_f = frontSides;
		_ll = length;

		int a = dfs(0, _f[0]);
		if (_ll - _f[0] != _f[0]) {
			a += dfs(0, _ll - _f[0]);
		}
		
		if (a >= 2) {
			return "MULTIPLE SOLUTIONS";
		}
		if (a == 0) {
			return "NO SOLUTION";
		}
		
		String answer = "";
		for (int i = 0 ; i < len - 1 ; i++) {
			if (_f[i] >= _f[i+1]) {
				_f[i] = _ll - _f[i];
				if (_f[i] >= _f[i+1]) {
					_f[i] = _ll - _f[i];
					_f[i+1] = _ll - _f[i+1];
				}
			}
			answer = answer + _f[i] + " ";
		}
		answer += _f[len-1];
		
		return answer;
	}
}

SRM 321 WeirdSort

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

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

てきとーに書いたら通ってしまった。

辞書順最小だからdfsでよくね

⇒ {1, 1, 1, 1, …, 1, 2} なパターンだとTLEする

⇒ じゃあ同じ数字をまとめちゃおう(上の例だと、{1, 2} ⇒ {2, 1} ⇒ {2, 1, 1, ... , 1} とする)

⇒ {1, 1, 2, 2, 4, 4} みたいなパターンでWAする(正解は {1, 1, 4, 2, 2, 4} で、4が分離する形になる)

⇒ それじゃ同じ数字を1個とn-1個に分けてまとめよう

⇒ 通った


import java.util.ArrayList;
import java.util.List;

public class WeirdSort {

	int[] _ans;
	int len;
	
	public void dfs(int i, int prev, int[] now) throws Exception {
		if (i > 0) {
			_ans[i-1] = prev;
		}
		if (i == len) {
			throw new Exception();
		}
		for (int a = 0 ; a < len ; a++) {
			if (now[a] != -1 && now[a] != prev + 1) {
				int[] next = now.clone();
				next[a] = -1;
				dfs(i+1, now[a], next);
			}
		}
	}
	
	public int[] sortArray(int[] dat) {
		int[] cnt = new int[1001];
		List<Integer> nlist = new ArrayList<Integer>();
		for (int d : dat) {
			cnt[d]++;
			if (cnt[d] == 1) {
				nlist.add(d);
			}
			if (cnt[d] == 2) {
				nlist.add(d);
			}
		}
		len = nlist.size();
		int[] data = new int[len];
		for (int i = 0 ; i < len ; i++) {
			data[i] = nlist.get(i);
		}
		java.util.Arrays.sort(data);
		
		_ans = new int[len];
		try {
			dfs(0, -9999, data);
		} catch (Exception e) {
		}
		
		int[] ans = new int[dat.length];
		boolean[] hit = new boolean[1001];
		int ansidx = 0;
		for (int i = 0 ; i < len ; i++) {
			if (!hit[_ans[i]]) {
				hit[_ans[i]] = true;
				cnt[_ans[i]]--;
				ans[ansidx] = _ans[i];
				ansidx++;
			} else {
				for (int a = 0 ; a < cnt[_ans[i]] ; a++) {
					ans[ansidx] = _ans[i];
					ansidx++;
				}
			}
		}
		return ans;
	}
}