Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-10SRM346 (Practice)

SRM 346 CommonMultiples

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

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

  • やるだけ。
public class CommonMultiples {

	public long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a%b);
	}
	
	public long lcm(long a, long b) {
		long gcd = gcd(a, b);
		return (a / gcd) * b;
	}
	
	
	public int countCommMult(int[] a, int lower, int upper) {
		long lo = lower;
		long up = upper;
		
		long l = 1;
		for (int i = 0 ; i < a.length ;i++) {
			l = lcm(l, a[i]);
			if (l > up || l <= 0) {
				return 0;
			}
		}	
		return (int)((up / l) - ((lo - 1) / l));
	}
}

2012-04-05SRM347 (Practice)

SRM 347 Aircraft

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

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

  • ふつーに三分探索しようとした
    • 式が間違ってて答えが合わなかった。ひどい
  • editorial見ると二次方程式を解くのがいいらしい。なんと
public class Aircraft {
	long RR;
	public String nearMiss(int[] p1, int[] v1, int[] p2, int[] v2, int R) {
		RR = 1L * R * R;
		
		long[] np = new long[3];
		long[] dv = new long[3];
		for (int i = 0 ; i < 3 ; i++) {
			np[i] = p2[i] - p1[i];
			dv[i] = v2[i] - v1[i];
		}
		
		long A = 0, B = 0, C = 0;
		for (int i = 0 ; i < 3 ; i++) {
			A += dv[i] * dv[i];
			B += 2 * np[i] * dv[i];
			C += np[i] * np[i];
		}
		if (C <= RR) {
			return "YES";
		}
		if (A == 0 || B >= 0) {
			return "NO";
		}
		if (B * B - 4 * A * (C - R * R) >= 0) {
			return "YES";
		}
		return "NO";
	}
}

2012-04-04SRM349 (Practice)

SRM 348 LostParentheses

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

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

  • Greedyなアルゴリズムなんて思いつかないので、区間DPをする
import java.util.Arrays;

public class LostParentheses {
	int INF = 1000000;
	int[] nums, ops;
	int[][] memo;
	
	public int dfs(int from, int to) {
		if (from == to) {
			return nums[from];
		}
		if (memo[from][to] != INF) {
			return memo[from][to];
		}
		
		int ret = INF;
		for (int j = from ; j < to ; j++) {
			int a = dfs(from, j);
			int b = dfs(j+1, to);
			if (ops[j+1] == 1) {
				ret = Math.min(ret, a + b);
			} else if (ops[j+1] == -1) {
				ret = Math.min(ret, a - b);
			}
		}
		memo[from][to] = ret;
		return ret;
	}
	
	
	public int minResult(String e) {
		String[] numstrs = e.split("[+-]");
		nums = new int[numstrs.length];
		for (int i = 0 ; i < numstrs.length ; i++) {
			nums[i] = Integer.valueOf(numstrs[i]);
		}
		
		String[] opstrs = e.split("[0-9]+");
		ops = new int[opstrs.length];
		for (int i = 0 ; i < opstrs.length ; i++) {
			if ("+".equals(opstrs[i])) {
				ops[i] = 1;
			} else if ("-".equals(opstrs[i])) {
				ops[i] = -1;
			}
		}
		
		memo = new int[nums.length+1][nums.length+1];
		for (int i = 0 ; i < nums.length+1 ; i++) {
			Arrays.fill(memo[i], INF);
		}
		
		return dfs(0, nums.length-1);
	}
}

SRM 349 RadarFinder

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

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

  • 場合分け。
    • 一方の円が他方の円を完全に含む場合などに注意する
    • オーバーフローにも注意する
      • あらかじめ引数をlongに再代入しておく
public class RadarFinder {
	public int possibleLocations(int ix1, int iy1, int ir1, int ix2, int iy2, int ir2) {
		long x1 = ix1, x2 = ix2;
		long y1 = iy1, y2 = iy2;
		long r1 = ir1, r2 = ir2;
		
		if (x1 == x2 && y1 == y2) {
			if (r1 == r2) {
				return -1;
			}
			return 0;
		}
		
		long dx = Math.abs(x2 - x1);
		long dy = Math.abs(y2 - y1);
		long dist2 = dx * dx + dy * dy;
		long rr2 = (r1 + r2) * (r1 + r2);
		if (dist2 < rr2) {
			long rr1 = (r1 - r2) * (r1 - r2);
			if (dist2 < rr1) {
				return 0;
			} else if (dist2 == rr1) {
				return 1;
			}
			return 2;
		} else if (dist2 == rr2) {
			return 1;
		}
		return 0;
	}
}

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 350 SumsOfPerfectPowers

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

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

  • 求めるべき数の中で、m >= 2 で a^m となってる数はそんなに多くない。
    • なので、全て列挙し、2つの数の組み合わせを全部試せる。
