Codeforces ECR #074 : E. Keyboard Purchase

この回、AC数の減少が割と理想的？
https://codeforces.com/contest/1238/problem/E

問題

アルファベットの先頭M種類で構成されたN文字の文字列Sが与えられる。
今、M個のキーを横1列に並べたキーボードでこの文字を入力することにする。
任意の順でキーを並べられるとき、左右に指を動かす最小距離はキー何個分か。

解法

まずSにおける2文字の並びを見て、
f(a,b) := aの次にbのキーを打つ回数
を先に列挙しよう。
次に
g(mask) := キーのprefixをmaskに示すbitmaskまで並べたとき、その時点で確定している移動回数の最小値
としてこれを求めよう。
g(0)=0とする。

今maskに含まれないキーcを1個選んだとする。
g(mask^(1<

int N,M;
string S;

int num[26][26];
int dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	FOR(i,N-1) {
		num[S[i]-'a'][S[i+1]-'a']++;
		num[S[i+1]-'a'][S[i]-'a']++;
	}
	
	
	int mask;
	for(mask=1;mask<1<<M;mask++) {
		int sum=0;
		dp[mask]=1<<30;
		FOR(x,M) if(mask&(1<<x)) FOR(y,M) if(!(mask&(1<<y))) sum+=num[x][y];
		FOR(i,M) if(mask&(1<<i)) dp[mask]=min(dp[mask],dp[mask^(1<<i)]+sum);
	}
	
	cout<<dp[(1<<M)-1]<<endl;
	
	
}

まとめ

割と典型な気がする。
Mの上限で気づくよね。