Facebook Hacker Cup 2016 Round 2 Boomerang Decoration

Boomerang Decoration

問題

文字列$a,b$が与えられる。 prefixとsuffixをそれぞれ何らかの文字で塗り潰す変換$a = (a_1, a_2, \dots, a_n) \to a’ = (x, x, x, \dots, x, a_i, a_{i+1}, a_{i+2}, \dots, a_{j-1}, a_j, y, y, y, \dots y)$ができる。 これを繰り返し、文字列$a$を$b$に変換するとき、変換は最小で何回必要か。

解法

貪欲に両側から塗っていって、完成したら終了。$O(n)$。

実装

実験したところstring.operator !=でも間に合うようなのでさぼった。$O(n^2)$。

#include <iostream>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
void solve() {
    int n; string a, b; cin >> n >> a >> b;
    int ans = 0;
    for (int i = 0, j = n-1; a != b; ++ ans) {
        int pi = i; while (i <  n and b[i] == b[pi]) { a[i] = b[i]; ++ i; }
        int pj = j; while (j >= 0 and b[j] == b[pj]) { a[j] = b[j]; -- j; }
    }
    cout << ans << endl;
}
int main() {
    int testcases; cin >> testcases;
    repeat (testcase, testcases) {
        cout << "Case #" << testcase+1 << ": ";
        solve();
    }
    return 0;
}