Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 336 LikelyWord

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

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

  • 辞書順でdictionaries[i]の前に来る、長さkの文字列を数え上げる。
    • 区間は引き算して求められる
      • この時、dictionaries[i]の文字数がkであった場合、あとで数えないようにフラグを立てておく
    • 最後の区間は 26^k から (dictionaries[len-1] の前に来る文字列数) を引いて求める
public class LikelyWord {
	public int likely(String[] dic, int k) {
		int len = dic.length;
		
		long[] pow26 = new long[11];
		pow26[0] = 1;
		for (int i = 1 ; i < 11 ; i++) {
			pow26[i] = pow26[i-1] * 26;
		}
		
		long total = pow26[k];
		long best = -1;
		int bestidx = -1;
		boolean sameflg = false;
		long prev = 0;
		long mflg = 0;
		System.out.println("total:" + total);
		for (int i = 0 ; i < len ; i++) {
			int sl = dic[i].length();
			long cnt = 0;
			for (int d = 0 ; d < Math.min(k, sl) ; d++) {
				int prevch = dic[i].charAt(d) - 'a';
				cnt += prevch * pow26[k-d-1];
			}
			if (sl > k) {
				cnt++;
			}
			long sc = cnt - prev - mflg;
			if (sl == k) {
				mflg = 1;
			} else {
				mflg = 0;
			}
			System.out.println(sc);
			if (best < sc) {
				best = sc;
				bestidx = i;
				sameflg = false;
			} else if (best == sc) {
				sameflg = true;
			}
			prev = cnt;
		}

		long last = total - prev - mflg;
		System.out.println(last);
		if (best < last) {
			return len;
		} else if (best == last) {
			sameflg = true;
		}
		return sameflg ? -1 : bestidx;
	}
}

SRM 337 BuildingAdvertise

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

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

  • 僕の苦手なデータ構造を利用するタイプの問題。
    • やり方がいろいろあるらしい(スタックを使ったり、分割統治法をしたり。)
    • 要復習

public class BuildingAdvertise {
	class Tower {
		int pos;
		long height;
		Tower(int p, long h) {
			pos = p;
			height = h;
		}
	}
	
	public long getMaxArea(int[] h, int n) {
		long[] r = new long[n+1];
		int j = 0;
		int m = h.length;
		for (int i = 0 ; i < n ; i++) {
			r[i] = h[j];
			int s = (j + 1) % m;
			h[j] = ((h[j] ^ h[s]) + 13) % 835454957;
			j = s;
		}
		r[n] = 0;
		n++;
		
		Tower[] towers = new Tower[n+1];
		int tidx = -1;
		long ans = 0;
		for (int i = 0 ; i < n ; i++) {
			if (tidx == -1 || towers[tidx].height < r[i]) {
				tidx++;
				towers[tidx] = new Tower(i, r[i]);
				continue;
			} else {
				if (towers[tidx].height == r[i]) {
					continue;
				}
				
				int pos = 0;
				while (tidx >= 0 && towers[tidx].height > r[i]) {
					long width = i - towers[tidx].pos;
					long S = width * towers[tidx].height;
					ans = Math.max(ans, S);
					
					pos = towers[tidx].pos;
					tidx--;
				}
				tidx++;
				towers[tidx] = new Tower(pos, r[i]);
			}
		}
		return ans;
	}
}

SRM 338 RandomSwaps

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

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

  • 確率
public class RandomSwaps {

	public double getProbability(int al, int swapCount, int a, int b) {
		long total = (al * (al-1) / 2);
		double base = 1.0d / total;
		
		double nottouch = 1.0d * ((al - 1) * (al - 2) / 2) / total;
		
		double ok = (a == b) ? 1.0d : 0.0d;
		double ng = 1.0d - ok;
		for (int i = 0 ; i < swapCount ; i++) {
			double nok = ng * base + ok * nottouch;
			double nng = 1.0d - nok;
			ok = nok;
			ng = nng;
		}
		return ok;
	}
}

