Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-28ARC003

ARC003 A GPA計算

|  ARC003 A GPA計算 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 A GPA計算 - hama_DU@TopCoderへの道

  • 一瞬。
    • 足して、平均を取るだけ。

ARC003 B さかさま辞書

|  ARC003 B さかさま辞書 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 B さかさま辞書 - hama_DU@TopCoderへの道

  • List<String> に反転した文字列を突っ込む。
    • new StringBuffer(S).reverse().toString()
  • ソートする。
    • Collections.sort()
  • 順番に出力。
    • 出力するときに反転を元に戻す

ARC003 C 暗闇帰り道

|  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道

  • 方針を考える。
    • ダイクストラする?
      • (現在位置,時間)を状態に持つ
      • 500 * 500 * 1000 ぐらいになっておそらく間に合わない。
  • しばらく考える
    • 二分探索で、通れる明るさの上限を決めてしまおう
      • これだと現在位置だけを状態に持てばいいので、 500 * 500 * (二分探索の回数) で済む。
    • これでよさそう。
  • 実装
    • 特に詰まること無くサクサク。
    • 各明るさの初期値 (i:1〜9) について、n時間たった時の明るさを予め dvalue[i][n] に計算しておく
  • 出してみる。
    • TLEしてしまう。あれ?
    • 二分探索で誤差がe-10ぐらいになったら打ち切るようにしてみる
  • 再提出
    • 今度はWA
    • 到達不可の場合は -1 を出力しなければならないが、その判定がミスってる
      • 二分探索する前に、到達可否を調べるコードを書いた。
  • 提出。やっとACがもらえた。この時点で残り30分。

ARC003 D シャッフル席替え

|  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道

  • これは難しそう・・・
  • 制約の小ささから、bitDP的なことができるのではと思ってみる
    • dp[K][P] : K回席替えした時、禁止パターンの出現組合せがPになってる確率
    • でも、更新式が思い浮かばない。
    • 紙に書いてみても、
  • 素直に順列を全探索か?
    • 制限時間10秒あるし・・・
  • 書いてる途中にコンテスト終わった

コンテスト後

  • 答えの誤差が 0.002 まで許されることから、モンテカルロ法が使えるらしい。
    • 実際にランダムにK回席替えをして、禁止パターンになってるかどうか調べるという実験をする。
    • 成功数 / 試行回数 が答え
  • 制限時間ギリギリまで実験するコードを書いたら通った。

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

SRM 336 ServiceNames

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

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

  • ん?問題の意図するところがわからない・・・
    • サンプルから察するにやるだけっぽい
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ServiceNames {

	class Ret implements Comparable<Ret> {
		String service;
		List<String> items;
		Set<String> done;
		Ret(String a) {
			service = a;
			items = new ArrayList<String>();
			done = new HashSet<String>();
		}
		
		public void add(String item) {
			if (done.contains(item)) {
				return;
			}
			done.add(item);
			items.add(item);
			Collections.sort(items);
		}

		public int compareTo(Ret arg0) {
			return service.compareTo(arg0.service);
		}
		
		public String toString() {
			StringBuffer b = new StringBuffer(service);
			b.append(" ==> " + items.get(0));
			for (int j = 1 ; j < items.size() ; j++) {
				b.append(", ").append(items.get(j));
			}
			return b.toString();
		}
	}
	
	public String[] makeList(String[] services) {
		int len = services.length;
		List<Ret> list = new ArrayList<Ret>();
		Map<String, Ret> servmap = new HashMap<String, Ret>();
		for (int i = 0 ; i < len ; i++) {
			String[] x = services[i].split(" ");
			String item = x[0];
			for (int j = 1 ; j < x.length ; j++) {
				String serv = x[j];
				if (!servmap.containsKey(serv)) {
					servmap.put(serv, new Ret(serv));
					list.add(servmap.get(serv));
				}
				servmap.get(serv).add(item);
			}
		}
		
		Collections.sort(list);
		
		String[] r = new String[list.size()];
		for (int i = 0 ; i < list.size() ; i++) {
			r[i] = list.get(i).toString();
		}
		return r;
	}
}

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 336 Shadow

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

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

  • 問題文をナナメ読みしてそっと閉じた
    • 後でちゃんと解く。

