Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-13SRM494、SRM498など(DIV1)

SRM494 第二問(500pt) AlternatingLane

|  SRM494 第二問(500pt) AlternatingLane - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM494 第二問(500pt) AlternatingLane - hama_DU@TopCoderへの道

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

各木の間のBeauty期待値を計算していけばいい、ということに気づきさえすれば簡単。

あとは 100,000 * 100,000 でintの範囲を超えてしまうため、longで計算することに気をつける。


public class AlternatingLane {
	public long sumexternal(int f, int c, int d) {
		long cthigh = d - c + 1;
		long sumhigh = (d + c) * cthigh / 2;
		long ct = 0;
		ct += sumhigh;
		ct = Math.abs(sumhigh - f * cthigh);
		return ct;
	}

	public long suminternal(int f, int c, int d) {
		long ct = 0;
		ct += (long)(f - c) * (long)(f - c + 1) / 2;
		ct += (long)(d - f) * (long)(d - f + 1) / 2;
		return ct;
	}

	public double expectedBeauty(int[] low, int[] high) {
		int len = low.length;
		if (len == 1) {
			return 0;
		}

		double res = 0.0d;
		for (int i = 0 ; i < len - 1 ; i++) {
			long ct = 0;
			for (int f = low[i] ; f <= Math.min(low[i+1] - 1, high[i]) ; f++) {
				ct += sumexternal(f, low[i+1], high[i+1]);
			}
			for (int f = Math.max(low[i+1], low[i]) ; f <= Math.min(high[i+1], high[i]) ; f++) {
				ct += suminternal(f, low[i+1], high[i+1]);
			}
			for (int f = Math.max(high[i+1] + 1, low[i]) ; f <= high[i] ; f++) {
				ct += sumexternal(f, low[i+1], high[i+1]);
			}
			res += (double)ct / (double)((long)(high[i+1] - low[i+1] + 1) * (long)(high[i] - low[i] + 1));
			System.out.println(res + "/");
		}

		return res;
	}
}

2011-03-08SRM497(DIV1)

CssRules

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

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

この問題は2つのパートに分かれている。

  • 与えられたxhtmlをパースする
  • 最小ルール適用回数を求める

本番中ではパースするコードが正しく書けなくて撃沈。

与えられたxhtmlをパースする

正規表現を使ってタグを切り分けていく。

各タグにつき、タグ名、タグID、目的の色、および含まれるタグの一覧を記憶。

最小ルール適用回数を求める

各idのタグにおいて、8 * 8 * 8 通りのCSSパターンが考えられる。

その各パターンにおいて子のタグにそのCSSが適用できるかどうかを調べ、

タグが子を持つ場合は再度 8 * 8 * 8 通りのCSSパターンを試す。

正しく探索する方針が思いつかず、editorialを見て理解。

