Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-21SRM343, SRM344 (Practice)

SRM343 (Practice)

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

問題結果ポイントその他
250CDPlayerAccepted228.59実装
500MoneyGameWA0.00ゲーム
1000RefactorableNumberAccepted860.09実装

SRM 343 CDPlayer

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

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

  • 実装するだけ。
public class CDPlayer {

	public int isRandom(String[] songlist, int n) {
		String list = "";
		for (String s : songlist) {
			list += s;
		}
		int len = list.length();
		
		for (int i = 0 ; i < n ; i++) {
			boolean isok = true;
			int[] pcnts = new int[512];
			for (int p = 0 ; p < i ; p++) {
				if (++pcnts[list.charAt(p)] >= 2) {
					isok = false;
					break;
				}
			}
			if (!isok) {
				continue;
			}
			
			int idx = i;
			while (idx < len && isok) {
				int[] cnts = new int[512];
				for (int j = idx ; j < Math.min(len, idx + n) ; j++) {
					if (++cnts[list.charAt(j)] >= 2) {
						isok = false;
						break;
					}
				}
				idx += n;
			}
			if (isok) {
				return i;
			}
		}
		return -1;
	}
}

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 343 RefactorableNumber

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

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

  • これ(難易度的に)250だろ・・・
  • 当時の本番後どんな反応だったかは想像に難くない
public class RefactorableNumber {
	public int count(int low, int high) {
		int[] factors = new int[2000010];
		for (int i = 1 ; i < 2000010 ; i++) {
			for (int j = i ; j < 2000010 ; j += i) {
				factors[j]++;
			}
		}
		int cnt = 0;
		for (int l = low ; l <= high ; l++) {
			if (l % factors[l] == 0) {
				cnt++;
			}
		}
		return cnt;
	}
}

SRM344 (Practice)

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

問題結果ポイントその他
250VolleyballTournamentAccepted192.23全探索
500QuantumAlchemyTLE0.00探索
1000FairTournamentOpened0.00動的計画法

SRM 344 VolleyballTournament

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

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

  • 0点、1点、2点を取った試合数を全探索する。
    • 組み合わせが複数あれば AMBIGUITY を返す
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class VolleyballTournament {

	static final String AMB = "AMBIGUITY";
	
	public String reconstructResults(int wm, int lm, int ws, int ls) {
		ws -= wm * 3;
		ls -= lm * 3;
		int[] mat = {wm, lm};
		int[] set = {ls, ws};
		List<String> rs = new ArrayList<String>();
		for (int x = 0 ; x <= 1 ; x++) {
			int match = mat[x];
			int sets = set[x];
			int[] zot = new int[3];
			
			int rec = 0;
			for (int zero = 0 ; zero <= match ; zero++) {
				for (int one = 0 ; one <= match ; one++) {
					for (int two = 0 ; two <= match ; two++) {
						if (zero + one + two != match) {
							continue;
						}
						if (zero * 0 + one * 1 + two * 2 == sets) {
							rec++;
							zot = new int[]{zero, one, two};
						}
					}
				}
			}
			if (rec >= 2) {
				return AMB;
			}
			
			if (x == 0) {
				for (int z = 0 ; z <= 2 ; z++) {
					for (int d = 0 ; d < zot[z] ; d++) {
						rs.add("3-" + z);
					}
				}
			} else {
				for (int z = 0 ; z <= 2 ; z++) {
					for (int d = 0 ; d < zot[z] ; d++) {
						rs.add(z + "-3");
					}
				}				
			}
		}
		
		Collections.sort(rs);
		String ret = "";
		for (String s : rs) {
			ret += s + ",";
		}
		return ret.substring(0, ret.length() - 1);
	}
}

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

通ったコード

en

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