Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM350 (Practice)

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

問題結果ポイントその他
250SumsOfPerfectPowersAccepted215.74列挙して探索
500StarsInGraphsWA0.00グラフ
1000PlaneDivisionOpened0.00幾何

SRM 350 SumsOfPerfectPowers

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

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

  • 求めるべき数の中で、m >= 2 で a^m となってる数はそんなに多くない。
    • なので、全て列挙し、2つの数の組み合わせを全部試せる。
import java.util.HashSet;
import java.util.Set;

public class SumsOfPerfectPowers {
	int MAX = 8000000;
	
	public int howMany(int lowerBound, int upperBound) {
		boolean[] done = new boolean[MAX];
		Set<Integer> l = new HashSet<Integer>();
		
		for (int a = 0 ; a <= 10000 ; a++) {
			long aa = a;
			for (int m = 2 ; m <= 100 ; m++) {
				aa *= a;
				if (aa >= MAX || aa <= -1) {
					break;
				}
				l.add((int)aa);
			}
		}

		int cnt = 0;
		boolean[] met = new boolean[MAX];
		for (int a : l) {
			for (int b : l) {
				int ab = a + b;
				if (lowerBound <= ab && ab <= upperBound) {
					if (!met[ab]) {
						met[ab] = true;
						cnt++;
					}
				}
			}
		}
		return cnt;
	}
}

SRM 350 StarsInGraphs

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

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

  • まず、全頂点のstar numberを求める。
  • 「今どこにいるか」を状態としたダイクストラをする
    • 経由頂点数が100を超えるようだったらループしてるので、-1を返す。
  • 練習ではDPの更新部分でバグっててWAした。
import java.math.BigInteger;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class StarsInGraphs {
	class State {
		int now;
		int prev;
		int cnt;
		State(int n, int p, int c) {
			now = n;
			prev = p;
			cnt = c;
		}
	}
	
	int len;
	boolean[][] graph;
	boolean[] done;
	long[] star;
	
	public int starryPaths(String[] adj, int C) {
		len = adj.length;
		graph = new boolean[len][len];
		int[] deg = new int[len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				graph[i][j] = (adj[i].charAt(j) == '1');
				if (graph[i][j]) {
					deg[i]++;
				}
			}
		}
		
		
		long[][] ncr = new long[51][51];
		for (int i = 0 ; i < 51 ; 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];
			}
		}
		
		
		star = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			long s = 0;
			for (int d = 3 ; d <= deg[i] ; d++) {
				s += ncr[deg[i]][d];
				if (s <= -1) {
					s = -1;
					break;
				} else if (s > C) {
					s = -1;
					break;
				}
			}
			if (1 <= s && s <= C) {
				star[i] = s;
			} else {
				star[i] = -1;
			}
		}
		
		Queue<State> q = new PriorityQueue<State>(10000, new Comparator<State>(){
			public int compare(State o1, State o2) {
				return o2.cnt - o1.cnt;
			}
		});
		int[] dp = new int[len];
		for (int i = 0 ; i < len ; i++) {
			if (star[i] >= 1) {
				dp[i] = 1;
				q.add(new State(i, i, 1));
			}
		}
		
		int max = 0;
		while (q.size() >= 1) {
			State s = q.poll();
			max = Math.max(max, s.cnt);
			for (int i = 0 ; i < len ; i++) {
				if (i != s.prev && graph[s.now][i] && star[i] >= star[s.now]) {
					if (dp[i] < s.cnt + 1) {
						dp[i] = s.cnt + 1;
						if (dp[s.now] >= 100) {
							return -1;
						}
						q.add(new State(i, i, s.cnt + 1));
					}
				}
			}
		}
		return max;
	}
}

SRM 350 PlaneDivision

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

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

  • 幾何。典型問題っぽい?
  • あとでやろう。

SRM351 (Practice)

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

問題結果ポイントその他
250CoinsExchangeAccepted185.39貪欲法
500BoxesArrangementAccepted317.47DP
1000NewMagicSquareUnopened0.00最大流

SRM 351 CoinsExchange

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

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

  • 貪欲法
    • 足りないGold、Silver、Bronzeの順に両替を行いながら埋め合わせる
  • 通ったのがいいがきれいな実装ができなかったので後で確認する。
