Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-02SRM353, SRM354 (Practice)

SRM353 (Practice)

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

問題結果ポイントその他
250GlossaryAccepted180.29実装
500PlatformJumperAccepted373.88グラフ
1000FurnitureRobberyOpened0.00???

SRM 353 Glossary

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

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

  • 問題文の通りに正しく実装する。
    • 文字列の比較はcase insensitiveなのに注意(サンプルにあって助かった)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Glossary {

	public String[] buildGlossary(String[] items) {
		List<String>[] list = new List[256];
		for (int i = 0 ; i < 256 ; i++) {
			list[i] = new ArrayList<String>();
		}
		int len = items.length;
		for (int i = 0 ; i < len ; i++) {
			String a = items[i];
			char c = a.charAt(0);
			if ('a' <= c && c <= 'z') {
				c = (char)('A' + (c - 'a'));
			}
			list[c].add(a);
		}
		for (int i = 'A' ; i <= 'Z' ; i++) {
			Collections.sort(list[i], new Comparator<String>(){
				public int compare(String a, String b) {
					return a.compareToIgnoreCase(b);
				}
			});
		}
		
		
		List<String> left = new ArrayList<String>();
		List<String> right = new ArrayList<String>();
		
		for (int i = 'A' ; i <= 'M' ; i++) {
			if (list[i].size() >= 1) {
				left.add((char)i + "                  ");
				left.add("-------------------");
				for (String l : list[i]) {
					int sz = l.length();
					String add = "  " + l;
					for (int j = sz ; j < 17 ; j++) {
						add += ' ';
					}
					left.add(add);
				}
			}
		}
		for (int i = 'N' ; i <= 'Z' ; i++) {
			if (list[i].size() >= 1) {
				right.add((char)i + "                  ");
				right.add("-------------------");
				for (String l : list[i]) {
					int sz = l.length();
					String add = "  " + l;
					for (int j = sz ; j < 17 ; j++) {
						add += ' ';
					}
					right.add(add);
				}
			}
		}		
		
		
		int size = Math.max(left.size(), right.size());
		if (left.size() < size) {
			for (int i = left.size() ; i < size ; i++) {
				left.add("                   ");
			}
		}
		if (right.size() < size) {
			for (int i = right.size() ; i < size ; i++) {
				right.add("                   ");
			}
		}
		
		String[] ret = new String[size];
		for (int i = 0 ; i < size ; i++) {
			ret[i] = left.get(i) + "  " + right.get(i);
		}
		return ret;
	}
}

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;
	}
}

SRM354 (Practice)

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

3つとも探索(DP)という珍しい回。

問題結果ポイントその他
300DateFormatAccepted172.73DP
500RemissiveSwapsAccepted452.96DP
900RooksPlacementOpened0.00DP

SRM 354 DateFormat

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

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

  • 日付を4桁の数にエンコーディング
  • DPと経路復元(めんどい)をするだけ。
    • 状態は [今考えてる日付の位置][直前の日付]
      • 状態数は 2500 * 1300 ≒ 50^4 / 2 としてまぁ大丈夫でしょう。
      • そもそも使わない日付もあるんだし。(1050とか)
  • 月ごとの最大日付のインデックス指定をミスってハマる
import java.util.ArrayList;
import java.util.List;

public class DateFormat {
	int[] a, r;
	int[][] next;
	int[] daymonth = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

	public int dfs(int i, int prev) {
		if (i == a.length) {
			return 1;
		}
		if (next[i][prev] != 0) {
			if (next[i][prev] >= 1) {
				return 1;
			} else {
				return -1;
			}
		}
		
		int first = Math.min(a[i], r[i]);
		int second = Math.max(a[i], r[i]);
		boolean fv = isvalid(first) && (first > prev);
		boolean sv = isvalid(second)&& (second > prev);
		if (fv) {
			if (dfs(i+1, first) == 1) {
				next[i][prev] = first;
				return 1;
			}
		}
		if (sv) {
			if (dfs(i+1, second) == 1) {
				next[i][prev] = second;
				return 1;
			}
		}
		
		next[i][prev] = -1;
		return -1;
	}
	
	public boolean isvalid(int dat) {
		int month = dat / 100;
		if (month <= 0 || month >= 13) {
			return false;
		}
		int day = dat % 100;
		
		if (1 <= day && day <= daymonth[month]) {
			return true;
		}
		return false;
	}
	
