Facebook Hacker Cup 2016 Round 2 Boomerang Decoration

Facebook Hacker Cup 2016 Round 2 に参加しました。Round 3 に進めないのは仕方ないですが T シャツもらえないのは残念。

問題

https://www.facebook.com/hackercup/problem/424794494381569/

解法

左側と右側, どこで区切るかで場合分けします。i 番目まで左側で処理し, それ以降は右側で処理するとすると, max(左の処理数, 右の処理数) が答えです。

const int MAXN = 100010;
const int INF = 1e8;
int dp[MAXN];

vector<int> calc(const string& s, const string& t, int N) {
    char prev = '?';
    int now = 0, cnt = 0;
    vector<int> ret(N);
    for (int i = 0; i < N; i++) {
        if (prev != t[i]) cnt++;
        prev = t[i];
        if (s[i] != t[i]) now = cnt;
        ret[i] = now;
    }
    return ret;
}

void solve(int T) {
    int N;
    cin >> N;
    string s, t;
    cin >> s;
    cin >> t;
    vector<int> left = calc(s, t, N);
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    vector<int> right = calc(s, t, N);
    int ans = right[N-1];
    for (int i = 0; i < N; i++) {
        int r = (i==N-1) ? 0 : right[N-i-2];
        ans = min(ans, max(left[i], r));
    }
    cout << "Case #" << T << ": " << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}