Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-09SRM383,384,385 (Practice)

SRM383 (Practice)

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

三本目。 Mediumが既視だったのでノーコン。

問題結果ポイントその他
250PlanksAccepted219.42全探索
500FloorBoardsAccepted262.13最強最速アルゴリズマー
1000PyramidPuzzleOpened0.00解ける気がしない

SRM 383 Planks

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

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

  • 方針を検討
    • 切る長さを決め打ちして全探索でいこう
  • 実装
    • 切る長さでちょうど割り切れる場合に注意する。うなうな
  • 最後のサンプルだけ通らない。
    • 切らないほうが得する場合もあるのか
    • サンプル親切だなぁ
    • ある板について、切断コストが得られる利益を上回ってればパスするよう変更
  • 提出
public class Planks {

	public int makeSimilar(int[] lengths, int costPerCut, int woodValue) {
		int max = 0;
		int len = lengths.length;
		for (int l = 1 ; l <= 10000 ; l++) {
			int pieces = 0;
			int costs = 0;
			for (int i = 0 ; i < len ; i++) {
				if (lengths[i] < l) {
					continue;
				} else {
					int p = lengths[i] / l;
					int c = p;
					if (lengths[i] % l == 0) {
						c--;
					}
					if (p * woodValue * l <= costPerCut * c) {
						continue;
					}
					pieces += p;
					costs += c;
				}
			}
			max = Math.max(max, woodValue * pieces * l - costPerCut * costs);
		}
		return max;
	}
}

SRM 383 FloorBoards

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

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

  • 既視感がある問題。
  • 方針を検討
    • 解説ではO((2^W)^2 * H)の動的計画法(ループ)で解いてるが、今回はメモ化再帰で解いてみよう
    • dfs(i, j, ptn) i行目j列目において、直前W個の縦横線のパターンptnについて考える
      • 縦棒を使うか横棒を使うかという選択は直前W個さえ知ってれば十分
      • 計算量 O(W*H*(2^W))
  • 実装
  • サンプル全然合わない。なぜだー
    • 次の状態を見る時 dfs(i, j+1, ptn*2) ではなく dfs(i+1, j, ptn*2)としてた・・・
    • その他にもいろいろ間違ってた
  • サンプル通った。最大ケース確認して提出
    • 見たことある問題の割に解くのが遅い・・・
import java.util.Arrays;

public class FloorBoards {

	char[][] r;
	int[][][] memo;
	int h;
	int w;
	int wptn;
	
	public int dfs(int i, int j, int ptn) {
		if (i >= h) {
			return 0;
		}
		if (j >= w) {
			return dfs(i+1, 0, ptn);
		}
		if (memo[i][j][ptn] != Integer.MAX_VALUE) {
			return memo[i][j][ptn];
		}
		
		int ans = Integer.MAX_VALUE;
		if (r[i][j] == '#') {
			ans = dfs(i, j+1, (ptn*2) & wptn);
		} else {
			int vertical = 0;
			if (i == 0 || r[i-1][j] == '#' || (ptn & (1<<(w-1))) >= 1) {
				vertical = 1;
			}
			
			int holizonal = 0;
			if (j == 0 || r[i][j-1] == '#' || (ptn & 1) == 0) {
				holizonal = 1;
			}

			ans = Math.min(ans, dfs(i, j+1, (ptn*2) & wptn) + vertical);
			ans = Math.min(ans, dfs(i, j+1, (ptn*2+1) & wptn) + holizonal);
		}
		memo[i][j][ptn] = ans;
		return ans;
	}
	
	public int layout(String[] room) {
		h = room.length;
		w = room[0].length();
		
		r = new char[h][w];
		for (int i = 0 ; i < h ; i++) {
			r[i] = room[i].toCharArray();
		}
		
		memo = new int[h][w][1<<w];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				Arrays.fill(memo[i][j], Integer.MAX_VALUE);
			}
		}
		wptn = (1<<w)-1;
		return dfs(0, 0, wptn);
	}
}