こんなんどう考えたら思いつくの・・・?


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class CssRules {

	public List<Tag> tagList = new ArrayList<Tag>();

	public List<Tag> parentTagList = new ArrayList<Tag>();

	public HashMap<Tag, Integer> countMap = new HashMap<Tag, Integer>();

	public int id = -1;

	public int colorToInt(String c){
		if ("black".equals(c)) {
			return 1;
		}
		if ("blue".equals(c)) {
			return 2;
		}
		if ("gray".equals(c)) {
			return 3;
		}
		if ("green".equals(c)) {
			return 4;
		}
		if ("red".equals(c)) {
			return 5;
		}
		if ("white".equals(c)) {
			return 6;
		}
		if ("yellow".equals(c)) {
			return 7;
		}
		return -1;
	}

	private class Tag {
		int id;
		char name;
		int color;
		String hid;
		List<Tag> inner;

		Tag(int _id, char _name, String _hid, String _color) {
			name = _name;
			id = _id;
			hid = _hid;
			color = colorToInt(_color);
			inner = new ArrayList<Tag>();
		}
		public String toString() {
			return name + " id=" + hid + " color=" + color;
		}
	}

	public int[][][][] memo;

	public int getMinimalCssRuleCount(String[] xthml) {
		String xhtml = "";
		for (String line : xthml) {
			xhtml += line;
		}
		System.out.println(xhtml);

		Pattern tagPattern = Pattern.compile("<([bui]) id='([a-z]+)' style='color:([a-z]+)'>");
		Matcher tagMatcher = tagPattern.matcher(xhtml);

		String left = xhtml;
		Stack<Tag> tagStack = new Stack<Tag>();
		while (tagMatcher.find()) {
			String full = tagMatcher.group();
			left = left.split(full, -1)[1];
			id++;
			Tag tag = new Tag(id, tagMatcher.group(1).charAt(0), tagMatcher.group(2), tagMatcher.group(3));
			if (tagStack.size() > 0) {
				tagStack.peek().inner.add(tag);
			} else {
				parentTagList.add(tag);
			}
			tagStack.push(tag);
			tagList.add(tag);

			String endTag = "</" + tagStack.peek().name + ">";
			while (left.startsWith(endTag)) {
				tagStack.pop();
				String l[] = left.split(endTag, 2);
				if (l.length > 0) {
					left = l[l.length - 1];
				} else {
					break;
				}
				if (tagStack.size() == 0) {
					break;
				}
				endTag = "</" + tagStack.peek().name + ">";
			}
		}

		memo = new int[100][8][8][8];
		for (int t = 0 ; t < 100 ; t++) {
			for (int b = 0 ; b <= 7 ; b++) {
				for (int u = 0 ; u <= 7 ; u++) {
					for (int i = 0 ; i <= 7 ; i++) {
						memo[t][b][u][i] = -1;
					}
				}
			}
		}

		int count = 0;
		for (Tag tag : parentTagList) {
			count += search(tag, 0, 0, 0);
		}
		return count;
	}

	public int search(Tag tag, int bc, int uc, int ic) {
		int needs = 0;

		if (memo[tag.id][bc][uc][ic] >= 0) {
			return memo[tag.id][bc][uc][ic];
		}

		switch (tag.name) {
			case 'b':
				if (tag.color != bc) {
					needs++;
				}
				break;
			case 'u':
				if (tag.color != uc) {
					needs++;
				}
				break;
			case 'i':
				if (tag.color != ic) {
					needs++;
				}
				break;
		}
		if (tag.inner.size() == 0) {
			memo[tag.id][bc][uc][ic] = needs;
			return needs;
		}

		int min = 999999999;
		for (int b = 0 ; b <= 7 ; b++) {
			for (int u = 0 ; u <= 7 ; u++) {
				for (int i = 0 ; i <= 7 ; i++) {
					int count = 0;
					int bcc = b == 0 ? bc : b;
					int ucc = u == 0 ? uc : u;
					int icc = i == 0 ? ic : i;
					if (bcc != bc) count++;
					if (ucc != uc) count++;
					if (icc != ic) count++;
					for (Tag childTag : tag.inner) {
						count += search(childTag, bcc, ucc, icc);
					}
					min = Math.min(min, count);
				}
			}
		}
		memo[tag.id][bc][uc][ic] = needs + min;

		return needs + min;
	}
}

2011-03-07SRM482(DIV1)

LockersDivOne

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

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

普通に探索すると間に合わないけど、

配列に「次の空いてるドア」を覚えさせとけば大丈夫。

学校の課題で、Cでリンクリスト実装したときのことを思い出しながら書いた。


public class LockersDivOne {

	public int lastOpened(int N) {
		int l[] = new int[N+1];
		for (int i = 0 ; i <= N ; i++) {
			l[i] = i+1;
		}
		int closed = N;
		int opened = 1;
		int times = 1;
		while (closed > 0) {
			int count = 0;
			int before = 0;
			int index = l[0];
			while (index <= N) {
				if (--count < 0) {
					l[before] = l[index];
					opened = index;
					count = times;
					closed--;
				}
				before = index;
				index = l[index];
			}
			times++;
		}
		return opened;
	}
}

HanoiGoodAndBad

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

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

この問題は2つのパートに分かれている。

  • Daveが手数分動かした際の輪っかの状態を作る
  • Earlがその状態に辿りつくまでの手数を求める

Daveが手数分動かした際の状態を作る

