Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM380 (Practice)

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

1完爆死 225/465位

問題結果ポイントその他
250LameKnightAccepted175.79数学ゲー
500CompilingDecksWithJokersOpened0.00数学ゲー?
1000NestedDiamondsUnopened0.00見てない

SRM 380 LameKnight

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

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

  • コーナーケースに注意して場合分け。
public class LameKnight {

	public int maxCells(int height, int width) {
		if (height == 1 || width == 1) {
			return 1;
		}
		if (height == 2) {
			return Math.min(3, (width - 1) / 2) + 1;
		}
		int cnt = 0;
 		if (width >= 7) {
			int lw = width - 7;
			cnt = 4 + lw;
		}
		return Math.max(cnt, Math.min(3, width - 1)) + 1;
	}
}

SRM 380 CompilingDecksWithJokers

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

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

  • 圧倒的数学ゲー
    • いい問題
  • カードの残り数でソート
    • 一番小さな数 a が n個あって、その次に大きな数がb個あったら・・・
    • aとbが等しくなるには何枚ジョーカーを使う必要があるかで式を立ててゴニョゴニョ
  • n=1かつa=0のときに注意する
import java.util.Arrays;

public class CompilingDecksWithJokers {

	public int maxCompleteDecks(int[] cards, int jokers) {
		int len = cards.length;
		if (len == 1) {
			return cards[0] + jokers;
		}
		
		long cnt = 0;
		Arrays.sort(cards);
		while (jokers >= 1 && (cards[0] >= 1 || cards[1] >= 1)) {
			int samecnt = 0;
			long secondcnt = Integer.MAX_VALUE;
			for (int i = 0 ; i < len ; i++) {
				if (cards[i] == cards[0]) {
					samecnt++;
				}
			}
			if (samecnt < len) {
				secondcnt = cards[samecnt];
			}
			long willdo = Math.min(Math.min(secondcnt, jokers), (0L + secondcnt - cards[0]) * samecnt);
			if (samecnt >= 2) {
				willdo = Math.min(willdo, 1L * cards[0] * samecnt / (samecnt - 1));
			}
			long dec = 0, mod = 0;
			dec = willdo - willdo / samecnt;
			mod = willdo % samecnt;
			for (int i = 0 ; i < len ; i++) {
				if (i < samecnt) {
					cards[i] -= ((i < mod) ? (dec - 1) : dec);
				} else {
					cards[i] -= willdo;
				}
			}
			jokers -= willdo;
			cnt += willdo;
			Arrays.sort(cards);
		}
		Arrays.sort(cards);
		return (int) (cnt + cards[0]);
	}
}

SRM381 (Practice)

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

2本目。そこそこの速さで2完できた 47/577位

問題結果ポイントその他
250TheDiceGameAccepted210.09動的計画法
500TheHomeworkAccepted313.22メモ化再帰
1000TheSquaresOpened0.00-

SRM 381 TheDiceGame

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

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

  • あ、Theの人だ(Vasyl回)
  • 方針を検討
    • 数学ゲーと思いきや、制約ゆるい(N <= 1,000,000)のでDPしようかな
    • メモ化再起で書くとStack Overflowしそうなのでループで書く
  • 実装
    • もらうDPをループで書くのに慣れてなくてしばらく戸惑う・・・
      • メモ化再帰で書けるなら直感的にかけて好きなのに
  • サンプル通った
    • 最大ケースでチェック。提出
import java.util.Arrays;

public class TheDiceGame {
	public double expectedThrows(int candies) {
		double[] dp = new double[1000010];
		double p = 1.0d / 6;

		for (int n = 0 ; n <= candies ; n++) {
			for (int a = 1 ; a <= 6 ; a++) {
				if (n - a >= 1) {
					dp[n] += (dp[n-a] + 1.0d) * p;
				} else {
					dp[n] += p;
				}
			}
		}
		return dp[candies];
	}
}