SRM 337 CardStraights

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

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

  • し、しまった・・・(無能)
    • ジョーカーが余るパターンで、左に配置するパターンを考慮してなかった
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CardStraights {

	public int longestStraight(int[] cards) {
		Arrays.sort(cards);
		
		int len = cards.length;
		int js = 0;
		List<Integer> normals = new ArrayList<Integer>();
		for (int i  = 0 ; i < len ; i++) {
			if (cards[i] == 0) {
				js++;
			} else {
				if (!normals.contains(cards[i])) {
					normals.add(cards[i]);
				}
			}
		}
		
		int cl = normals.size();
		
		int max = js;
		for (int i = 0 ; i < cl ; i++) {
			int left = js;
			int cont = 1;
			int from = normals.get(i);
			for (int j = i ; j < cl - 1 ; j++) {
				int x = normals.get(j+1) - normals.get(j) - 1;
				if (x <= left) {
					left -= x;
					cont += x + 1; 
				} else {
					cont += left;
					left = 0;
					break;
				}
			}
			
			if (i == 0 && from >= 2) {
				cont += Math.min(from - 1, left);
				left -= Math.min(from - 1, left);
			} else if (i >= 1 && left >= 1) {
				int d = normals.get(i) - normals.get(i-1) - 1;
				cont += Math.min(d, left);
				left -= Math.min(d, left);
			}
			if (left >= 1) {
				int yetanother = 1000000 - normals.get(cl-1);
				cont += Math.min(yetanother, left);
			}
			max = Math.max(max, cont);
		}
		return max;
	}
}

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 337 CountPalindromes

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

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

  • 典型的な文字列回文DP
    • 左右どちらかに余る文字列パターンは 15 * 15 * 2 * 50 = 22,500 なので、文字列 -> 数にエンコードして持っておく
    • どの文字列パターンにどの文字列を当てるとどの文字列パターンになるか、という状態遷移関数を前もって作成しておく。
      • これをやらないと多分文字列操作コストが重くてTLEする。
  • 時間はかかったが、一発ACできた。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CountPalindromes {
	
	long MOD = 835454957;

	class Go {
		int from;
		int to;
		int change;
		int add;
		Go(int f, int t, int c, int a) {
			from = f;
			to = t;
			change = c;
			add = a;
		}
	}
	
	public int count(String[] words, int alen) {
		int len = words.length;
		Map<String, Integer> strmap = new HashMap<String, Integer>();

		
		String[][] strs = new String[len][2];
		for (int i = 0 ; i < len ; i++) {
			strs[i][0] = words[i];
			strs[i][1] = new StringBuffer(words[i]).reverse().toString();
		}
		
		List<String> strlist = new ArrayList<String>();
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < 2 ; j++) {
				int strlen = strs[i][j].length();
				for (int k = 0 ; k < strlen ; k++) {
					for (int l = k + 1 ; l <= strlen ; l++) {
						String str = strs[i][j].substring(k, l);
						if (!strmap.containsKey(str)) {
							strmap.put(str, strmap.size());
							strlist.add(str);
						}
					}
				}
			}
		}
		strmap.put("", strmap.size());
		strlist.add("");
		
		
		int wordcnt = strmap.size();
		int emptword = wordcnt - 1;
		
		long[][][] dp = new long[101][wordcnt][2];
		for (int i = 0 ; i < len ; i++) {
			String str = words[i];
			int wid = strmap.get(str);
			dp[str.length()][wid][0] = 1;
		}
		
		List<Go>[][] crspids = new List[wordcnt][2];
		for (int i = 0 ; i < wordcnt ; i++) {
			crspids[i][0] = new ArrayList<Go>();
			crspids[i][1] = new ArrayList<Go>();
			String basestr = strlist.get(i);
			for (int j = 0 ; j < len ; j++) {
				for (int d = 0 ; d <= 1 ; d++) {
					String matchstr = strs[j][d];
					int change = 0;
					String left = "";
					if (matchstr.startsWith(basestr)) {
						change = 1;
						left = matchstr.substring(basestr.length());
					} else if (basestr.startsWith(matchstr)) {
						change = 0;
						left = basestr.substring(matchstr.length());
					} else {
						continue;
					}
					crspids[i][d].add(new Go(i, strmap.get(left), change, matchstr.length() + 1));
				}
			}
		}
		
		
		
		
		for (int i = 0 ; i < alen ; i++) {
			for (int j = 0 ; j < wordcnt ; j++) {
				for (int k = 0 ; k <= 1 ; k++) {
					if (dp[i][j][k] == 0) {
						continue;
					}
					long base = dp[i][j][k];
					int opsk = 1 - k;
					for (Go g : crspids[j][opsk]) {
						int ni = i + g.add;
						int nj = g.to;
						int nk = (g.change == 1) ? 1 - k : k;
						if (ni <= alen) {
							dp[ni][nj][nk] += base;
							dp[ni][nj][nk] %= MOD;
						}
					}
				}
			}
		}
		
		
		boolean[] isp = new boolean[wordcnt];
		for (int i = 0 ; i < wordcnt ; i++) {
			String str = strlist.get(i);
			String rev = new StringBuffer(str).reverse().toString();
			if (str.equals(rev)) {
				isp[i] = true;
			}
		}
		
		
		long ans = 0;
		for (int j = 0 ; j < wordcnt ; j++) {
			if (isp[j]) {
				for (int i = 1 ; i <= alen ; i++) {
					for (int k = 0 ; k <= 1 ; k++) {
						ans += dp[i][j][k];
						ans %= MOD;
					}
				}
			}
		}
		return (int)ans;
	}
}

