Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

Codeforces Round #541 (Div. 2) - E 「String Multiplication」 [2200]

codeforces.com

概要

文字列 s, tに対して、文字列同士の「掛け算」を s \cdot t = t + s_1 + t + s_2 + \cdots + t + s_m + tと定義する( +は文字列の結合)。

そして文字列の「美しさ」を、「1種類の文字からなる最長連続部分列の長さ」として定義する。

 n個の文字列 \{p_i\}が与えられるので、文字列 ( \cdots ( ( p_1 \cdot p_2) \cdot p_3) \cdots ) \cdot p_nの美しさを求めよ。なお、解は 10^9を超えないことが保証されている。

制約

  •  2 \leq n \leq 10^5
  •  \sum p_i \leq 10^5

解説

本質的なところから言ってしまうと、この「掛け算」には結合律が成り立つ。つまり、任意の文字列 s, t, uについて、 (s \cdot t) \cdot u = s \cdot (t \cdot u)が成り立つ。

各長さが2の場合を図にしたのが以下の通り。

f:id:misteer:20190227221530j:plain

正直「いや気づくかい」って感じだが、「掛け算(multiplication)」って名前がヒントだったのだろう。


そういうわけで結合律が成り立つので、 ( \cdots ( (p_1 \cdot p_2) \cdot p_3) \cdots ) \cdot p_nの代わりに p_1 \cdot (\cdots (p_{n-2} \cdot (p_{n-1} \cdot p_n) ) \cdots )について考えればいい。

こうすることで、格段に考えるのが楽になる。というのも、途中で違う文字が紛れ込んでくると、それ以降

  • 右端、左端の文字
  • 右端、左端の連続単一文字列の長さ( l, rとする)

が変わらなくなるからだ。そして美しさの更新は「それ以降の文字列に、端点と同じ文字が一度でも現れるか」だけ見れば十分となる。

それでも一番最初と全てが同じ文字の場合の処理は少し大変だが、そこは気合で実装する。

実装例

気合とは言ったが、適宜関数にすると幾分見通しが良くなる。

文字列を反転させて左右の処理を同じ関数で行うのは、実装を楽にする工夫として重要である。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// 先頭から何文字が同じか
int samecount(string S) {
    for (int i = 1; i < S.length(); ++i) {
        if (S[i] != S[i - 1]) return i;
    }
    return S.length();
}

// cのみからなる最長連続部分列の長さ
int subcount(string S, char c) {
    int ret = 0, cnt = 1;
    for (char sc : S) {
        if (sc != c) cnt = 0;
        ret = max(ret, cnt);
        ++cnt;
    }
    return ret;
}

int main() {
    int N;
    cin >> N;
    
    vector<string> S(N);
    for (auto& s : S) cin >> s;
    reverse(S.begin(), S.end());
    // ここで入力順を反転させているのに注意

    char lc = S[0].front();
    char rc = S[0].back();  // 左端、右端の文字
    
    int l = samecount(S[0]);  // 左端の連続単一文字列の長さ
    reverse(S[0].begin(), S[0].end());
    int r = samecount(S[0]);  // 右端の連続単一文字列の長さ
    
    bool same = (l == S[0].length());
    // 全ての文字が同じか否か

    int ans = 0;  // 現時点での美しさ
    for (char c = 'a'; c <= 'z'; ++c) ans = max(ans, subcount(S[0], c));

    string rest;
    // 違う文字が入ったとき、残りの文字列を全部くっつける
    
    for (int i = 1; i < N; ++i) {
        if (same) {  // 今掛け算中の文字列は全てlcからなる
        
            ans = (l + 1) * (subcount(S[i], lc) + 1) - 1;

            if (S[i].front() == lc) {
                l = (l + 1) * (samecount(S[i]) + 1) - 1;
            }

            reverse(S[i].begin(), S[i].end());
            if (S[i].front() == rc) {
                r = (r + 1) * (samecount(S[i]) + 1) - 1;
            }

            same = (S[i].front() == rc && samecount(S[i]) == S[i].length());
        } else {
            // 違う文字が混ざったので、残りを全部くっつける
            for (int j = i; j < N; ++j) rest += S[j];
            break;
        }
    }

    // 違う文字が入ったときの処理
    if (lc == rc && find(rest.begin(), rest.end(), lc) != rest.end()) {
        ans = max(ans, l + r + 1);
    } else {
        if (find(rest.begin(), rest.end(), lc) != rest.end()) ans = max(ans, l + 1);
        if (find(rest.begin(), rest.end(), rc) != rest.end()) ans = max(ans, r + 1);
    }

    cout << ans << endl;
    return 0;
}

ちなみに、最後の「違う文字が入ったときの処理」を最初はforループの中に入れていたのだが、find()が重かったらしくTLEになった。こういう「読めないエラー」はどう対処すればいいのか...。

感想

  • 結合律に気づくのがやはり鬼門。
  • 実装はこれでも結構スッキリさせた方。