2012-04-30SRM339 (Practice)

SRM 339 TestBettingStrategy

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

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

  • 簡単。
public class TestBettingStrategy {

	public double winProbability(int initSum, int goalSum, int rounds, int prob) {
		if (initSum >= goalSum) {
			return 1.0d;
		}
		
		int[] bets = new int[22];
		bets[0] = 1;
		for (int i = 1 ; i < 21 ; i++) {
			bets[i] = bets[i-1] * 2;
		}
		
		double p = prob * 1.0d / 100;
		double ans = 0.0d;
		double[][][] dp = new double[51][21][2002];
		dp[0][0][initSum] = 1.0d;
		for (int r = 0 ; r < rounds ; r++) {
			for (int l = 0 ; l < 21 ; l++) {
				for (int now = 0 ; now <= 2000 ; now++) {
					if (dp[r][l][now] > 0.0d) {
						double base = dp[r][l][now];
						int bet = bets[l];
						if (now < bet) {
							continue;
						}
						
						int win = (now - bet) + bet * 2;
						if (win >= goalSum) {
							win = 2001;
						}
						int lose = now - bet;
						
						if (win >= 2001) {
							ans += base * p;
						} else {
							dp[r+1][0][win] += base * p;
						}
						dp[r+1][Math.min(20, l+1)][lose] += base * (1.0d - p);
					}
				}
			}
		}
		return ans;
	}
}

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 340 CsCourses

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

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

  • 動的計画法+辞書順最小経路復元
    • 状態は [month][theoreticalValue][practicalValue]
    • 経路復元付きの場合はメモ化再帰すると楽。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CsCourses {
	int len;
	int[] tv;
	int[] pv;
	int[] exp;
	int bound;
	
	int[][][] memo = new int[51][51][51];
	int[][][] memo_prev = new int[51][51][51];

	
	public int dfs(int month, int ntv, int npv) {
		if (ntv >= bound && npv >= bound) {
			return 0;
		}
		if (memo[month][ntv][npv] >= 0) {
			return memo[month][ntv][npv];
		}
		
		int min = 100000;
		int mini = -1;
		for (int i = 0 ; i < len ; i++) {
			if ((ntv >= tv[i] && npv >= pv[i]) || (ntv < tv[i] - 1 || npv < pv[i] - 1)) {
				continue;
			}
			if (month >= exp[i]) {
				continue;
			}
			int ttv = Math.max(ntv, tv[i]);
			int tpv = Math.max(npv, pv[i]);
			int rec = dfs(month+1, ttv, tpv) + 1;
			if (min > rec) {
				min = rec;
				mini = i;
			}
		}
		memo[month][ntv][npv] = min;
		memo_prev[month][ntv][npv] = mini;
		
		return min;
	}
	
	public int[] getOrder(int[] t, int[] p, int[] expire, int sb) {
		bound = sb;
		tv = t;
		pv = p;
		exp = expire;
		len = tv.length;
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				Arrays.fill(memo[i][j], -1);
				Arrays.fill(memo_prev[i][j], -1);
			}
		}
		
		int num = dfs(0, 0, 0);
		if (num >= 1000) {
			return new int[]{};
		}
		
		int nowmonth = 0;
		int nowtv = 0;
		int nowpv = 0;
		List<Integer> takecourse = new ArrayList<Integer>();
		while (nowtv < sb || nowpv < sb) {
			int c = memo_prev[nowmonth][nowtv][nowpv];
			takecourse.add(c);
			nowmonth++;
			nowtv = Math.max(nowtv, tv[c]);
			nowpv = Math.max(nowpv, pv[c]);
		}
		int[] ret = new int[takecourse.size()];
		for (int i = 0 ; i < ret.length ; i++) {
			ret[i] = takecourse.get(i);
		}
		return ret;
	}
}