SRM384 (Practice)

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

本日二本目。 57/390位

問題結果ポイントその他
250LibraryAccepted243.87早解きを意識
500SchoolTripAccepted258.80非常に小さい確率は無視出来る
1000ChessTrainingOpened0.00問題を見てそっと閉じた

SRM 384 Library

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

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

  • 方針を検討
    • 条件に合うDocumentを数えればいいらしい
    • 同じDocumentを数えてしまわないようにSetで管理する
import java.util.HashSet;
import java.util.Set;

public class Library {

	public int documentAccess(String[] records, String[] userGroups, String[] roomRights) {
		int cnt = 0;
		Set<String> done = new HashSet<String>();
		for (String r : records) {
			String[] data = r.split(" ");
			boolean isok = false;
			for (String user : userGroups) {
				for (String rr : roomRights) {
					if (data[1].equals(rr) && data[2].equals(user)) {
						isok = true;
					}
				}
			}
			if (isok) {
				if (!done.contains(data[0])) {
					done.add(data[0]);
					cnt++;
				}
			}
		}
		return cnt;
	}
}

SRM 384 SchoolTrip

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

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

  • 方針を検討
    • また制約甘い系か・・・
    • ボールを持ってる人、生き残ってる人のビットパターンでDPしちゃおう
    • dfsで書くのが楽だよね
  • 実装
    • これ一周誰もヒットせずに同じ人に戻って来ちゃう場合もあるのか。
      • どうしよう・・・ これだとdfsが終わらない
    • しばらく考える。数式に落としてみたりとか。
      • うまくいかない・・・
  • 制約を見る。
    • ヒット率は最低でも0.1以上
    • 0.9 ^ 200 < 10^-9 だから、200回以上連続でヒットしなかった場合の確率はほぼ0で、答えの要求する精度に対して無視出来る
    • 計算量的に余裕あるし、500回以上ヒットしなかったら0を返すようにしよう
  • サンプル通った。
    • 最大ケース {10, 10, 10, 10, 10, 10} で確認
      • 0.1sで通った。余裕
  • 出した
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SchoolTrip {

	int len;
	double[] prob;
	double[][][] memo;

	public double dfs(int now, int ptn, int cnt) {
		if (Integer.bitCount(ptn) == len - 1) {
			return 0.0d;
		}
		if (memo[now][ptn][cnt] >= 0.0d) {
			return memo[now][ptn][cnt];
		}
		if ((ptn & (1<<now)) >= 1) {
			return dfs((now+1)%len, ptn, cnt);
		}
		if (cnt >= 500) {
			return 0.0d;
		}
		
		double mintime = Double.MAX_VALUE;
		for (int t = 0 ; t < len ; t++) {
			if (t != now && (ptn & (1<<t)) == 0) {
				double proba = prob[now] * (dfs((now+1) % len, ptn | (1<<t), 0) + 1.0d);
				double probb = (1.0d - prob[now]) * (dfs((now+1) % len, ptn, cnt + 1) + 1.0d);
				mintime = Math.min(mintime, proba + probb);
			}
		}
		memo[now][ptn][cnt] = mintime;
		return mintime;
	}
	
	
	public double duration(int[] probability) {
		len = probability.length;
		prob = new double[len];
		for (int p = 0 ; p < len ; p++) {
			prob[p] = probability[p] * 1.0d / 100;
		}
		
		memo = new double[len][1<<len][501];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < (1<<len) ; j++) {
				Arrays.fill(memo[i][j], -1.0d);
			}
		}
		return dfs(0, 0, 0);
	}
}

SRM385 (Practice)

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

Petr回 153/563位

問題結果ポイントその他
250UnderscoreJustificationAccepted167.30相変わらず素早く解けない
500TurningMazeAccepted262.97実装重めダイクストラ
1100InfiniteAdditionUnopened0.00辿りつけなかった