SRM 381 TheHomework

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

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

  • 方針を検討
    • うーむ
    • まず、サンプルが理解出来ない
      • 例えばsample3。これ挿入が9回と削除が2回必要で、どう考えても4回の操作でできるはずがないのだが
    • 問題文に戻ってみる。しばらく理解できなくて悩む
  • あっ
    • 複数回の挿入・削除・変更をまとめて1回と数えるのか
    • sample3なら
{12,13}
{12,13,1,1}
{12,13,1,1,1,1,1,1}
{12,13,1,1,1,1,1,1,1,1,1}
{1,1,1,1,1,1,1,1,1}
    • で4回
    • そうと分かれば話は簡単。
    • 「現在の長さ」「余分な物の数」「必要なものの数」を状態に持って探索してやればいい
  • 実装
    • dfsでメモ化再帰を実装
    • 必要なものの数以上に数を足すと、余分なものが増えるが・・・
      • 余分なものを増やしたほうが得する場合はあるのだろうか
      • 逆に、必要なものを削ったほうが得する場合はあるのだろうか
    • とりあえずない気がするのでそのケースは考えないでおく
  • サンプル通った。
    • 配列サイズチェック
    • 追加テスト
      • {1}, {2}x50
      • {2}x50, {1}
      • {1}x50, {2}x50
  • 多分大丈夫。提出
    • 提出後、余分な操作について考える
    • 余計なことをすると、余計なことをした分の埋め合わせ操作が必要になる気がするなぁ
    • ということで多分今のコードで大丈夫だ。
import java.util.Arrays;

public class TheHomework {
	int[][][] memo;
	int fl, sl;
	int INF = Integer.MAX_VALUE;
	
	public int dfs(int now, int g, int n) {
		if (now == sl && g == 0 && n == 0) {
			return 0;
		}
		if (memo[now][g][n] != INF) {
			return memo[now][g][n];
		}
		
		int minop = INF;
		
		// add
		for (int a = 1 ; a <= now ; a++) {
			int newn = n - a;
			int newg = g;
			if (newn < 0) {
				continue;
			}
			minop = Math.min(minop, dfs(now + a, newg, newn) + 1);
		}
		
		// delete
		for (int d = 1 ; d <= now / 2 ; d++) {
			int newg = g - d;
			int newn = n;
			if (newg < 0) {
				continue;
			}
			minop = Math.min(minop, dfs(now - d, newg, newn) + 1);
		}
		
		// chnage
		for (int c = 1 ; c <= now / 2 ; c++) {
			int newg = g - c;
			int newn = n - c;
			if (newg < 0 || newn < 0) {
				continue;
			}
			minop = Math.min(minop, dfs(now, newg, newn) + 1);
		}
		
		memo[now][g][n] = minop;
		return minop;
	}
	
	public int transform(int[] first, int[] second) {
		fl = first.length;
		sl = second.length;
		int need = 0;
		int garb = 0;
		
		boolean[] matchedF = new boolean[fl];
		boolean[] matchedS = new boolean[sl];
		for (int i = 0 ; i < fl ; i++) {
			for (int j = 0 ; j < sl ; j++) {
				if (first[i] == second[j]) {
					if (!matchedF[i] && !matchedS[j]) {
						matchedF[i] = true;
						matchedS[j] = true;
					}
				}
			}
		}
		
		for (int i = 0 ; i < fl ; i++) {
			if (!matchedF[i]) {
				garb++;
			}
		}
		for (int i = 0 ; i < sl ; i++) {
			if (!matchedS[i]) {
				need++;
			}
		}
		
		memo = new int[200][101][101];
		for (int i = 0 ; i < 200 ; i++) {
			for (int j = 0 ; j < 101 ; j++) {
				Arrays.fill(memo[i][j], INF);
			}
		}		
		int ret = dfs(fl, garb, need);		
		return (ret == INF) ? -1 : ret;
	}
}

SRM382 (Practice)

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

2完ならず。mediumは難しくなかったが解けなかった・・・ 173/438位

問題結果ポイントその他
250CollectingRidersAccepted150.17前計算して全探索
500PointsOnACircleOpened0.00グラフ
1000CharmingTicketsUnopened0.00見てない

SRM 382 CollectingRiders

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

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

  • 方針を検討
    • とりあえず、dx,dy進むのにかかる手数を前計算してしまおう
  • 実装
    • BFSで実装。OFFSET = 15, MAX = 30 ぐらいでゴリゴリ書く
  • いや待て、壁があるからそう単純にはできない
    • やはり、(a,b)から(c,d)に進む最小手数を全部計算する必要が有りそうだ。
      • だが、最大サイズは10なので十分間に合うだろう。
  • 実装
    • 書いてしまったBFSの部分を使いまわす
    • 境界判定に番兵用意したいけど、最大2マス進めるし配列番号の扱いも面倒になりそうなので、愚直にif文で判定することにした
  • できた。サンプル通った。
  • コーナーケース確認して提出。