	public String fromEuropeanToUs(String[] dateList) {
		String d = "";
		for (String x : dateList) {
			d += x;
		}
		String[] dates = d.split(" ");
		
		int len = dates.length;
		a = new int[len];
		r = new int[len];
		for (int i = 0 ; i < len ; i++) {
			String[] date = dates[i].split("/");
			a[i] = Integer.valueOf(date[0]) * 100 + Integer.valueOf(date[1]);
			r[i] = Integer.valueOf(date[1]) * 100 + Integer.valueOf(date[0]);
		}
		next = new int[len+1][1300];
		
		if (dfs(0, 0) == -1) {
			return "";
		}
		
		List<String> list = new ArrayList<String>();
		int nowi = 0;
		int nowprev = 0;
		while (nowi < len) {
			int nextdata = next[nowi][nowprev];
			int nmonth = nextdata / 100;
			int nday = nextdata % 100;
			String month = (nmonth <= 9) ? ("0" + nmonth) : ("" + nmonth);
			String day = (nday <= 9) ? ("0" + nday) : ("" + nday);
			list.add(month + "/" + day);
			nowi++;
			nowprev = nextdata;
		}
		
		String ans = "";
		for (String l : list) {
			ans += " " + l;
		}
		return ans.substring(1);
	}
}

SRM 354 RemissiveSwaps

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

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

  • 素直にDPするだけ。
    • 3問の中で一番簡単かも
    • Math.pow(10, n)とかしてると定数倍に重く効いてくるので配列に持たせておくとよい
public class RemissiveSwaps {
	int[] memo = new int[1000001];
	int[] pidx = new int[]{1, 10, 100, 1000, 10000, 100000, 1000000};
	
	public int dfs(int now) {
		if (now == 0) {
			return 0;
		}
		if (memo[now] >= 1) {
			return memo[now];
		}
		
		int nn = now;
		int[] d = new int[7];
		int cnt = 0;
		for (int i = 0 ; i < 7 ; i++) {
			d[i] = nn % 10;
			nn /= 10;
			cnt++;
		}
		
		int max = now;
		for (int i = 0 ; i < cnt ; i++) {
			for (int j = i+1 ; j < cnt ; j++) {
				if (d[i] >= 1 && d[j] >= 1) {
					int tn = now;
					tn -= pidx[i] * d[i];
					tn -= pidx[j] * d[j];
					tn += pidx[i] * (d[j]-1);
					tn += pidx[j] * (d[i]-1);
					
					max = Math.max(max, dfs(tn));
				}
			}
		}
		
		memo[now] = max;
		return max;
	}
	
	
	public int findMaximum(int N) {
		if (N >= 1000000) {
			return 1000000;
		}
		return dfs(N);
	}
}

SRM 354 RooksPlacement

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

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

  • シンプルなDPのはずだがなかなか答えが合わず。
    • 考えてる状態数が足りないことに時間切れ直前になって気づいた
  • 通した。
    • 考察が足りなかった
public class RooksPlacement {
	long MOD = 1000001;
	int n, m, k;
	int K;
	long[][][] memo;
	long[][] ncr;
	
	public long ncr(int a, int b) {
		if (b > a) {
			return 0;
		}
		if (a <= 0) {
			return 0;
		}
		return ncr[a][b];
	}
	
	public long dfs(int now, int cv1, int cv2) {
		int left = k - cv1 - cv2; 
		if (now == n) {
			if (left == 0) {
				return 1;
			}
			return 0;
		} else if (now > n) {
			return 0;
		}
		if (memo[now][cv1][cv2] >= 0) {
			return memo[now][cv1][cv2];
		}
		if (left <= -1) {
			return 0;
		}

		long ret = 0;
		int free0 = m - cv1;
		
		// place two
		{
			long f02 = ncr(free0, 2);
			if (f02 >= 1) {
				ret += dfs(now+1, cv1+2, cv2) * f02;
				ret %= MOD;
			}
		}

		// place one
		{
			if (free0 >= 1) {
				ret += dfs(now+1, cv1+1, cv2) * free0;
				ret %= MOD;
			}
			
			long r2 = ncr(n - now - 1, 1);
			if (r2 >= 1 && free0 >= 1) {
				ret += dfs(now+2, cv1+1, cv2+1) * r2 * free0;
				ret %= MOD;
			}
		}
		
		// dont place
		ret += dfs(now+1, cv1, cv2);
		
		memo[now][cv1][cv2] = ret;
		return ret;
	}
	
	public int countPlacements(int N, int M, int K) {
		n = N;
		m = M;
		k = K;
		memo = new long[101][101][101];
		for (int i = 0 ; i < 101 ; i++) {
			for (int j = 0 ; j < 101 ; j++) {
				for (int k = 0 ; k < 101 ; k++) {
					memo[i][j][k] = -1;
				}
			}
		}
		ncr = new long[201][201];
		for (int i = 0 ; i < 201 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % MOD;
			}
		}
		
		return (int)(dfs(0, 0, 0) % MOD);
	}
}