SRM 385 UnderscoreJustification

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

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

  • 方針を検討
    • コーナーケースとかこわいし、各文字列の間にアンダースコアを何個配るかでDPしちゃおう
    • 計算量は O(文字列数 * アンダースコアの数 ^ 2) まぁ余裕
  • 実装
  • サンプル通らない。
    • なんで!?自分の解が間違ってるとは思えない。
    • 問題を読みなおしてみる
      • なるほど・・・、なるべくアンダースコアを均等に配らなきゃなのか
    • これひょっとしてDPしなくてもいけたんじゃ・・・
  • アンダースコアを使う数を2つに制限するようにDPを書き換える
    • サンプル通った。
  • 出した

public class UnderscoreJustification {
	String[][] dp;
	String[] w;
	String[] ucs;
	int[] canuse;

	public boolean isbetter(String a, String b) {
		int len = Math.min(a.length(), b.length());
		for (int i = 0 ; i < len ; i++) {
			if (a.charAt(i) < b.charAt(i)) {
				return false;
			} else if (a.charAt(i) > b.charAt(i)) {
				return true;
			}
		}
		if (a.length() <= b.length()) {
			return false;
		}
		return true;
	}
	
	public String dfs(int idx, int left) {
		if (left < 0) {
			return null;
		}
		String ans = w[idx];
		if (idx == w.length - 1) {
			if (left == 0) {
				return ans;
			} else {
				return null;
			}
		}
		if (dp[idx][left] != null) {
			return dp[idx][left];
		}
		
		String fastest = "~";
		for (int i = 0 ; i < 2 ; i++) {
			int u = canuse[i];
			String res = dfs(idx+1, left-u);
			if (res != null) {
				res = ucs[u] + res;
				if (isbetter(fastest, res)) {
					fastest = res;
				}
			}
		}
		if ("~".equals(fastest)) {
			return null;
		}
		
		dp[idx][left] = ans + fastest;
		return dp[idx][left];		
	}
	
	
	public String justifyLine(String[] words, int width) {
		w = words;
		String line = "";
		for (String wd : words) {
			line += wd;
		}
		int underlen = width - line.length();
		
		canuse = new int[2];
		canuse[0] = underlen / (w.length - 1);
		canuse[1] = canuse[0];
		if (underlen % (w.length - 1) != 0) {
			canuse[1] += 1;
		}
		
		int wlen = words.length;
		dp = new String[width+1][underlen+1];
		
		ucs = new String[underlen+1];
		ucs[0] = "";
		for (int i = 1 ; i <= underlen ; i++) {
			ucs[i] = ucs[i-1] + "_";
		}
		return dfs(0, underlen);
	}
}

SRM 385 TurningMaze

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

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

  • 方針を検討
    • 制約甘い・・・またbitDPか
    • どの行と列が反転してるかのフラグを持ちながらダイクストラすればよさそうだ
      • 状態数は 2^14 * 7 * 7
    • 今いる位置(nx, ny, 0-indexed)で反転操作を行うと、nx桁目とny+7桁目のbitを入れ替える
    • 今いる位置が反転してるかどうかは、nx桁目とny+7桁目のXORをとって確認する
  • 実装
    • 重い・・・
    • 各部屋の状態について、ドアが使えるかどうか配列を用意するなど工夫した
  • 最後のサンプルだけが通らない 正解「6」に対して「4」を返した
    • 手で確認してみる
    • あれ、これ4手(下、右、右、下)でいけるのでは・・・
  • 問題を読みなおす
    • そうか、ドアがつながってなきゃ通れないのか
      • 南に行くときは南の部屋の北のドアがないと通れない
  • 行き先のドアについても調べる実装を追加
    • サンプル通った。
  • 念のため最大ケース(7x7, ABCDランダム)で確認
    • TCサーバで0.4s 大丈夫だろう。
  • 提出
  • editorial曰くただのBFSで通るらしい
Constant