SRM 338 ImprovingStatistics

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

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

  • 二分探索するだけ
public class ImprovingStatistics {

	public int calcRate(long p, long w) {
		return (int)(w * 100 / p);
	}
	
	public long INF = 2000000000;
	
	public int howManyGames(int played, int won) {
		long pl = played;
		long wl = won;
		int rate = calcRate(pl, wl);
		int obj = rate + 1;
		
		if (calcRate(pl + INF, wl + INF) < obj) {
			return -1;
		}
		
		long max = INF;
		long min = 0;
		for (int c = 0 ; c < 100 ; c++) {
			long mid = (max + min) / 2;
			if (calcRate(pl + mid, wl + mid) >= obj) {
				max = mid;
			} else {
				min = mid;
			}
		}
		return (int)max;
	}
}

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 BusTrip

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

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

  • 問題文のとおりにシミュレーションするだけ。
import java.util.Arrays;

public class BusTrip {
	class Bus {
		int total;
		int id;
		int[] begins;
		int[] next;
		Bus(String input, int i) {
			String[] strs = input.split(" ");
			begins = new int[101];
			next = new int[101];
			Arrays.fill(begins, -1);
			Arrays.fill(next, -1);
			int len = strs.length;
			
			total = 0;

			// total distance
			int prev =  Integer.valueOf(strs[0]);
			for (int j = 0 ; j < len ; j++) {
				int dg = Integer.valueOf(strs[j]);
				int diff = Math.abs(prev - dg);
				total += diff;
				begins[dg] = total;
				prev = dg;
			}
			total += Math.abs(prev - Integer.valueOf(strs[0]));

			// next
			for (int j = 0 ; j < len - 1 ; j++) {
				int from = Integer.valueOf(strs[j]);
				int to = Integer.valueOf(strs[j+1]);
				next[from] = to;
			}
			next[Integer.valueOf(strs[len-1])] = Integer.valueOf(strs[0]);
			
			id = i;
		}
	}

	public int returnTime(int N, String[] buses) {
		int bl = buses.length;
		Bus[] b = new Bus[bl];
		for (int i = 0 ; i < bl ; i++) {
			b[i] = new Bus(buses[i], i);
		}
		
		int time = -1;
		int now = 0;
		while (time <= 1000) {
			int bestbus = -1;
			int besttime = 100000;
			for (int i = 0 ; i < bl ; i++) {
				if (b[i].begins[now] == -1) {
					continue;
				}
				for (int c = 0 ; c < 1000 ; c++) {
					int cometime = b[i].begins[now] + b[i].total * c;
					if (cometime > time) {
						if (besttime > cometime) {
							besttime = cometime;
							bestbus = i;
						}
						break;
					}
				}
			}
			if (bestbus == -1) {
				System.out.println("err");
			}
			
			int go = b[bestbus].next[now];
			time = besttime + Math.abs(go - now);
			now = go;
			if (now == 0) {
				break;
			}
		}
		return (time >= 1001) ? -1 : time;
	}
}

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 ProblemsToSolve

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

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

  • 動的計画法
    • 座標圧縮して [現在位置][最大][最小] でDPする
import java.util.Arrays;