SRM 341 LandAndSea

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

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

  • 実装間に合わず。
import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class LandAndSea {
	int[][] map;
	int[][] maplevel;
	int[][] islid;
	int[][] islinfo = new int[1000][4];
	int[] levels;
	int idx = 1;
	boolean[][] graph;
	boolean[][] visited;
	
	int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
	int[] dy = {0, 1, 0, -1, -1, 1, -1, 1};
	
	public int dfs(int isl) {
		int r = 0; 
		for (int i = 1 ; i < idx ; i++) {
			if (graph[isl][i]) {
				r = Math.max(r, dfs(i) + 1);
			}
		}
		return r;
	}
	
	public void paint(int x, int y, int isl) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 4 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (tx <= -1 || ty <= -1 || tx >= visited[0].length || ty >= visited.length) {
					continue;
				}
				if (islid[ty][tx] != isl && !visited[ty][tx]) {
					visited[ty][tx] = true;
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}
	
	public void island(int x, int y) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		islid[y][x] = idx;
		islinfo[idx][0] = x;
		islinfo[idx][1] = y;
		islinfo[idx][2] = x;
		islinfo[idx][3] = y;
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 8 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (map[ty][tx] == 1 && islid[ty][tx] == 0) {
					islid[ty][tx] = idx;
					islinfo[idx][0] = Math.min(islinfo[idx][0], tx);
					islinfo[idx][1] = Math.min(islinfo[idx][1], ty);
					islinfo[idx][2] = Math.max(islinfo[idx][2], tx);
					islinfo[idx][3] = Math.max(islinfo[idx][3], ty);
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}

	
	public int[] howManyIslands(String[] seaMap) {
		int w = seaMap[0].length();
		int h = seaMap.length;
		map = new int[h+2][w+2];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (seaMap[i].charAt(j) == 'x') {
					map[i+1][j+1] = 1;
					System.out.print(1);
				} else {
					System.out.print(0);
				}
			}
			System.out.println();
		}
		
		levels = new int[501];
		maplevel = new int[h+2][w+2];
		islid = new int[h+2][w+2];
		idx = 1;
		for (int i = 1 ; i <= h ; i++) {
			for (int j = 1 ; j <= w ; j++) {
				if (map[i][j] == 1 && islid[i][j] == 0) {
					island(j, i);
					idx++;
				}
			}
		}
		
		graph = new boolean[idx][idx];
		for (int i = 1 ; i < idx ; i++) {
			visited = new boolean[h+2][w+2];
			paint(0, 0, i);
			for (int y = 0 ; y < h ; y++) {
				for (int x = 0 ; x < w ; x++) {
					int idx = (islid[y][x]);
					if (idx != i && idx >= 1 && !visited[y][x]) {
						graph[i][idx] = true;
					}
				}
			}
		}
		
		for (int i = 1 ; i < idx ; i++) {
			levels[dfs(i)]++;
		}
		int maxlevel = -1;
		for (int l = 0 ; l < 500 ; l++) {
			if (levels[l] >= 1) {
				maxlevel = l;
			}
		}
		int[] ans = new int[maxlevel+1];
		for (int l = 0 ; l <= maxlevel ; l++) {
			ans[l] = levels[l];
		}
		System.out.println(Arrays.toString(ans));
		return ans;
	}
}

SRM 342 ReverseResources

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

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

  • 動的計画法
    • 典型っぽいのでこのぐらいはサクッと解けるようになりたい
import java.util.Arrays;

public class ReverseResources {
	long MOD = 1000000007;
	
	String match;
	String[] parts;
	int len;
	
	long[][] dp;
	long[][][][] dp2;

