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