public class ProblemsToSolve {
	public int minNumber(int[] pn, int variety) {
		int len = pn.length;
		int[] pmap = new int[1001];
		int[] idxscore = new int[1001];
		Arrays.fill(pmap, -1);
		int pidx = 0;
		for (int x : pn) {
			if (pmap[x] == -1) {
				pmap[x] = pidx;
				idxscore[pidx] = x;
				pidx++;
			}
		}
		
		int[][][] dp = new int[len][pidx][pidx];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				Arrays.fill(dp[i][j], 10000);
			}
		}
		dp[0][pmap[pn[0]]][pmap[pn[0]]] = 1;
		
		int min = len;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				for (int k = 0 ; k < pidx ; k++) {
					if (dp[i][j][k] >= 10000) {
						continue;
					}
					for (int go = i + 1 ; go <= i + 2 ; go++) {
						if (go >= len) {
							continue;
						}
						
						int solve = dp[i][j][k] + 1;
						int wmin = Math.min(idxscore[j], pn[go]);
						int wmax = Math.max(idxscore[k], pn[go]);
						if (wmax - wmin >= variety) {
							min = Math.min(min, solve);
						}
						int tj = pmap[wmin];
						int tk = pmap[wmax];
						if (dp[go][tj][tk] > solve) {
							dp[go][tj][tk] = solve;
						}
					}
				}
			}
		}
		return min;
	}
}

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 340 VegetableGarden

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

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

  • 面白い問題。
    • グラフに帰着できるような気がするが、どうすればいいかわからない
    • 答えは必ず偶数になる?
  • あとで解く。

SRM 341 KLastNonZeroDigits

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

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

  • やるだけ。
public class KLastNonZeroDigits {
	public String getKDigits(int N, int K) {
		long x = 1;
		for (long a = N ; a >= 1 ; a--) {
			x *= a;
			while (x % 10 == 0 && x >= 1) {
				x /= 10;
			}
		}
		
		String str = String.valueOf(x);
		if (str.length() <= K) {
			return str;
		}
		return str.substring(str.length() - K, str.length());
	}
}

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 341 ValidPlates

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

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

  • DP
    • 行列累乗すればいい気がする
  • まだ解いてない

SRM 342 TagalogDictionary

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

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

  • やるだけ。
    • Comparatorの中に変数を仕込む方法が分からなかったので仕方なくバブルソートでやった
import java.util.Arrays;
import java.util.Comparator;

public class TagalogDictionary {

	int[] ord;
	int ngord;
	
	public int compare(String arg0, String arg1) {
		if (arg0.equals(arg1)) {
			return 0;
		}
		int al = arg0.length();
		int bl = arg1.length();
		int aidx = 0;
		int bidx = 0;
		while (aidx < al && bidx < bl) {
			char a = arg0.charAt(aidx);
			char b = arg1.charAt(bidx);
			int aval = ord[a];
			int bval = ord[b];
			aidx++;
			bidx++;
			if (a == 'n' && aidx < al) {
				if (arg0.charAt(aidx) == 'g') {
					aval = ngord;
					aidx++;
				}
			}
			if (b == 'n' && bidx < bl) {
				if (arg1.charAt(bidx) == 'g') {
					bval = ngord;
					bidx++;
				}
			}
			if (aval < bval) {
				return -1;
			} else if (aval > bval) {
				return 1;
			}
		}
		if (aidx >= al) {
			return -1;
		}
		return 1;
	}
	
	public String[] sortWords(String[] words) {
		String order = "a b k d e g h i l m n ng o p r s t u w y";
		
		
		String[] cp = order.split(" ");
		int cl = cp.length;
		ord = new int[512];
		ngord = 0;
		for (int i = 0 ; i < cl ; i++) {
			if (cp[i].length() == 1) {
				ord[cp[i].charAt(0)] = i;
			} else {
				ngord = i;
			}
		}
		
		int len = words.length;
		for (int y = 0 ; y < len ; y++) {
			for (int x = 0 ; x < len - 1 ; x++) {
				int i = x;
				int j = x + 1;
				String a = words[i];
				String b = words[j];
				int comp = compare(a, b);
				if (comp > 0) {
					String t = words[i];
					words[i] = words[j];
					words[j] = t;
				}
			}
		}
		
		return words;
	}
}

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

