AtCoder Regular Contest #002 C : コマンド入力

問題概要

コマンド列を短くする最適の置換を求める問題。

解法

割り当てを全通り試してDP。貪欲にやっても良いので適当にreplaceしてlength調べるだけでも多分大丈夫なはず。

acceptされたコード

import std.stdio, std.array, std.algorithm, std.conv, std.string;

int N;
int[] cs;

void init(){
	N = to!int(readln.chomp);
	string t = readln.chomp;
	int[char] dict;
	foreach(int i, char c ; "ABXY"){
		dict[c] = i;
	}
	foreach(c; t){
		cs ~= dict[c];
	}
}

int solve(){
	
	immutable mask = 3;
	
	int ans = int.max;
	foreach(bit; 0..(4^^4)){
		auto L = [(bit>>0)&mask, (bit>>2)&mask], R = [(bit>>4)&mask, (bit>>6)&mask];
		int[] dp = new int[N + 1];
		dp[] = int.max;
		dp[0] = 0;
		
		foreach(i ; 0..N){
			dp[i+1] = min(dp[i+1], dp[i] + 1);
			if(i < N - 1){
				if( (L[0] == cs[i] && L[1] == cs[i+1]) || (R[0] == cs[i] && R[1] == cs[i+1]) ){
					dp[i+2] = min(dp[i+2], dp[i] + 1);
				}  
			}
		}
		
		ans = min(ans, dp[N]);
	}
	
	return ans;
}

void main(){
	init;
	writeln(solve);
}