import java.util.HashSet;
import java.util.Set;

public class SumsOfPerfectPowers {
	int MAX = 8000000;
	
	public int howMany(int lowerBound, int upperBound) {
		boolean[] done = new boolean[MAX];
		Set<Integer> l = new HashSet<Integer>();
		
		for (int a = 0 ; a <= 10000 ; a++) {
			long aa = a;
			for (int m = 2 ; m <= 100 ; m++) {
				aa *= a;
				if (aa >= MAX || aa <= -1) {
					break;
				}
				l.add((int)aa);
			}
		}

		int cnt = 0;
		boolean[] met = new boolean[MAX];
		for (int a : l) {
			for (int b : l) {
				int ab = a + b;
				if (lowerBound <= ab && ab <= upperBound) {
					if (!met[ab]) {
						met[ab] = true;
						cnt++;
					}
				}
			}
		}
		return cnt;
	}
}

SRM 351 CoinsExchange

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

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

  • 貪欲法
    • 足りないGold、Silver、Bronzeの順に両替を行いながら埋め合わせる
  • 通ったのがいいがきれいな実装ができなかったので後で確認する。
public class CoinsExchange {
	public int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2) {
		int req = 0;
		if (G2 > G1) {
			int gneed = G2 - G1;
			if (S1 >= 11 * gneed) {
				req += gneed;
				S1 -= 11 * gneed;
			} else {
				int sneed = 11 * gneed - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					req += gneed;
					B1 -= 11 * sneed;
					S1 += sneed;
					S1 -= 11 * gneed;
				} else {
					return -1;
				}
			}
		}
		
		if (S2 > S1) {
			int sneed = S2 - S1;
			if (G1 - G2 > 0) {
				int lgold = G1 - G2;
				int needgold = (sneed + 8) / 9;
				if (lgold >= needgold) {
					req += needgold;
					G1 -= needgold;
					S1 += needgold * 9;
				} else {
					req += lgold;
					G1 = G2;
					S1 += lgold * 9;
				}
			}
			if (S2 > S1) {
				sneed = S2 - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					B1 -= 11 * sneed;
					S1 += sneed;
				} else {
					return -1;
				}
			}
		}
		
		
		if (B2 > B1) {
			int needbronze = B2 - B1;
			int reqsilver = (needbronze + 8) / 9;
			req += reqsilver;
			if (S1 - S2 >= reqsilver) {
			} else {
				reqsilver -= (S1 - S2); 
				int reqgold = (reqsilver + 8) / 9;
				if (G1 - G2 >= reqgold) {
					req += reqgold;
				} else {
					return -1;
				}
			}
		}	
		return req;
	}
}

SRM 352 NumberofFiboCalls

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

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

  • やるだけ
    • 練習では配列のサイズ指定ミスでREをくらう
public class NumberofFiboCalls {
	public int[] fiboCallsMade(int n) {
		int[][] ret = new int[41][2];
		ret[0][0] = 1;
		ret[0][1] = 0;
		ret[1][0] = 0;
		ret[1][1] = 1;
		
		for (int k = 2 ; k <= n ; k++) {
			ret[k][0] = ret[k-1][0] + ret[k-2][0];
			ret[k][1] = ret[k-1][1] + ret[k-2][1];
		}
		return ret[n];
	}
}

2012-04-02SRM353, SRM354 (Practice)