SRM 342 DrivingAround

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

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

  • 既視感のある問題。
  • だが、この問題は辺に重みがついているので違う問題になっている
    • 待てよ、重みが w >= 2 の時はダミーの頂点を w-1 個はさんでやることで重みなしのグラフにできるのでは
    • これで簡易版「いけるかな?」に帰着できた
  • しかし、最大でノードが 10 + 90 * 4 = 370個必要になる。
    • 相当スパースな行列になるが、累乗すると 370^3 のコストが重くのしかかる
    • しかも、「いけるかな」とは違い場合の数を求めなきゃなので、MOD操作のコストがものすごく重い。
      • YES/NO 問題だったらまだ救いはあったが・・・
  • この考え方ではダメのようだ。
    • 一応、書いて出してみるか・・・問題の条件を見落としてるかもしれないし。
      • 案の定TLE。dsyn-

その後

  • ノード数は実は50個用意すれば十分
    • あるノードから他のノードに向かう途中のダミーノードは共通にして使いまわせるため

通ったコード

public class DrivingAround {
	long MOD = 1000003;

	public long[][] e(int size) {
		long[][] e = new long[size][size];
		for (int i = 0; i < size; i++) {
			e[i][i] = 1;
		}
		return e;
	}

	public long[][] pow(long[][] a, long p) {
		long x = 1;
		int len = a.length;
		long[][] ans = e(len);
		while (x <= p) {
			if ((p & x) >= 1) {
				ans = mul(ans, a);
			}
			x *= 2;
			a = mul(a, a);
		}
		return ans;
	}
	
	public long[][] mul(long[][] a, long[][] b) {
		int h = a.length;
		int w = b[0].length;
		int kk = a[0].length;
		long[][] c = new long[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				long sum = 0;
				for (int k = 0; k < kk; k++) {
					sum += (a[i][k] * b[k][j]);
					if (sum >= MOD + 1) {
						 sum %= MOD;
					}
				}
				c[i][j] = sum;
			}
		}
		return c;
	}

	public void print(long[][] a) {
		int h = a.length;
		int w = a[0].length;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}

	public int numberOfWays(String[] adj, int start, int finish, int time) {
		int len = adj.length;

		long[][] a = new long[51][51];
		int idx = len;
		for (int i = 0; i < len; i++) {
			for (int x = 0 ; x < 4 ; x++) {
				a[i*5+x][i*5+x+1] = 1;
			}
			for (int j = 0; j < len; j++) {
				if (adj[i].charAt(j) == '.') {
				} else {
					int recur = adj[i].charAt(j) - '1';
					a[i*5+recur][j*5] = 1;
				}
			}
		}

		a = pow(a, time);

		return (int) (a[start*5][finish*5] % MOD);
	}
}

TLEするコード

public class DrivingAround {

	long MOD = 1000003;

	public long[][] e(int size) {
		long[][] e = new long[size][size];
		for (int i = 0; i < size; i++) {
			e[i][i] = 1;
		}
		return e;
	}

	public long[][] pow(long[][] a, long p) {
		long x = 1;
		int len = a.length;
		long[][] ans = e(len);
		while (x <= p) {
			if ((p & x) >= 1) {
				ans = mul(ans, a);
			}
			x *= 2;
			a = mul(a, a);
		}
		return ans;
	}

	public long[][] mul(long[][] a, long[][] b) {
		int h = a.length;
		int w = b[0].length;
		int kk = a[0].length;
		long[][] c = new long[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				long sum = 0;
				for (int k = 0; k < kk; k++) {
					sum += (a[i][k] * b[k][j]) % MOD;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}

	public void print(long[][] a) {
		int h = a.length;
		int w = a[0].length;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}

	public int numberOfWays(String[] adj, int start, int finish, int time) {
		int len = adj.length;

		boolean[][] graph = new boolean[500][500];
		int idx = len;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (adj[i].charAt(j) == '.') {
				} else {
					int recur = adj[i].charAt(j) - '0';
					int from = i;
					for (int x = 0; x < recur - 1; x++) {
						graph[from][idx] = true;
						from = idx;
						idx++;
					}
					graph[from][j] = true;
				}
			}
		}

		long[][] a = new long[idx][idx];
		for (int i = 0; i < idx; i++) {
			for (int j = 0; j < idx; j++) {
				if (graph[i][j]) {
					a[i][j] = 1;
				}
			}
		}
		a = pow(a, time);

		return (int) (a[start][finish] % MOD);
	}
}

2012-04-21SRM343, SRM344 (Practice)

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

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

通ったコード

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