Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

}