Codeforces Round 879 (Div. 2) - C. Game with Reversing

C. Game with Reversing

Bob 이 두 번 뒤집는건 어떻게 뒤집어도 결과에 아무런 영향을 끼칠 수 없다.

두 가지 정답을 고려한다.

하나는 $s_i \neq t_i$ 의 개수를 세는 것이고 하나는 $s_i \neq t_{n-1-i}$ 의 개수를 세는 것이다.

그것의 개수를 $c$ 라 하자.

전자에선 $c$가 짝수라면 Bob 이 뒤집는 것에 따라 딱 맞게 끝낼 수 있으므로 $2c$ 가 정답이다.

$c$가 홀수라면 $2c-1$ 이 되어야 한다. 밥이 뒤집은 다음 마지막 한 번으로 Alice가 끝내면 된다.

후자라면 $c$가 홀수라면 딱 맞게 끝내므로 $2c$ 가 정답이고 반대로 짝수일 때 $2c-1$ 이 된다.

그런데 후자인 경우 최소 정답은 $2$인것을 고려해주어야 한다.

void solve() {
   int n;
   string s, t;
   cin >> n >> s >> t;
   if (s == t) {
      cout << 0 << endl;
      return;
   }
 
   int ans1 = 0, ans2 = 0;
 
   // 가장 마지막에 바꿔도 된다.
   int odd = n % 2 && s[n / 2] != t[n / 2];
   for (int i = 0; i < n; i++) {
      if (s[i] != t[i])ans1++;
   }
   for (int i = 0; i < n; i++) {
      if (s[i] != t[n - 1 - i]) ans2++;
   
 
   if (ans1 % 2 == 0) {
      ans1 = ans1 + ans1;
   } else {
      ans1 = ans1 + ans1 - 1;
   }
 
   if (ans2 % 2 == 0) {
      ans2 = ans2 + ans2 - 1;
   } else {
      ans2 = ans2 + ans2;
   }
 
   cout << min(ans1, max(2ll, ans2)) << endl;
}