public class CoinsExchange {
	public int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2) {
		int req = 0;
		if (G2 > G1) {
			int gneed = G2 - G1;
			if (S1 >= 11 * gneed) {
				req += gneed;
				S1 -= 11 * gneed;
			} else {
				int sneed = 11 * gneed - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					req += gneed;
					B1 -= 11 * sneed;
					S1 += sneed;
					S1 -= 11 * gneed;
				} else {
					return -1;
				}
			}
		}
		
		if (S2 > S1) {
			int sneed = S2 - S1;
			if (G1 - G2 > 0) {
				int lgold = G1 - G2;
				int needgold = (sneed + 8) / 9;
				if (lgold >= needgold) {
					req += needgold;
					G1 -= needgold;
					S1 += needgold * 9;
				} else {
					req += lgold;
					G1 = G2;
					S1 += lgold * 9;
				}
			}
			if (S2 > S1) {
				sneed = S2 - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					B1 -= 11 * sneed;
					S1 += sneed;
				} else {
					return -1;
				}
			}
		}
		
		
		if (B2 > B1) {
			int needbronze = B2 - B1;
			int reqsilver = (needbronze + 8) / 9;
			req += reqsilver;
			if (S1 - S2 >= reqsilver) {
			} else {
				reqsilver -= (S1 - S2); 
				int reqgold = (reqsilver + 8) / 9;
				if (G1 - G2 >= reqgold) {
					req += reqgold;
				} else {
					return -1;
				}
			}
		}	
		return req;
	}
}

SRM 351 BoxesArrangement

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

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

  • 要は、A,B,Cをルールに則り並び替えた時元の位置と一致する最大数が分かればいい
    • 普通に数を並べるDPで書ける。
    • [Aを使った数][Bを使った数][Cを使った数][直前の文字][直前の文字が何個連続したか]
      • 多めに見積もって 51*51*51*4*4 = 2M程度。
  • 練習ではメモ化再帰で書こうとした
    • (文字数) >= 30 程度になると間に合わなくなったのでループDPに書き換え。
atement

SRM 351 NewMagicSquare

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

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

  • 見てない

後で

  • やってみた
    • これただの最大流だ
  • 辞書順最小に数字を当てはめながら最大流するだけ。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NewMagicSquare {
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}
	
	public boolean isok(int[][] tbl, boolean[] used) {
		init(52);
		for (int n = 0 ; n < 25 ; n++) {
			edge(50, n, 1);
			edge(25+n, 51, 1);
		}
		
		for (int r = 0 ; r < 5 ; r++) {
			for (int c = 0 ; c < 4 ; c++) {
				if (tbl[r][c] >= 0 && tbl[r][c+1] >= 0) {
					if (tbl[r][c] > tbl[r][c+1]) {
						return false;
					}
				}
			}
		}
		
		for (int r = 0 ; r < 5 ; r++) {
			for (int c = 0 ; c < 5 ; c++) {
				int pos = r * 5 + c;
				if (tbl[r][c] == -1) {
				} else {
					edge(tbl[r][c], 25+pos, 1);
				}
			}
		}
		
		for (int n = 0 ; n < 25 ; n++) {
			if (used[n]) {
				continue;
			}
			for (int r = 0 ; r < 5 ; r++) {
				for (int c = 0 ; c < 5 ; c++) {
					boolean isok = true;
					for (int b = 0 ; b < c ; b++) {
						if (tbl[r][b] >= 0 && tbl[r][b] > n) {
							isok = false;
							break;
						}
					}
					for (int b = c+1 ; b < 5 ; b++) {
						if (tbl[r][b] >= 0 && tbl[r][b] < n) {
							isok = false;
							break;
						}
					}
					if (isok) {
						edge(n, 25+r*5+c, 1);
					}
				}
			}
		}
		
		
		return (max_flow(50, 51) == 25);
	}
	
	public String[] completeTheSquare(String[] square) {
		int[][] tbl = new int[5][5];
		
		boolean[] used = new boolean[25];
		for (int i = 0 ; i < 5 ; i++) {
			String[] d = square[i].split(" ");
			for (int j = 0 ; j < 5 ; j++) {
				if ("??".equals(d[j])) {
					tbl[i][j] = -1;
				} else {
					tbl[i][j] = Integer.valueOf(d[j]) - 1;
					used[tbl[i][j]] = true;
				}
			}
		}
		
		for (int r = 0 ; r < 5 ; r++) {
			for (int c = 0 ; c < 5 ; c++) {
				if (tbl[r][c] == -1) {
					boolean isok = false;
					for (int n = 0 ; n < 25 ; n++) {
						if (used[n]) {
							continue;
						}
						tbl[r][c] = n;
						used[n] = true;
						if (isok(tbl, used)) {
							isok = true;
							break;
						}
						used[n] = false;
					}
					if (!isok) {
						return new String[]{};
					}
				}
			}
		}
		
		String[] ret = new String[5];
		for (int r = 0 ; r < 5 ; r++) {
			ret[r] = to2str(tbl[r][0]+1);
			for (int c = 1 ; c < 5 ; c++) {
				ret[r] += " " + to2str(tbl[r][c]+1);
			}
		}
		return ret;
	}

	public String to2str(int i) {
		if (i >= 10) {
			return String.valueOf(i);
		} else {
			return "0" + String.valueOf(i);
		}
	}
}

