Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-30SRM356 (Practice)

SRM 356 AverageProblem

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

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

  • 頭の悪いDPをした
    • DPで解ける余地を残してくれるあたり優しい
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class AverageProblem {

	public int numberOfParticipants(String[] marks) {
		for (int i = 999 ; i >= 0 ; i--) {
			String zux = "0." + (String.valueOf(i) + "00000").substring(0, 3);
			System.out.print("\"" + zux + "\",");
		}
		System.out.println();
		
		Set<String> want = new HashSet<String>();
		for (String s : marks) {
			String[] data = s.split(" ");
			for (String n : data) {
				want.add(n);
			}
		}
		Map<String, Integer> smap = new HashMap<String, Integer>();
		for (String w : want) {
			smap.put(w, smap.size());
		}
		
		boolean[] dp = new boolean[10010];
		boolean[] dp_next = new boolean[10010];
		dp[0] = true;
		for (int p = 1 ; p <= 1000 ; p++) {
			for (int v = 0 ; v < 10010 ; v++) {
				if (dp[v]) {
					for (int a = 0 ; a <= 10 ; a++) {
						if (v+a < 10010) {
							dp_next[v+a] = true;
						}
					}
				}
			}
			for (int v = 0 ; v < 10010 ; v++) {
				dp[v] = dp_next[v];
				dp_next[v] = false;
			}

			boolean isok = true;
			for (String x : want) {
				int val = (int)(Double.valueOf(x) * p);
				boolean made = false;
				for (int d = 0 ; d <= 1 ; d++) {
					int intval = val + d;
					if (dp[intval]) {
						String dval = (intval * 1.0d / p) + "0000";
						if (intval == p * 10) {
							dval = dval.substring(0, 6);
						} else {
							dval = dval.substring(0, 5);
						}
						if (dval.equals(x)) {
							made = true;
							break;
						}
					}
				}
				if (!made) {
					isok = false;
					break;
				}
			}
			if (isok) {
				return p;
			}
		}
		return -1;
	}

}