Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 351 BoxesArrangement

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

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

  • 要は、A,B,Cをルールに則り並び替えた時元の位置と一致する最大数が分かればいい
    • 普通に数を並べるDPで書ける。
    • [Aを使った数][Bを使った数][Cを使った数][直前の文字][直前の文字が何個連続したか]
      • 多めに見積もって 51*51*51*4*4 = 2M程度。
  • 練習ではメモ化再帰で書こうとした
    • (文字数) >= 30 程度になると間に合わなくなったのでループDPに書き換え。
import java.util.Arrays;

public class BoxesArrangement {

	int[][][][][] memo = new int[51][51][51][4][4];
	int len;
	int[] otehon;
	int INF = 999999;
	int[] da = {1, 0, 0};
	int[] db = {0, 1, 0};
	int[] dc = {0, 0, 1};
	int[] ch;
	
	public int dfs(int a, int b, int c, int prev, int cont) {
		if (cont >= 3) {
			return INF;
		}
		if (memo[a][b][c][prev][cont] < INF) {
			return memo[a][b][c][prev][cont];
		}
		
		int ret = INF;
		int idx = (ch[0] - a) + (ch[1] - b) + (ch[2] - c);
		
		for (int d = 0 ; d < 3 ; d++) {
			int diff = (otehon[idx] == d) ? 0 : 1;
			int ta = a - da[d];
			int tb = b - db[d];
			int tc = c - dc[d];
			if (ta < 0 || tb < 0 || tc < 0) {
				continue;
			}
			if (prev == d) {
				ret = Math.min(ret, dfs(ta, tb, tc, d, cont+1) + diff);
			} else {
				ret = Math.min(ret, dfs(ta, tb, tc, d, 1) + diff);
			}
		}
		return ret;
	}
	
	public int maxUntouched(String boxes) {
		len = boxes.length();
		otehon = new int[len];
		ch = new int[3];
		for (int i = 0 ; i < len ; i++) {
			ch[boxes.charAt(i)-'A']++;
			otehon[i] = boxes.charAt(i)-'A';
		}
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				for (int k = 0 ; k < 51 ; k++) {
					for (int l = 0 ; l < 4 ; l++) {
						Arrays.fill(memo[i][j][k][l], INF);
					}
				}
			}
		}
		memo[0][0][0][3][0] = 0;
		for (int i = 0 ; i <= ch[0] ; i++) {
			for (int j = 0 ; j <= ch[1] ; j++) {
				for (int k = 0 ; k <= ch[2] ; k++) {
					int idx = i + j + k;
					if (idx >= len) {
						continue;
					}
					for (int l = 0 ; l < 4 ; l++) {
						for (int cont = 0 ; cont < 3 ; cont++) {
							if (memo[i][j][k][l][cont] >= INF) {
								continue;
							}
							int base = memo[i][j][k][l][cont];
							
							for (int d = 0 ; d < 3 ; d++) {
								int diff = (otehon[idx] == d) ? 0 : 1;
								int tocont = ((l == d) ? cont + 1 : 1);
								memo[i+da[d]][j+db[d]][k+dc[d]][d][tocont] = Math.min(memo[i+da[d]][j+db[d]][k+dc[d]][d][tocont], base + diff);
							}
						}
					}
				}
			}
		}
		
		int ret = INF;
		for (int l = 0 ; l < 4 ; l++) {
			for (int cont = 0 ; cont < 3 ; cont++) {
				ret = Math.min(memo[ch[0]][ch[1]][ch[2]][l][cont], ret);
			}
		}	
		return (ret == INF) ? -1 : (len - ret);
	}
}