問題文中の solve_Dave(N) を実行するのに 2^N - 1 ターンかかることを考えると、

2^(N-1)-1 ターンあれば 上からN-1個の輪っかをsourceからspareに移すことができ、

余ったターンのうち、

  • 1ターンは 上からN個目の輪っかをtargetに移す
  • 2^(N-1)-1ターンは再度solve_Dave

に使える。

このとき、最初に移す輪っかの数の偶奇により、spareとtargetが入れ替わるので注意する。

再帰関数を愚直に実装した。残り手数が0になったところで終了する。

Earlが特定の状態に辿りつくまでの手数を求める

一番下の輪っかから順番に考えていけばOK。求める状態の輪っかの位置が、

  • sourceにあるなら経過ターン数は0
  • spareにあるなら経過ターン数は (3^(N-1) - 1) + 1
    • 上にあるN - 1個の輪っかを target に移すのに 3^(N-1) - 1 ターン
    • 自身を spareに移すのに 1ターン
    • この状態で、上の輪っかについて考える。sourceとtargetが入れ替わるのことに注意する
  • targetにあるなら経過ターン数は (3^(N-1) * 2 - 2) + 2
    • 上にあるN - 1個の輪っかを sourceからtarget、targetからsourceに移すのに 3^(N-1) * 2 - 2 ターン
    • 自身を sourceからspare、spareからtargetに移すのに 2ターン
    • この状態で、上の輪っかについて考える。

public class HanoiGoodAndBad {

	public int[] state;

	public int doEarl(int N, int source, int target, int spare) {
		if (N == 0) {
			return 0;
		}
		if (state[N-1] == spare) {
			return (int)(Math.pow(3, N-1)) + doEarl(N-1, target, source, spare);
		}
		if (state[N-1] == target) {
			return (int)(Math.pow(3, N-1) * 2) + doEarl(N-1, source, target, spare);
		}
		return doEarl(N-1, source, target, spare);
	}

	public void doDave(int N, int t, int source, int target, int spare) {
		int count = 1;
		int canmove = 0;

		for (int i = 1 ; i <= N - 1 ; i++) {
			count = (int)Math.pow(2, i) - 1;
			if (t <= count) {
				break;
			}
			canmove = i;
		}

		for (int i = N - 1 ; i > canmove ; i--) {
			int sp = target;
			target = spare;
			spare = sp;
		}

		t -= ((int)Math.pow(2, canmove) - 1);
		for (int i = 0 ; i < canmove ; i++) {
			state[i] = spare;
		}
		if (t == 0) {
			return;
		}

		t--;
		state[canmove] = target;
		if (t == 0) {
			return;
		}
		doDave(canmove, t, spare, target, source);
	}

	public int moves(int N, int Dave) {
		state = new int[N];
		doDave(N, Dave, 0, 2, 1);
		return doEarl(N, 0, 2, 1);
	}

}

2011-01-10SRM483(DIV1)

SRM483 第一問(250pt) BestApproximationDiv1

|  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道

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

1000(a) * 1000(b) で全探索余裕でした

何か引っ掛けがあるかと思いきや、特になし。

public class BestApproximationDiv1 {
	public int eq(double x, String number) {
		String enumber = String.valueOf(x);
		int size = enumber.length();
		if (size < 8) {
			for (int i = size ; i < 8 ; i++) {
				enumber += "0";
			}
		}
		int match = 0;
		for (int i = 0 ; i < 8 ; i++) {
			if (i == 1) continue;
			if (enumber.charAt(i) != number.charAt(i)) {
				break;
			}
			match++;
		}
		return match;
	}

	public String findFraction(int maxDen, String number) {
		int maxeq = 0;
		int maxa = 0;
		int maxb = 0;
		for (int a = 0 ; a <= maxDen ; a++) {
			for (int b = 0 ; b < a ; b++) {
				double d = b * 1.0 / a;
				int eq = eq(d, number);
				if (eq > maxeq) {
					maxeq = eq;
					maxa = a;
					maxb = b;
				}
			}
		}
		return maxb+"/"+maxa+" has "+maxeq+" exact digits";
	}
}

