Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

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