Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-21SRM394 (Practice)

mediumは幾何ゲー。投げた

253/605位

問題結果ポイントその他
250RoughStringsAccepted170弱ぐらいDP
600 CentersOfSymmetryOpened0.00
1000 PseudoRandomKingdomOpened0.00記念Open

SRM 394 RoughStrings

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

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

  • 文字列から最大n文字を削除した時、roughnessを最小化する
    • ある文字列のroughnessは、文字の最大出現回数 - 文字の最小出現回数 で計算する
  • 方針を検討
    • 貪欲で良さそう
    • たくさん出現する文字を順番に削っていけばいいんじゃない?
    • サンプルを見る。あれ?
      • レアな文字を削ったほうがいい場合もあるのか。
    • うーむ
  • そうだ、DPしよう
    • 貪欲かDPで迷ったら即DP
    • 各文字(26種)の数をカウントし、何文字ずつ削るかで探索しよう
    • 最大と最小をメモしておけばいいよね・・・
      • いやいや、最大を覚えさせておけばそれの最小を取っていけばいいはず
    • 状態数は dp[26][51][51] 余裕ですね
    • 問題の答えは j - dp[26][i][j] を全探索する
  • 実装
    • 元から存在しない文字に気をつけて場合分け
    • できた。
    • サンプル合わない。全部0ってどういうことなの・・・
      • 初期値が間違ってた。
    • 直したらサンプル通った。
  • 見直しフェーズ(5分)
    • あせるな、まだ提出しない。
    • 実装に問題はなさそう。
    • テスト
      • "aaaaa", 10 -> 0
      • "aaaaab", 3 -> 0
      • "aaabbbcd", 2 -> 0
      • "abcdefgg", 1 -> 0
    • ・・・大丈夫かな?
    • 出しちゃえ!
  • resubmit will result in 10% penalty...
    • えーっ、解いたことあったのか
    • 別に既視感はなかったけど・・・ これじゃポイントが分からない
    • 20分位経ってるから170点ぐらいかな・・・

public class RoughStrings {

	public int minRoughness(String s, int n) {
		char[] list = new char[26];
		
		int max = -55;
		int min = 55;
		for (int i = 0 ; i < s.length() ; i++) {
			list[s.charAt(i)-'a']++;
		}
		for (int j = 0 ; j < 26 ; j++) {
			if (list[j] != 0) {
				max = Math.max(max, list[j]);
				min = Math.min(min, list[j]);
			}
		}
		int rough = max - min;
		
		// idx, deleted, max
		int[][][] dp = new int[27][101][101];
		for (int i = 0 ; i < 27 ; i++) {
			for (int j = 0 ; j < 101 ; j++) {
				for (int k = 0 ; k < 101 ; k++) {
					dp[i][j][k] = Integer.MIN_VALUE;
				}
			}
		}
		
		dp[0][0][0] = 51;
		for (int i = 0 ; i < 26 ; i++) {
			for (int j = 0 ; j <= n ; j++) {
				for (int k = 0 ; k < 51 ; k++) {
					if (dp[i][j][k] != Integer.MIN_VALUE) {
						if (list[i] == 0) {
							dp[i+1][j][k] = Math.max(dp[i+1][j][k], dp[i][j][k]);
						} else {
							for (int del = 0 ; del < list[i] ; del++) {
								int left = list[i] - del;
								int newk = Math.max(k, left);
								int newj = j+del;
								int newvalue = dp[i][j][k];
								if (dp[i][j][k] > left && left > 0) {
									newvalue = left;
								}
								
								if (newj <= n) {
									dp[i+1][newj][newk] = Math.max(dp[i+1][newj][newk], newvalue);
								}
							}
							if (j + list[i] <= n) {
								dp[i+1][j+list[i]][k] = Math.max(dp[i+1][j+list[i]][k], dp[i][j][k]);
							}
						}
					}
				}
			}
		}
		
		int minrough = rough;
		for (int j = 0 ; j <= n ; j++) {
			for (int k = 1 ; k < 51 ; k++) {
				if (dp[26][j][k] != Integer.MIN_VALUE) {
					minrough = Math.min(minrough, k - dp[26][j][k]);
				}
			}
		}	
		return minrough;
	}
}