けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 039 A - Connection and Disconnection (茶色, 300 点)

区間分割して考える系、AGC-A にめちゃくちゃ多いね

問題概要

文字列  S が与えられる。 S K 回繰り返してできる文字列を  T とする。

 T の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにするとき、 必要な操作の回数の最小値を求めよ。

制約

  •  1 \le |S| \le 100
  •  1 \le K \le 10^{9}

考えたこと

まず  K = 1 の場合を考えてみる。このとき、文字列  S において、同じ文字が連続している箇所ごとに区切って考えることにする。たとえば

aaabccccccddd

であれば、

aaa | b | cccccc | ddd

という感じだ (これはランレングス圧縮そのもの)。そして、それぞれの区間について、長さが  n のとき、 n/2 回 (小数点以下切り捨て) の操作で条件を満たすようにできる。

axa | b | cxcxcx | dxd
(1 回、0 回、3 回、1 回)

という風になってる。

文字列が  K 回連続するとき

まず、 S において、区間の両端以外の部分については、単純に  K 倍するだけで OK。

そしてもし両端の文字が異なる場合は、両端についても単純に  K 倍すれば OK。

両端の文字が一致する場合は、

  • 左端側の文字数を  a
  • 右端側の文字数を  b

としたとき、

  • 長さ  a区間が 1 個 ( a/2 回)
  • 長さ  b区間が 1 個 ( b/2 回)
  • 長さ  a + b区間 K-1 個 ( (a+b)/2 * (K-1) 回)

を合計すれば OK。

コード

計算量は  O(|S|) となる。

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

int main() {
    string S;
    long long K;
    cin >> S >> K;
    vector<long long> v;
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < S.size() && S[j] == S[i]) ++j;
        v.push_back(j - i);
        i = j;
    }
    if (S[0] != S.back()) {
        long long sum = 0;
        for (auto c : v) sum += c/2;
        cout << sum * K << endl;
    }
    else {
        if (v.size() == 1) cout << v[0] * K / 2 << endl;
        else {
            long long left = v[0], right = v.back(), mid = 0;
            for (int i = 1; i+1 < v.size(); ++i) mid += v[i]/2;
            cout << mid*K + (left+right)/2 * (K-1) + left/2 + right/2 << endl;
        }
    }
}