Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-10SRM346 (Practice)

SRM 346 HeightRound

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

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

  • 貪欲法。難しい
    • editorialや他の人のコードを見ながら書いた。
    • 要復習
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HeightRound {
	public int[] getBestRound(int[] h) {
		int len = h.length;
		Arrays.sort(h);
		int[] ret = new int[len];
		ret[0] = h[0];
		for (int d = 0 ; d <= 1000 ; d++) {
			boolean isok = true;
			List<Integer> hv = new ArrayList<Integer>();
			for (int i = 1 ; i < len ; i++) {
				hv.add(h[i]);
			}
			int q = h.length - 1;
			while (q > 0) {
				int idx = hv.size() - 1;
				int prev = (q + 1 == ret.length) ? ret[0] : ret[q+1];
				while (idx >= 0) {
					if (Math.abs(hv.get(idx) - prev) <= d) {
						break;
					}
					idx--;
				}
				if (idx < 0) {
					isok = false;
					break;
				}
				ret[q] = hv.remove(idx);
				q--;
			}
			if (Math.abs(ret[1] - ret[0]) > d) {
				continue;
			}
			if (isok) {
				return ret;
			}
		}
		return ret;
	}
}

2012-04-05SRM347 (Practice)

SRM 347 FlightScheduler

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

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

  • 問題文が正しく読めず、editorialを読むまで意味不明だった
  • 式変形して1回のフライトでR飛ぶときの必要燃料を求める。
    • n回に分けて飛行する場合の必要燃料を考えた時最適な回数を三分探索で探す。
public class FlightScheduler {
	int em;
	int k;
	
	public double ff(double r) {
		return 1.0d * em * (Math.pow(Math.E, (r / k)) - 1);
	}
	
	public double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel) {
		em = emptyMass;
		k = K;
		
		long tf = takeoffFuel;
		double req = Double.MAX_VALUE;
		
		long min = 1;
		long max = 1000000000L;
		for (int cur = 1 ; cur <= 10000 ; cur++) {
			long stp1 = (min * 2 + max) / 3;
			long stp2 = (min + max * 2) / 3;
			double d1 = 1.0d * distance / stp1;
			double d2 = 1.0d * distance / stp2;
			double fuel1 = tf * stp1 + ff(d1) * stp1;
			double fuel2 = tf * stp2 + ff(d2) * stp2;
			if (fuel1 > fuel2) {
				min = stp1;
			} else {
				max = stp2;
			}
		}
		
		for (long stp = min - 1000000 ; stp <= min + 1000000 ; stp++) {
			if (stp <= 0) {
				continue;
			}
			double d = 1.0d * distance / stp;
			double fuel1 = tf * stp + ff(d) * stp;
			req = Math.min(req, fuel1);
		}
		return req;
	}
}

2012-04-04SRM349 (Practice)

SRM 348 RailwayTickets

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

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

  • 蟻本第二版p220と同じ問題。
    • そのままやるとTLEするが、座標圧縮するとうまくいく。
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 RailwayTickets {
	// 最小費用流のコードは省略

	class P {
		int from, to;
		P(String data) {
			String[] ft = data.split("-");
			from = Integer.valueOf(ft[0]);
			to = Integer.valueOf(ft[1]);
		}
	}

	public int minRejects(String[] travel, int seats) {
		int len = travel.length;
		List<P> p = new ArrayList<P>();
		for (int i = 0 ; i < len ; i++) {
			String[] data = travel[i].split(" ");
			int dlen = data.length;
			for (int j = 0 ; j < dlen ; j++) {
				p.add(new P(data[j]));
			}
		}
		
		int max = 0;
		int[] tcnt = new int[10001];
		for (int i = 0 ; i < p.size() ; i++) {
			P pas = p.get(i);
			tcnt[pas.from]++;
			tcnt[pas.to]++;
		}
		
		int[] idmap = new int[10001];
		int idcnt = 1;
		for (int i = 1 ; i <= 10000 ; i++) {
			if (tcnt[i] >= 1) {
				idmap[i] = idcnt;
				idcnt++;
			}
		}
		
		int start = 0;
		int goal = 10001;
		init(10002);
		
		edge(start, 1, seats, 0);
		edge(idcnt-1, goal, seats, 0);
		for (int i = 1 ; i < idcnt ; i++) {
			edge(i, i+1, INF, 0);
		}
		
		for (int i = 0 ; i < p.size() ; i++) {
			int from = idmap[p.get(i).from];
			int to = idmap[p.get(i).to];
			edge(to, from, 1, 1);
			edge(start, to, 1, 0);
			edge(from, goal, 1, 0);
		}
		
		return min_cost_flow(start, goal, seats+p.size());
	}
}

SRM 349 DiceGames

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

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

  • ソートして数え上げるだけ
    • メモ化再帰を実装した
import java.util.Arrays;

public class DiceGames {
	
	int[] a;
	int len;
	
	long[][] memo;
	
	public long dfs(int i, int prev) {
		if (i == len) {
			return 1;
		}
		if (memo[i][prev] >= 0) {
			return memo[i][prev];
		}
		
		long ret = 0;
		for (int n = prev ; n <= a[i] ; n++) {
			ret += dfs(i+1, n);
		}
		memo[i][prev] = ret;
		return ret;
	}

	public long countFormations(int[] sides) {
		a = sides;
		len = sides.length;
		Arrays.sort(sides);
		
		memo = new long[50][50];
		for (int i = 0 ; i < 50 ; i++) {
			Arrays.fill(memo[i], -1);
		}
		return dfs(0, 1);
	}
}

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

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

2012-04-02SRM353, SRM354 (Practice)

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

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