	public long dfs(int from, int to, int i, int j) {
		long ptn = 0;
		if (from > to) {
			return 0;
		}
		if (dp2[from][to][i][j] >= 0) {
			return dp2[from][to][i][j];
		}

		boolean lf = (j == parts[i].length());
		boolean gf = (from == to);
		if (lf || gf) {
			if (lf && gf) {
				ptn = 1;
			} else {
				ptn = 0;
			}
			dp2[from][to][i][j] = ptn;
			return ptn;
		}
		
		if (parts[i].charAt(j) == '%') {
			for (int rep = from + 1 ; rep <= to ; rep++) {
				long after = dfs(rep, to, i, j+2) % MOD;
				if (after >= 1) {
					long a = ((dfs(from, rep) % MOD) * after) % MOD;
					ptn = (ptn + a) % MOD;
				}
			}
		} else if (parts[i].charAt(j) == match.charAt(from)){
			ptn = dfs(from+1, to, i, j+1);
		} else {
			ptn = 0;
		}
		
		dp2[from][to][i][j] = ptn;
		return ptn;
	}

	
	public long dfs(int from, int to) {
		if (from >= to) {
			return 1;
		}
		if (dp[from][to] >= 0) {
			return dp[from][to];
		}
		
		long ret = 0;
		for (int i = 0 ; i < len ; i++) {
			ret += dfs(from, to, i, 0);
			ret %= MOD;
		}
		dp[from][to] = ret;
		return ret;
	}
	
	
	public int findDecompositions(String str, String[] resources) {
		dp = new long[101][101];
		dp2 = new long[31][31][51][51];
		for (int i = 0 ; i < 101 ; i++) {
			Arrays.fill(dp[i], -1);
		}
		for (int i = 0 ; i < 31 ; i++) {
			for (int j = 0 ; j < 31 ; j++) {
				for (int k = 0 ; k < 51 ; k++) {
					Arrays.fill(dp2[i][j][k], -1);
				}
			}
		}
		
		match = str;
		parts = resources;
		len = resources.length;
		return (int)dfs(0, str.length());
	}
}

2012-04-21SRM343, SRM344 (Practice)

SRM 343 MoneyGame

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

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

  • ゲーム木実装するだけかな?
  • 書いたらサンプル通ったので出した
    • 愚直にやると計算量的に厳しいと思ったのでポットから取り出すコインの選択を貪欲法でやった
  • WA

その後

  • 愚直にやっても充分間に合った。
    • O(12^6) = 2Mちょい

import java.util.Arrays;

public class MoneyGame {
	int[] total;
	int[] values;
	int[][] dp;
	int[] idxmul = {1, 12, 144};
	
	public int dfs(int mine, int other) {
		if (dp[mine][other] != Integer.MAX_VALUE) {
			return dp[mine][other];
		}
		
		int[] coinm = new int[3];
		int[] coino = new int[3];
		int[] coinp = new int[3];
		int dmi = mine;
		int dot = other;
		for (int i = 0 ; i < 3 ; i++) {
			coinm[i] = dmi % 12;
			coino[i] = dot % 12;
			dmi /= 12;
			dot /= 12;
			coinp[i] = total[i] - (coinm[i] + coino[i]);
		}
		
		int result = 0;
		if (mine == 0) {
			for (int i = 0 ; i < 3 ; i++) {
				result -= coino[i] * values[i];
			}
			dp[mine][other] = result;
			return result;
		}

		int bresult = Integer.MAX_VALUE;
		for (int p = 0 ; p < 3 ; p++) {
			if (coinm[p] >= 1) {
				int nexto = mine - idxmul[p];
				int nextm = other;
				int left = values[p];
				for (int a = 0 ; a <= coinp[0] ; a++) {
					for (int b = 0 ; b <= coinp[1] ; b++) {
						for (int c = 0 ; c <= coinp[2] ; c++) {
							int val = values[0] * a + values[1] * b + values[2] * c;
							if (val < left) {
								int nextother = nexto;
								nextother += idxmul[0] * a + idxmul[1] * b + idxmul[2] * c;
								bresult = Math.min(bresult, dfs(nextm, nextother));  
							}
						}
					}
				}
			}
		}
		bresult *= -1;
		dp[mine][other] = bresult;

		return bresult;
	}
	
	
	class Coin implements Comparable<Coin> {
		int l;
		int f;
		int v;
		Coin(int _l, int _f, int _v) {
			l = _l;
			f = _f;
			v = _v;
		}
		public int compareTo(Coin arg0) {
			return v - arg0.v;
		}
	}
	
