AGC 039 | A - Connection and Disconnection

問題

https://atcoder.jp/contests/agc039/tasks/agc039_a

考えたこと

(ほとんど解説と同じ)

すべて同じ文字列の場合以下のようになる。文字列の長さを$n$とすると$\lfloor \frac{n}{2} \rfloor$で求められる。

どれかの文字がことなる場合はまずSで何回変更が必要かカウントする。それを$l$とする。

$S$の先頭と末尾が異なる文字なら以下のようになり、答えは$l \times K$で求められる。

$S$の先頭と末尾が異なる文字なら以下のようになる。

先頭の連続する文字数を$a$、末尾の連続する文字数を$b$とすると答えは以下で求められる。

$$k * l - (k -1) \times ( \lfloor \frac{a+b}{2} \rfloor - ( \lfloor \frac{a}{2} \rfloor + \lfloor \frac{b}{2} \rfloor ))$$

コード

実装時のTips

• 特に難しくない。条件をうまく整理できればよい。
• 文字を変更したかどうかは小文字以外をおけばいい。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll k;
  string s;
  cin >> s >> k;
  const int n = s.size();

  ll a = 1, b = 1;
  for (int i = 0; i < n - 1; i++) {
    if (s[i] == s[i + 1]) {
      a++;
    } else {
      break;
    }
  }
  for (int i = n - 1; i > 0; i--) {
    if (s[i] == s[i - 1]) {
      b++;
    } else {
      break;
    }
  }
  if (a == n) {  // 全部同じ場合
    cout << a * k / 2 << endl;
    return 0;
  }
  ll l = 0;
  for (int i = 1; i < n; i++) {
    if (s[i] == s[i - 1]) {
      l++;
      s[i] = '-';
    }
  }
  if (s[0] != s[n - 1]) {
    cout << l * k << endl;
    return 0;
  }

  cout << k * l + (k - 1) * ((a + b) / 2 - (a / 2 + b / 2)) << endl;
}

参考

• https://atcoder.jp/contests/agc039/tasks/agc039_a/editorial