ショートカットキー L と R は A, B, X, Y の4種類から重複を許して 2 つを選び一列に並べたものなので高々 
通りしかない．したがって，すべての L と R の割り当て方に対してコマンド列を最小にする置き換え方を求めることを考える．
現在 L と R はある値に固定されているとする．L と R を適切に置き換えることによって 
の長さを最小にするために動的計画法を用いる．dp[i] を部分コマンド列 
に対してショートカットキーを割り当てたときの長さの最小値とする．遷移方法はソースコードを参照．
計算時間： 
（
はコマンドに現れる文字列の種類数）
#include <bits/stdc++.h>
using namespace std;
int numPush(const string &s, const string &L, const string &R) {
const int n = s.size();
vector<int> dp(n + 1, n);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = min(dp[i], dp[i - 1] + 1);
if (s.substr(i - 2, 2) == L || s.substr(i - 2, 2) == R)
dp[i] = min(dp[i], dp[i - 2] + 1);
}
return dp.back();
}
int main() {
cin.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
string s;
cin >> s;
const string BUTTON = "ABXY";
int min_push = N;
for (auto l1 : BUTTON) {
for (auto l2 : BUTTON) {
for (auto r1 : BUTTON) {
for (auto r2 : BUTTON) {
string L = string(1, l1) + string(1, l2);
string R = string(1, r1) + string(1, r2);
min_push = min(min_push, numPush(s, L, R));
}
}
}
}
cout << min_push << endl;
return 0;
}
解法2．貪欲法
解法1の L と R が固定されているときに，上手く割り当てる方法を次のように貪欲的に選択する．
まで割り当てが済んでいるとする．
が L または R に等しい場合は を L または R に置き換えて 
を考える．等しくない場合は 
はそのままにして 
を考える．これをすべてのコマンド列を置き換えるまで貪欲的に行う．
TODO：AC はしたが未証明なので証明を行う
計算時間： （ はコマンドに現れる文字列の種類数）
#include <bits/stdc++.h>
using namespace std;
int numPush(const string &s, const string &L, const string &R) {
int num = 0;
for (size_t i = 0; i < s.size(); ++i) {
++num;
if (s.substr(i, 2) == L || s.substr(i, 2) == R) ++i;
}
return num;
}
int main() {
cin.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
string s;
cin >> s;
const vector<string> BUTTON = {"A", "B", "X", "Y"};
int min_push = N;
for (const auto &l1 : BUTTON) {
for (const auto &l2 : BUTTON) {
for (const auto &r1 : BUTTON) {
for (const auto &r2 : BUTTON) {
min_push = min(min_push, numPush(s, l1 + l2, r1 + r2));
}
}
}
}
cout << min_push << endl;
return 0;
}
貪欲法の証明は難しいことが多いので，出来ない場合はペナルティーが怖くなければ投げて，それ以外の証明が簡単な方法（動的計画法）が思いつけばそれを実装する．