	public int play(int[] lc, int[] fc, int[] v) {
		dp = new int[2000][2000];
		for (int i = 0 ; i < 2000 ; i++) {
			Arrays.fill(dp[i], Integer.MAX_VALUE);
		}
		Coin[] c = new Coin[3];
		for (int i = 0 ; i < 3 ; i++) {
			c[i] = new Coin(lc[i], fc[i], v[i]);
		}
		Arrays.sort(c);
		for (int i = 0 ; i < 3 ; i++) {
			lc[i] = c[i].l;
			fc[i] = c[i].f;
			v[i] = c[i].v;
		}
		values = v.clone();
		total = new int[3];
		for (int i = 0 ; i < 3 ; i++) {
			total[i] = lc[i] + fc[i];
		}
		
		int a = 0;
		int b = 0;
		for (int i = 0 ; i < 3 ; i++) {
			a += idxmul[i] * lc[i];
			b += idxmul[i] * fc[i];
		}
		return dfs(a, b);
	}

}

SRM 344 QuantumAlchemy

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

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

  • 逆から考えていけばいいのではと思った
    • つまり、'X' だけの状態から反応を逆向きにして戻していく
  • 終了条件は、文字列が initial の subset になること。
  • TLEが不安だが他に思いつかないのでこのまま出してしまおう。

後で

  • wataさんのコード見た
    • 基本的な考え方は同じっぽい・・・
    • よく見ると、一度展開した文字は再度展開しないようにしてる
      • 無限に展開されるのを防ぐためか
    • また、状態を文字列そのものではなく残り必要な文字数で管理している
      • うまいなぁ

通ったコード

public class QuantumAlchemy {
	class Rea {
		String from;
		int flen;
		char to;
		Rea(String f, char t) {
			from = f;
			flen = from.length();
			to = t;
		}
		
		public String toString() {
			return from + ":" + to;
		}
	}

	int al;
	int[] iniset = new int[26];
	Rea[] reamap;
	boolean[] done = new boolean[512];
	
	public int dfs(char c) {
		if (reamap[c] == null) {
			return -1;
		}
		if (done[c]) {
			return -1;
		}
		int ret = 1;
		done[c] = true;
		for (char d : reamap[c].from.toCharArray()) {
			if (iniset[d] > 0) {
				iniset[d]--;
				al--;
				if (al < 0) {
					return -1;
				}
			} else {
				int tf = dfs(d);
				if (tf < 0) {
					return -1;
				}
				ret += tf;
			}
		}
		done[c] = false;
		return ret;
	}

	public int minSteps(String initial, String[] reactions) {
		int len = reactions.length;
		Rea[] r = new Rea[len];
		reamap = new Rea[512];
		for (int i = 0 ; i < len ; i++) {
			String[] data = reactions[i].split("->");
			
			char o = reactions[i].charAt(reactions[i].length()-1);
			r[i] = new Rea(data[0], o);
			reamap[o] = r[i];
		}
		
		al = initial.length();
		iniset = new int[512];
		for (int i = 0 ; i < al ; i++) {
			iniset[initial.charAt(i)]++;
		}
		if (iniset['X'] >= 1) {
			return 0;
		}
		
		return dfs('X');
	}
}

