「要するに o の最長連続箇所を求めればいい (ただし例外あり)」って感じに、シンプルに整理する力が問われる問題！

問題へのリンク

問題概要

正の整数 $L$ に対して、レベル $L$ のダンゴ文字列とは、以下の条件を満たす文字列である。

o と - からなる長さ $L+1$ の文字列である
先頭の文字と末尾の文字のうちちょうど一方が - であり、そのほかの $L$ 文字はすべて o である

2 種類の文字 o, - からなる、長さ $N$ の文字列 $S$ が与えられるので、次の条件を満たすような正整数 $X$ のうち、最大のものを求めよ。

「 $S$ の連続する部分文字列であって、レベル $X$ のダンゴ文字列であるものが存在する」

ただし、そのような整数が存在しない場合、-1 と出力せよ。

制約

$1 \le N \le 2 \times 10^{5}$

解法

問題文がとても数学チックで難しい。しかし、実は言っていることはそんなに難しくない。

後半の文章 (次の条件を満たす正整数 $X$ の最大値を求めよ、のところ) は、要するに次のことを言っている。

文字列 $S$ に含まれるダンゴ文字列のレベル (o の個数 ) の最大値を求めよ

ダンゴ文字列とは、ooo- や、-ooooo みたいに、

左端と右端のどちらかが -
それ以外はすべて o

という文字列のことだ。ここまで整理すると、そう難しい問題文ではなくなって来る。

さらに整理する

ここで入力例 3 を見てみよう。

30
-o-o-oooo-oo-o-ooooooo--oooo-o

この答えは 7 だ。具体的には、次の部分が最大レベルのダンゴ文字列になっている。

-o-o-oooo-oo-o "-ooooooo" --oooo-o

もしくは、次のような取り方でも OK

-o-o-oooo-oo-o- "ooooooo-" -oooo-o

これを見ると、次の予想が立つ。

要するに、文字列 $S$ 中の、o が連続する長さの最大値が答えではなかろうか

ただし例外はある。

$S$ のすべての文字が o の場合は、- がないのでダンゴ文字列が含まれない
$S$ のすべての文字が - の場合は、o がないのでダンゴ文字列が含まれない

逆に、o と - の両方を含む文字列なら、上記の予想は正しい。

なぜなら、連続する o の左側と右側のどちらかには - がないと「すべての文字が o」ということになってしまうからだ。

解法

整理すると、

$S$ のすべての文字が o や - である場合は、-1
それ以外の場合は、o が連続する長さの最大値

計算量は $O(N)$ となる。

解答例

C++

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    int res = -1;
    int length = 0;  // 現在 o が何個連続しているか
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'o') {
            // `o` の場合は「連続長」を伸ばす
            ++length;
            res = max(res, length);
        } else {
            // `-` の場合は記録が途絶える
            length = 0;
        }
    }
    
    // 全部 `o` の場合はダメ (全部 `-` の場合は res = -1 のまま)
    if (res == N) res = -1;
    cout << res << endl;
}

Python3

N, S = int(input()), input()

if '-' in S and 'o' in S:
    # 文字列 S を '-' で分解して、その最大長さをとる
    print(max(map(len, S.split('-'))))
else:
    # 'o' だけ、または '-' だけ、という場合は -1
    print(-1)

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

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

AtCoder ABC 299 C - Dango (4Q, 灰色, 300 点)

問題概要

制約

解法

さらに整理する

解法

解答例

C++

Python3