Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

SRM336 (Practice)

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

問題結果ポイントその他
250ServiceNamesAccepted196.25実装
500LikelyWordWA0.00実装
1000ShadowOpened0.00幾何

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

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

SRM337 (Practice)

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

問題結果ポイントその他
250CardStraightsWA0.00実装
500BuildingAdvertiseOpened0.00データ構造
1000CountPalindromesOpened0.00DP

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

SRM338 (Practice)

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

問題結果ポイントその他
250ImprovingStatisticsAccepted239.03二分探索
500RandomSwapsAccepted416.29確率
1000CakePartyOpened0.00

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