SRM483 第二問(500pt) Bribes

|  SRM483 第二問(500pt) Bribes - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM483 第二問(500pt) Bribes - hama_DU@TopCoderへの道

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

ポイントは賄賂の影響が前後8人までしか伝わらないこと。

そこで、ある人を堕とすことができる、17人(前8人、後8人、本人で17名)の賄賂パターンを17bitで表してやるといいようです。

「0」を賄賂しない、「1」を賄賂するに対応させると、例えば本人と前後1人ずつに対して賄賂する場合は

← 並び順
00000001 1 10000000(2)

と表せます。

そして、ある人に対して上記パターンで賄賂に成功した場合は、

次の人に対する賄賂は1bitずつ右にずらして、次のように表せます。

← 並び順
?0000000 1 11000000(2)

? の部分には「0」と「1」を入れ、次の人に対する賄賂の探索候補とします。


public class Bribes {
	public int minBribes(int[] influence, int[] resistance) {
		int len = influence.length;
		int[] inf = new int[len + 17];
		for (int i = 8 ; i < len + 8 ; i++) {
			inf[i] = influence[i-8];
		}

		int[][] dp = new int[len+1][1<<17];
		for (int n = 1 ; n <= len ; n++) {
			java.util.Arrays.fill(dp[n], -1);
		}

		for (int i = 0 ; i < len ; i++) {
			for (int pattern = 0 ; pattern < 1<<17 ; pattern++) {
				if (dp[i][pattern] == -1) {
					continue;
				}

				int bib = 0;
				for (int j = 0 ; j < 17 ; j++) {
					if (((1 << j) & pattern) > 0) {
						bib += inf[i+j] >> Math.abs(8 - j);
					}
				}
				if (bib >= resistance[i]) {
					int next = pattern >> 1;
					int val = (pattern & 1) + dp[i][pattern];

					if (dp[i+1][next] == -1) {
						dp[i+1][next] = val;
					} else {
						dp[i+1][next] = Math.min(dp[i+1][next], val);
					}

					next |= 0x10000;
					if (dp[i+1][next] == -1) {
						dp[i+1][next] = val;
					} else {
						dp[i+1][next] = Math.min(dp[i+1][next], val);
					}

				}
			}
		}

		int minnum = -1;
		for (int i = 0 ; i < 1<<17 ; i++) {
			if (dp[len][i] >= 0) {
				int bribenum = Integer.bitCount(i) + dp[len][i];
				if (bribenum < minnum || minnum == -1) {
					minnum = bribenum;
				}
			}
		}
		return minnum;
	}
}

2010-11-23SRM488(DIV1)

SRM488 第一問(250pt) TheBoredomDivOne

|  SRM488 第一問(250pt) TheBoredomDivOne - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM488 第一問(250pt) TheBoredomDivOne - hama_DU@TopCoderへの道

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

  • 期待値をメモ化すればおk。
  • 時間はかかったが解けた。120点ぐらい

public class TheBoredomDivOne {
	public double[][] ex;

	public double calc(int n, int m) {
		if (m <= 0) {
			return 0;
		}
		if (ex[n][m] > 0) {
			return ex[n][m];
		}
		double all = (n + m) * (n + m - 1) / 2;
		double zero = n * (n - 1) / 2 / all;
		double two = m * (m - 1) / 2 / all;
		double one = 1 - (zero + two);

		double ans = (zero + one * (1 + calc(n+1, m-1)) + two * (1 + calc(n+2, m-2))) / (one + two);
		ex[n][m] = ans;
		return ans;
	}

	public double find(int n, int m) {
		ex = new double[100][100];
		ex[1][1] = 1.0;
		ex[2][1] = 1.5;
		ex[1][2] = 2.0;
		return calc(n, m);
	}
}

SRM488 第二問(500pt) TheBoringStoreDivOne