SRM 353 Glossary

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

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

  • 問題文の通りに正しく実装する。
    • 文字列の比較はcase insensitiveなのに注意(サンプルにあって助かった)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Glossary {

	public String[] buildGlossary(String[] items) {
		List<String>[] list = new List[256];
		for (int i = 0 ; i < 256 ; i++) {
			list[i] = new ArrayList<String>();
		}
		int len = items.length;
		for (int i = 0 ; i < len ; i++) {
			String a = items[i];
			char c = a.charAt(0);
			if ('a' <= c && c <= 'z') {
				c = (char)('A' + (c - 'a'));
			}
			list[c].add(a);
		}
		for (int i = 'A' ; i <= 'Z' ; i++) {
			Collections.sort(list[i], new Comparator<String>(){
				public int compare(String a, String b) {
					return a.compareToIgnoreCase(b);
				}
			});
		}
		
		
		List<String> left = new ArrayList<String>();
		List<String> right = new ArrayList<String>();
		
		for (int i = 'A' ; i <= 'M' ; i++) {
			if (list[i].size() >= 1) {
				left.add((char)i + "                  ");
				left.add("-------------------");
				for (String l : list[i]) {
					int sz = l.length();
					String add = "  " + l;
					for (int j = sz ; j < 17 ; j++) {
						add += ' ';
					}
					left.add(add);
				}
			}
		}
		for (int i = 'N' ; i <= 'Z' ; i++) {
			if (list[i].size() >= 1) {
				right.add((char)i + "                  ");
				right.add("-------------------");
				for (String l : list[i]) {
					int sz = l.length();
					String add = "  " + l;
					for (int j = sz ; j < 17 ; j++) {
						add += ' ';
					}
					right.add(add);
				}
			}
		}		
		
		
		int size = Math.max(left.size(), right.size());
		if (left.size() < size) {
			for (int i = left.size() ; i < size ; i++) {
				left.add("                   ");
			}
		}
		if (right.size() < size) {
			for (int i = right.size() ; i < size ; i++) {
				right.add("                   ");
			}
		}
		
		String[] ret = new String[size];
		for (int i = 0 ; i < size ; i++) {
			ret[i] = left.get(i) + "  " + right.get(i);
		}
		return ret;
	}
}

SRM 354 DateFormat

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

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

  • 日付を4桁の数にエンコーディング
  • DPと経路復元(めんどい)をするだけ。
    • 状態は [今考えてる日付の位置][直前の日付]
      • 状態数は 2500 * 1300 ≒ 50^4 / 2 としてまぁ大丈夫でしょう。
      • そもそも使わない日付もあるんだし。(1050とか)
  • 月ごとの最大日付のインデックス指定をミスってハマる
import java.util.ArrayList;
import java.util.List;

public class DateFormat {
	int[] a, r;
	int[][] next;
	int[] daymonth = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

	public int dfs(int i, int prev) {
		if (i == a.length) {
			return 1;
		}
		if (next[i][prev] != 0) {
			if (next[i][prev] >= 1) {
				return 1;
			} else {
				return -1;
			}
		}
		
		int first = Math.min(a[i], r[i]);
		int second = Math.max(a[i], r[i]);
		boolean fv = isvalid(first) && (first > prev);
		boolean sv = isvalid(second)&& (second > prev);
		if (fv) {
			if (dfs(i+1, first) == 1) {
				next[i][prev] = first;
				return 1;
			}
		}
		if (sv) {
			if (dfs(i+1, second) == 1) {
				next[i][prev] = second;
				return 1;
			}
		}
		
		next[i][prev] = -1;
		return -1;
	}
	
	public boolean isvalid(int dat) {
		int month = dat / 100;
		if (month <= 0 || month >= 13) {
			return false;
		}
		int day = dat % 100;
		
		if (1 <= day && day <= daymonth[month]) {
			return true;
		}
		return false;
	}
	
	public String fromEuropeanToUs(String[] dateList) {
		String d = "";
		for (String x : dateList) {
			d += x;
		}
		String[] dates = d.split(" ");
		
		int len = dates.length;
		a = new int[len];
		r = new int[len];
		for (int i = 0 ; i < len ; i++) {
			String[] date = dates[i].split("/");
			a[i] = Integer.valueOf(date[0]) * 100 + Integer.valueOf(date[1]);
			r[i] = Integer.valueOf(date[1]) * 100 + Integer.valueOf(date[0]);
		}
		next = new int[len+1][1300];
		
		if (dfs(0, 0) == -1) {
			return "";
		}
		
		List<String> list = new ArrayList<String>();
		int nowi = 0;
		int nowprev = 0;
		while (nowi < len) {
			int nextdata = next[nowi][nowprev];
			int nmonth = nextdata / 100;
			int nday = nextdata % 100;
			String month = (nmonth <= 9) ? ("0" + nmonth) : ("" + nmonth);
			String day = (nday <= 9) ? ("0" + nday) : ("" + nday);
			list.add(month + "/" + day);
			nowi++;
			nowprev = nextdata;
		}
		
		String ans = "";
		for (String l : list) {
			ans += " " + l;
		}
		return ans.substring(1);
	}
}