Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

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