読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

yukicoder No.345 最小チワワ問題(★1) 解説

競プロ 作問 文字列

yukicoderで初めて作問させていただいたので、その問題の解説です。

解説にはC++, Pythonのサンプルコードをつけてあります。

質問等あればコメント欄か @yurahuna まで。

問題

No.345 最小チワワ問題 - yukicoder

与えられる文字列 Sの連続した部分文字列のうち、「チワワ列」となるものの最小の長さを出力してください。

ただしチワワ列とは、'c', 'w', 'w' がこの順で含まれるような文字列のことです。

もし Sの中にチワワ列が存在しないときは、 -1を出力してください。

制約

 1 \leq S \leq 100

解法

想定解は O(N^2)ですが、 O(N)の解法もあります。順に紹介しますね。

共通事項として、この問題ではチワワ列の最小の長さを求めたいので、先頭が 'c' かつ終端が 'w' であるようなチワワ列のみ考えれば十分です。

解法1

文字列を左から順に見ていきます。'c' に出会ったらその位置を iとし、 iより右側にあるwを探します。2個目の 'w' が見つかったらその位置を jとします。すると、 iの位置にある 'c' については、 jの位置にある 'w' までをチワワ列とするのが長さ最小になります。よって、各 'c' について2つめの 'w' の位置を探し、長さの最小値を取っていけばOKです。 iを探すループの中に jを探すループが入っているので、計算量は O(N^2)となります。

  • 解答例: C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

/*** O(N^2) ver. ***/

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

int main() {
    string S;
    cin >> S;
    int N = S.length();
    int mi = N + 1;
    REP(i, N) {
        if (S[i] == 'c') {
            int w = 0;
            FOR(j, i+1, N) {
                if (S[j] == 'w') {
                    w++;
                }
                if (w == 2) {
                    mi = min(mi, j - i + 1);
                    break;
                }
            }
        }
    }
    if (mi == N + 1) mi = -1;
    cout << mi << endl;
    return 0;
}
s = input()
N = len(s)

mi = N + 1
for i in range(N):
    if s[i] == 'c':
        cnt = 0
        for j in range(i+1, N):
            if s[j] == 'w':
                cnt += 1
            if cnt >= 2:
                mi = min(mi, j - i + 1)
                break

if mi != N + 1:
    print(mi)
else:
    print(-1)

解法2

解法1では、各 'c' について、何度も2番目の 'w' を探しているという点で無駄がありました。

そこで、文字列を左からではなく右から走査し、「2番目の 'w' 」の位置 w2を更新していきます。すると 'c' に出会う度に長さの最小値を更新すればよく、計算量が O(N)で済みます。

  • 解答例: C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

/*** O(N) ver. ***/

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

int main() {
    string S;
    cin >> S;
    int N = S.length();
    int mx = N + 1;
    int w1 = N, w2 = N;
    RREP(i, N) {
        if (S[i] == 'w') {
            w2 = w1;
            w1 = i;
        }
        if (S[i] == 'c' && w2 != N) {
            mx = min(mx, w2 - i + 1);
        }
    }
    if (mx == N + 1) mx = -1;
    cout << mx << endl;
    return 0;
}
# -*- coding: utf-8 -*-

### O(N) ver. ###

s = input()
N = len(s)

mi = N + 1
w1 = w2 = N
for i in range(N)[::-1]:
    if s[i] == 'w':
        w1, w2 = i, w1
    if s[i] == 'c' and w2 < N:
        mi = min(mi, w2 - i + 1)

if mi != N + 1:
    print(mi)
else:
    print(-1)

実はとある方からのリクエストで作った問題なのですが、果たしてCさんは解けたのでしょうか……?