[AtCoder] ARC 002 C – コマンド入力

2020年9月17日2020年12月13日

問題

方針

ショートカットは冗長に選んだとしても \( 4^4 \) 通りなので、全てのショートカットの組み合わせに対して必要なボタンの入力回数を求めます。ここで、\( d(i, 0) \) を \( i \) 文字をショートカットを使わずに打ち込んだときの入力回数の最小値として、\( d(i, 1) \) を\( i \) 文字をショートカットを使って打ち込んだときの入力回数の最小値とします。初期値は、

\begin{eqnarray}
d(0, 0) &=& 1\\
d(1, 0) &=& 2\\
\end{eqnarray}

であり、\( c_1c_2 = L \vee c_1c_2 = R \) であるとき、

\[ d(1, 1) = 1\]

となり、それ以外は \( \infty \) で初期化します。更新式は、ショートカットを使わないとき、

\[d(i, 0) = \min(d(i – 1, 0), d(i – 1, 1)) + 1\]

ショートカットを使える場合 \( (c_{i-1}c_{i} = L \vee c_{i-1}c_i = R) \)、

\[d(i, 1) = \min(d(i-2, 0), d(i-2, 1)) + 1\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
string c;
char t[4];
char g[] = {'A', 'B', 'X', 'Y'};
int best = 100000;

void solve() {
    int d[N][2]{};
    for (int i = 0; i < N; i++) {
        d[i][0] = N;
        d[i][1] = N;
    }
    d[0][0] = 1;
    d[1][0] = 2;
    if ((c[0] == t[0] && c[1] == t[1]) || (c[0] == t[2] && c[1] == t[3])) {
        d[1][1] = 1;
    }
    for (int i = 2; i < N; i++) {
        if ((c[i - 1] == t[0] && c[i] == t[1]) || ((c[i - 1] == t[2] && c[i] == t[3]))) {
            d[i][1] = min(d[i - 2][0], d[i - 2][1]) + 1;
        }
        d[i][0] = min(d[i - 1][0], d[i - 1][1]) + 1;
    }
    best = min(best, min(d[N - 1][0], d[N - 1][1]));
}

void dfs(int n) {
    if (n == 4) {
        if (t[0] == t[2] && t[1] == t[3]) return;
        solve();
        return;
    }
    for (int i = 0; i < 4; i++) {
        t[n] = g[i];
        dfs(n + 1);
    } 
}

int main() {
    cin >> N >> c;
    if (N <= 2) {
        cout << 1 << "\n";
        return 0;
    }
    dfs(0);
    cout << best << "\n";
    return 0;
}