Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-25SRM362, SRM363 (Practice)

SRM 362 PartialSeries

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

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

  • 経路復元付きDP
    • 状態数は [使った数字の組み合わせ][直前の数字][前回上がったか下がったかそのままか]
      • 2^15 * 11 * 3
  • 経路復元ができなくて死亡。
    • 他の人のコードを見て実装を勉強する
  • 解いた。
    • 辞書順最小で経路復元する必要がある場合はメモ化再帰で書くと見通しが良い
    • 状態も単純に [使った数字の組み合わせ][前回の数字][前々回の数字] として良い
      • その方が極値判定が楽で、バグが少なく実装できる
import java.util.Arrays;

public class PartialSeries {
	int[][][] memo;
	int[][][] next;
	int[] idxmap;
	int[] seq, avl;
	int ecnt;
	int len;
	int alen;
	
	public int ext(int a, int b, int c) {
		return (((a < b) && (b > c)) || ((a > b) && (b < c))) ? 1 : 0;
	}
	
	public int dfs(int idx, int ptn, int prev1, int prev2) {
		if (idx == len) {
			return 0;
		}
		
		if (seq[idx] == -1) {
			if (memo[ptn][prev1][prev2] != Integer.MAX_VALUE) {
				return memo[ptn][prev1][prev2];
			}
			int ret = Integer.MAX_VALUE;
			int best = -1;
			int besta = -1;
			for (int a = 0 ; a < alen ; a++) {
				if ((ptn & (1<<a)) == 0) {
					int nptn = ptn | (1<<a);
					int tr = dfs(idx+1, nptn, avl[a], prev1);
					int trext = ext(avl[a], prev1, prev2);
					if (idx <= 1) {
						trext = 0;
					}
					tr += trext;
					if (ret > tr) {
						ret = tr;
						best = avl[a];
						besta = a;
					} else if (ret == tr && best > avl[a]) {
						best = avl[a];
						besta = a;
					}
				}
			}
			next[ptn][prev1][prev2] = besta; 
			memo[ptn][prev1][prev2] = ret;
			return ret;
		}
		int ret = dfs(idx+1, ptn, seq[idx], prev1);
		int tr = ext(seq[idx], prev1, prev2);
		if (idx <= 1) {
			tr = 0;
		}
		return ret + tr;
	}
	
	public int[] getFirst(int[] series, int[] available) {
		seq = series;
		avl = available;
		len = series.length;
		alen = available.length;
		ecnt = 0;
		idxmap = new int[51]; 
		for (int i = 0 ; i < len ; i++) {
			if (series[i] == -1) {
				idxmap[ecnt] = i;
				ecnt++;
			}
		}
		
		memo = new int[1<<alen][11][11];
		next = new int[1<<alen][11][11];
		for (int i = 0 ; i < (1<<alen) ; i++) {
			for (int j = 0 ; j < 11 ; j++) {
				Arrays.fill(memo[i][j], Integer.MAX_VALUE);
				Arrays.fill(next[i][j], Integer.MAX_VALUE);
			}
		}
		
		dfs(0, 0, 0, 0);
		
		
		
		int now = 0;
		int nptn = 0;
		int val = seq[0];
		int prev1 = 0;
		int prev2 = 0;
		while (now < len) {
			while (now < len && seq[now] != -1) {
				val = seq[now];
				prev2 = prev1;
				prev1 = val;
				now++;
			}
			if (now >= len) {
				break;
			}
			
			int tptn = nptn;
			if (next[nptn][prev1][prev2] == Integer.MAX_VALUE) {
			} else {
				tptn |= (1<<next[nptn][prev1][prev2]);
				seq[now] = avl[next[nptn][prev1][prev2]];
			}
			val = seq[now];
			nptn = tptn;
			prev2 = prev1;
			prev1 = val;
			now++;
		}
		System.out.println(Arrays.toString(seq));
		return seq;
	}
}