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

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

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

AtCoder AtCoder300点 AGC-A 茶色diff ランレングス圧縮 テク:区間ごとに分割する 算数と数学 グルーピング(算数) 文字列 最小回数・最小個数を求める 操作 隣接2要素に制約や目的関数のある問題 操作:1文字を変更する 最適化問題 制約条件:隣接する要素について

区間分割して考える系、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;
        }
    }
}