import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class CollectingRiders {
	class State {
		int nx;
		int ny;
		int time;
		State(int x, int y, int t) {
			nx = x;
			ny = y;
			time = t;
		}
	}
	
	public int minimalMoves(String[] board) {
		int w = board[0].length();
		int h = board.length;

		int[] dx = {1, 1, 2, 2, -1, -1, -2, -2};
		int[] dy = {2, -2, 1, -1, 2, -2, 1, -1};
		int[][][][] dp = new int[h][w][h][w];
		for (int i = 0 ; i < dp.length ; i++) {
			for (int j = 0 ; j < dp[0].length ; j++) {
				for (int k = 0 ; k < dp[0][0].length ; k++) {
					Arrays.fill(dp[i][j][k], Integer.MAX_VALUE);
				}
			}
		}

		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				Queue<State> q = new ArrayBlockingQueue<State>(1000);
				q.add(new State(j, i, 0));
				dp[i][j][i][j] = 0;
				while (q.size() >= 1) {
					State stat = q.poll();
					for (int d = 0 ; d < 8 ; d++) {
						int tx = stat.nx + dx[d];
						int ty = stat.ny + dy[d];
						if (0 <= tx && tx < w && 0 <= ty && ty < h) {
							if (dp[i][j][ty][tx] > stat.time + 1) {
								dp[i][j][ty][tx] = stat.time + 1;
								q.add(new State(tx, ty, stat.time + 1));
							}
						}
					}
				}
			}
		}
		int minmove = Integer.MAX_VALUE;
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				int move = 0;
				search: for (int k = 0 ; k < h ; k++) {
					for (int l = 0 ; l < w ; l++) {
						if (i == k && j == l) {
							continue;
						}
						if (board[k].charAt(l) != '.') {
							int knight = board[k].charAt(l) - '0';
							int go = dp[k][l][i][j];
							if (go == Integer.MAX_VALUE) {
								move = Integer.MAX_VALUE;
								break search;
							}
							move += (go + knight - 1) / knight;
						}
					}
				}
				minmove = Math.min(minmove, move);
			}
		}
		return (minmove == Integer.MAX_VALUE) ? -1 : minmove;
	}
}

SRM 382 PointsOnACircle

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

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

  • 方針を検討
    • とりあえず、1度から359度回してみて一番いいのを選べばいいだろう
    • グラフにしてみるとフローで解けるかな?
      • 0〜359までのノードを考え、赤と青のノードに分割して考える
  • サンプル合わない・・・
    • 同じノードを2回使ってしまっていることに気づく。
    • フローじゃ解けない
    • いやそもそもフローなんて高等なもの使わなくていい気がする。
      • 一つの点からは高々一つの点にしかいかないんだし・・・
  • しばらく唸って時間切れ。

その後

  • 単純に、連結してるノードを数えてやればいいだけだった
    • ノードは単純に分割せず考える
    • ループが発生する場合に注意する
import java.util.Arrays;

public class PointsOnACircle {
	public int color(String[] points) {
		String line = "";
		for (String s : points) {
			line += s;
		}
		String[] data = line.split(" ");
		int len = data.length;
		int[] a = new int[len];
		int[] idmap = new int[361];
		Arrays.fill(idmap, -1);
		for (int i = 0 ; i < len ; i++) {
			a[i] = Integer.valueOf(data[i]);
		}
		Arrays.sort(a);
		for (int i = 0 ; i < len ; i++) {
			idmap[a[i]] = i;
		}
		if (len <= 1) {
			return 0;
		}
		
		int maxpair = 0;
		for (int r = 1 ; r <= 359 ; r++) {
			int[] next = new int[len];
			Arrays.fill(next, -1);
			boolean[] ishead = new boolean[len];
			Arrays.fill(ishead, true);
			for (int i = 0 ; i < len ; i++) {
				int go = (a[i] + r + 360) % 360;
				if (idmap[go] != -1) {
					next[i] = idmap[go];
					ishead[idmap[go]] = false;
				}
			}
			int pairs = 0;
			for (int i = 0 ; i < len ; i++) {
				if (ishead[i]) {
					int cnt = 1;
					int cur = i;
					while (next[cur] != -1) {
						cnt++;
						cur = next[cur];
					}
					pairs += cnt / 2;
				}
			}

			boolean[] visited = new boolean[len];
			for (int i = 0 ; i < len ; i++) {
				if (!ishead[i] && next[i] != -1 && !visited[i]) {
					int cnt = 0;
					int cur = i;
					do {
						visited[cur] = true;
						cnt++;
						cur = next[cur];
					} while (cur != -1 && cur != i);
					if (cur == i) {
						pairs += cnt / 2;
					}
				}
			}
			maxpair = Math.max(maxpair, pairs);
		}
		return maxpair*2;
	}
}