Facebook Hacker Cup 2016 Round 2 Boomerang Decoration
Facebook Hacker Cup 2016 Round 2 に参加しました。Round 3 に進めないのは仕方ないですが T シャツもらえないのは残念。
解法
左側と右側, どこで区切るかで場合分けします。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; }