TLEするコード

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class QuantumAlchemy {
	class Rea {
		String from;
		int flen;
		char to;
		Rea(String f, char t) {
			from = f;
			flen = from.length();
			to = t;
		}
		
		public String toString() {
			return from + ":" + to;
		}
	}
	
	class State implements Comparable<State> {
		String now;
		int step;
		State(String n, int s) {
			char[] arr = n.toCharArray();
			Arrays.sort(arr);
			now = String.valueOf(arr);
			step = s;
		}
		public int compareTo(State arg0) {
			return step - arg0.step;
		}
	}

	public int minSteps(String initial, String[] reactions) {
		int len = reactions.length;
		Rea[] r = new Rea[len];
		Rea[] reamap = new Rea[512];
		for (int i = 0 ; i < len ; i++) {
			String[] data = reactions[i].split("->");
			
			char o = reactions[i].charAt(reactions[i].length()-1);
			r[i] = new Rea(data[0], o);
			reamap[o] = r[i];
		}
		
		int al = initial.length();
		Queue<State> q = new PriorityQueue<State>(10000000);
		int[] iniset = new int[26];
		for (int i = 0 ; i < al ; i++) {
			iniset[initial.charAt(i)-'A']++;
		}
		
		
		Map<String, Integer> dp = new HashMap<String, Integer>();
		q.add(new State("X", 0));
		dp.put("X", 0);
		
		while (q.size() >= 1) {
			State s = q.poll();
			int bl = s.now.length();
			
			int[] chcnt = new int[26];
			for (int i = 0 ; i < bl ; i++) {
				chcnt[s.now.charAt(i)-'A']++;
			}
			
			boolean isans = true;
			for (int c = 0 ; c < 26 ; c++) {
				if (chcnt[c] >= 1 && iniset[c] < chcnt[c]) {
					isans = false;
				}
			}
			if (isans) {
				return s.step;
			}
			
			for (int i = 0 ; i < bl ; i++) {
				char c = s.now.charAt(i);
				if (reamap[c] != null) {
					if (bl - 1 + reamap[c].flen > al) {
						continue;
					}
					
					StringBuffer tob = new StringBuffer();
					for (int j = 0 ; j < bl ; j++) {
						if (j == i) {
							tob.append(reamap[s.now.charAt(i)].from);
						} else {
							tob.append(s.now.charAt(j));
						}
					}

					String to = tob.toString();
					int ts = s.step + 1;
					if (!dp.containsKey(to)) {
						dp.put(to, ts);
						q.add(new State(to, ts));
					} else {
						int beststep = dp.get(to);
						if (beststep > ts) {
							dp.put(to, ts);
							q.add(new State(to, ts));
						}
					}
				}
			}
		}
		return -1;
	}
}

2012-04-20SRM345 (Practice)

SRM 345 StoneGame

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

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

  • 手で実験してみる
    • これ、総取りできるか、全部相手に取られるかのどちらかなのでは
      • 石の総数の偶奇で決まる気がする(奇数なら総取りできる)
  • でも、石の数が1の場合はまずそちらを取った方がいい
    • 複数ある場合は当然価値が高いものを取った方がいい
    • 相手も当然価値が高いものを優先して取るはず
  • 石の数が1の山をすべて取り終えたときゲームが始まる
  • 書いたらサンプル合った。
    • 証明はできないが正しい気がするのでそのまま出した
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class StoneGame {

	public int getScore(int[] treasure, int[] stones) {
		int len = stones.length;
		List<Integer> cango = new ArrayList<Integer>();
		
		int etotal = 0;
		int etreas = 0;
		for (int i = 0 ; i < len ; i++) {
			if (stones[i] == 1) {
				cango.add(treasure[i]);
			} else {
				etotal += stones[i];
				etreas += treasure[i];
			}
		}
		Collections.sort(cango);
		Collections.reverse(cango);
		
		int canget = 0;
		int cl = cango.size();
		for (int i = 0 ; i < cl ; i += 2) {
			canget += cango.get(i);
		}
		if (cl == len) {
			return canget;
		}
		
		if (cl % 2 == 1) {
			etotal -= 1;
		}
		if (etotal % 2 == 1) {
			canget += etreas;
		}
		return canget;
	}
}