SRM352 (Practice)

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

問題結果ポイントその他
250NumberofFiboCallsRE0.00DP
500FibonacciKnapsackOpened0.00DP、枝刈り
1000PaperRacingUnopened0.00見てない

SRM 352 NumberofFiboCalls

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

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

  • やるだけ
    • 練習では配列のサイズ指定ミスでREをくらう
public class NumberofFiboCalls {
	public int[] fiboCallsMade(int n) {
		int[][] ret = new int[41][2];
		ret[0][0] = 1;
		ret[0][1] = 0;
		ret[1][0] = 0;
		ret[1][1] = 1;
		
		for (int k = 2 ; k <= n ; k++) {
			ret[k][0] = ret[k-1][0] + ret[k-2][0];
			ret[k][1] = ret[k-1][1] + ret[k-2][1];
		}
		return ret[n];
	}
}

SRM 352 FibonacciKnapsack

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

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

  • メモ化再帰。
    • 枝刈りを仕込むとうまくいく。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FibonacciKnapsack {

	class Item implements Comparable<Item> {
		long w;
		long v;
		Item(long _w, long _v) {
			w = _w;
			v = _v;
		}
		public int compareTo(Item arg0) {
			if (w == arg0.w) {
				return Long.signum(arg0.v - v);
			}
			return Long.signum(arg0.w - w);
		}
	}
	
	Item[] it;
	long[] sumw;
	long[] sumv;
	
	Map<Long, Long> m[];
	
	public long dfs(int i, long now) {
		if (i >= it.length) {
			return 0;
		}
		if (m[i].containsKey(now)) {
			return m[i].get(now);
		}
		
		long ret = 0;
		if (now >= sumw[i]) {
			ret = sumv[i];
		} else {
			ret = Math.max(ret, dfs(i+1, now));
			if (now >= it[i].w) {
				ret = Math.max(ret, dfs(i+1, now - it[i].w) + it[i].v);
			}
		}
		
		m[i].put(now, ret);
		return ret;
	}
	
	public long maximalCost(String[] items, String C) {
		int len = items.length;
		it = new Item[len];
		for (int i = 0 ; i < len ; i++) {
			String[] data = items[i].split(" ");
			long a = Long.valueOf(data[0]);
			long b = Long.valueOf(data[1]);
			it[i] = new Item(a, b);
		}
		Arrays.sort(it);
		
		sumw = new long[len+1];
		sumv = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			long v = 0;
			long w = 0;
			for (int j = i ; j < len ; j++) {
				w += it[j].w;
				v += it[j].v;
			}
			sumw[i] = w;
			sumv[i] = v;
		}
		
		m = new Map[len];
		for (int i = 0 ; i < len ; i++) {
			m[i] = new HashMap<Long, Long>();
		}

		return dfs(0, Long.valueOf(C));
	}
}