|  SRM488 第二問(500pt) TheBoringStoreDivOne - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM488 第二問(500pt) TheBoringStoreDivOne - hama_DU@TopCoderへの道

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

  • J、Bそれぞれ、2回以上出現する部分文字列をメモ。
  • その部分文字列をいくつか右(Bの場合は左)に伸ばしたパターンを全列挙。
    • substringやindexOf周りでバグったりした。
  • 全パターンゴリ押し。O(N^4)
  • 数時間かかって、他人のコードも参考にしながらやっと解けた。
    • systestで1.8sかかったケースもありかなりギリギリだった。(2秒以上だとタイムアップ)
    • div1の第2問を時間内に解くのは今の実力では難しい。方針はつかめるようになってきたけどね。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

public class TheBoringStoreDivOne {
	public HashMap<String, HashSet<String>> jpattern = new HashMap<String, HashSet<String>>();
	public HashMap<String, HashSet<String>> bpattern = new HashMap<String, HashSet<String>>();

	public boolean isGreater(String a, String b) {
		if (a.length() > b.length() || (a.length() == b.length() && a.compareTo(b) < 0)) {
			return true;
		}
		return false;
	}

	public void addAllJ(HashMap<String, HashSet<String>> w, String pattern, String sub, int idx) {
		HashSet<String> list = null;
		if (!w.containsKey(pattern)) {
			list = new HashSet<String>();
		} else {
			list = w.get(pattern);
		}
		list.add("");

		String a = "";
		int from = idx + pattern.length();
		int to = sub.length();
		for (int i = from ; i < to ; i++) {
			a += sub.substring(i, i + 1);
			list.add(a);
		}
		w.put(pattern, list);
	}

	public void addAllB(HashMap<String, HashSet<String>> w, String pattern, String sub, int idx) {
		HashSet<String> list = null;
		if (!w.containsKey(pattern)) {
			list = new HashSet<String>();
		} else {
			list = w.get(pattern);
		}
		list.add("");

		String a = "";
		int from = idx - 1;
		int to = 0;
		for (int i = from ; i >= to ; i--) {
			a = sub.substring(i, i + 1) + a;
			list.add(a);
		}
		w.put(pattern, list);
	}

	public void jyunbi(String J, String B) {
		int j = J.length();
		int b = B.length();
		for (int x = 0 ; x < j ; x++) {
			for (int y = x + 1 ; y <= j ; y++) {
				String pattern = J.substring(x, y);
				String prefix = J.substring(0, x);
				String suffix = J.substring(y, j);


				int pre = prefix.indexOf(pattern);
				if (pre != -1) {
					do {
						addAllJ(jpattern, pattern, prefix, pre);
						pre = prefix.indexOf(pattern, pre+1);
					} while(pre != -1);
				}

				int suf = suffix.indexOf(pattern);
				if (suf != -1) {
					do {
						addAllJ(jpattern, pattern, suffix, suf);
						suf = suffix.indexOf(pattern, suf+1);
					} while(suf != -1);
				}
			}
		}

		for (int x = 0 ; x < b ; x++) {
			for (int y = x + 1 ; y <= b ; y++) {
				String pattern = B.substring(x, y);
				String prefix = B.substring(0, x);
				String suffix = B.substring(y, b);

				int pre = prefix.lastIndexOf(pattern);
				if (pre != -1) {
					do {
						addAllB(bpattern, pattern, prefix, pre);
						pre = prefix.lastIndexOf(pattern, pre-1);
					} while(pre != -1);
				}

				int suf = suffix.lastIndexOf(pattern);
				if (suf != -1) {
					do {
						addAllB(bpattern, pattern, suffix, suf);
						suf = suffix.lastIndexOf(pattern, suf-1);
					} while(suf != -1);
				}
			}
		}
	}

	public String find(String J, String B) {
		jyunbi(J, B);
		String answer = "";

		for (Entry<String, HashSet<String>> jp : jpattern.entrySet()) {
			for (String amarinJ : jp.getValue()) {
				for (Entry<String, HashSet<String>> bp : bpattern.entrySet()) {
					for (String amarinB : bp.getValue()) {
						if (amarinJ.equals(amarinB)) {
							String result = jp.getKey() + amarinJ + bp.getKey();
							if (isGreater(result, answer)) {
								answer = result;
							}
						}
					}
				}
			}
		}

		return answer;
	}
}