【解答例】AGC 039 A - Connection and Disconnection

atcoder.jp

制約

1 ≤ | S | ≤ 100
1 ≤ K ≤ 10⁹

考えたこと

SとKの制約から、文字列を連結させてから操作回数を数えようとすると、O( | S | * K ) となり間に合いません．
そのため、Sに対して、どの隣り合う2文字も相異なるような操作回数を求めて、それをK倍する方針で解きます．

まず、同じ文字がX回連続する部分を、隣り合う2文字が相異なるようにするには、X / 2回操作を行えばよいです．

例）
aaa -> axa ( 3 / 2 = 1 回)
aaaa -> axax ( 4 / 2 = 2 回)

次に考えなければならないこととして、文字列の連結部分が同じ文字だった場合、連結後の連続する文字数に対して2で割らないと、正しい操作回数が求まらない、ということです．

例えば、K = 2, S = "aaabaaa"とすると、連結後は、aaabaaaaaabaaaとなります．
この場合の操作回数の最小は5回で、操作後の文字列は例えばaxabaxaxaxbaxaとなります．
これは、先頭と末尾で連続するaaaに対する操作2（ = (3 / 2) * 2 ）回と、連結部のaaaaaaに対する操作3（ = 6 / 2 ）回の和です。

上記の様に連結部分に考えず、単にSの中で必要な操作回数を求めてK倍すると、aaabaaaの操作回数は2回なので、解は4となり一致しません（aaabaaaをaxabaxaに変換後連結すると、axabaxaaxabaxaとなり、連結部に同じ文字が連続してしまう）．

私は上記の様な方針で解きましたが、連結部分に対する操作回数の数え方をどうするかによって、実装の仕方は分かれると思います．


それでは上記内容を実装してみます．

実装

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

signed main() {
  string s;
  ll k;
  cin >> s >> k;
  
  ll n = s.size();    // sの長さ
  ll ans = 0;         // 必要な操作回数
  ll top = 0;         // sで先頭で同じ文字が連続している数
  ll back = 0;        // sで末尾で同じ文字が連続している数
  ll same_char_cnt;   // iから数えて連続する同じ文字の数

  // sの中で同じ文字が連続する部分について数を数える
  for (ll i = 0; i < n; i += same_char_cnt) {
    same_char_cnt = 1;
    for (ll j = i + 1; j < n; j++) {
      if (s[i] == s[j])
        same_char_cnt++;
      else
        break;
    }

    // 先頭で連続する同じ文字数をtopに保存する. 先頭に対する操作回数はここでは数えない
    // 例えばsが、"aaabccdddaa" なら、先頭の"aaa"部分について3を格納する
    if (i == 0) {
      top = same_char_cnt;
      continue;
    }

    // 末尾で連続する同じ文字数をbackに保存する. 末尾に対する操作回数はここでは数えない
    // 例えばsが、"aaabccdddaa" なら、末尾の"aa"部分について2を格納する
    if (i + same_char_cnt >= n) {
      back = same_char_cnt;
      continue;
    }

    // 文字列の途中で連続する同じ文字に対する操作回数をansに加算する.
    // 例えばsが、"aaabccdddaa" なら、"b", "cc", "ddd" の3つの部分について計算を行う
    ans += same_char_cnt / 2;
  }

  

  if (top == n) { 
    // sが1種類の文字だけで構成される場合
    ans = (n * k) / 2;
  } else {
    // sが2種類以上の文字で構成される場合

    // sの途中部分に対する操作回数をk倍する
    ans *= k;

    if (s[0] == s[n - 1]) 
      // 先頭と末尾の文字が一致する場合
      
      // 1つの接点部分の操作回数は(top + back) / 2 回となる
      // 接点は k-1 箇所ある
      ans += (top + back) / 2 * (k - 1) + top / 2 + back / 2;
      
    else
      // 先頭と末尾の文字が一致しない場合
      ans += k * (top / 2 + back / 2);
      
  }

  cout << ans << endl;

  return 0;
}