Help us understand the problem. What is going on with this article?

尺取り法による部分文字列の探索

概要

ある条件を満たす部分文字列を探索する場合、総当たりで探索を行うと計算量がO(n^2)になり、制限時間に間に合わない場合がほとんどです。そこで今回は、尺取り法(しゃくとり法)によって効率的に部分文字列を探索する手法を紹介します。

例題

ABC032 C - 列

概要

長さ $n$ の0を含む自然数からなる数列 $a_1, a_2, \dots, a_n$ と自然数 $K$ が与えられる。数列の連続する部分列で、その積が $K$ 以下となるもののうち、最大の長さを求めよ (条件を満たす区間がないときは $0$ を出力)。

 条件: $n = 7$, $K = 6$, $a = (4, 3, 1, 1, 2, 10, 2)$
 解答: $4$

条件を満たす最長の部分列は(3, 1, 1, 2) であり、その長さは4である

実装例

import sys
n, k = map(int, input().split())
s = []
ans = 0

for i in range(n):
    s.append(int(input()))

# 0が一つでも含まれている場合、積は0になり必ず条件を満たすため、数列の長さをそのまま返す
if any(n == 0 for n in s):
    print(n)
    sys.exit()

# 全ての要素がKを超えている場合、条件を満たす部分列は存在しない
if all(n > k for n in s):
    print(0)
    sys.exit()

# 右端のindex
r = 0
# 第1項を積として持っておく
temp = s[0]

for l in range(n-1):
    if l > 0:
        temp //= s[l-1]

    while r <= n - 1:
        # 積がK以下の場合、部分列の長さを調べて最長なら更新する
        if temp <= k:
            ans = max(ans, r - l + 1)
            r += 1
            if r <= n - 1:
                temp *= s[r]
        else:
            break

print(ans)

ABC124 D - Handstand

概要

0と1 からなる長さ N の文字列 S と正整数 K が与えられる。連続する0の列をK回まで1の列に変換できる時、連続する1の列を最長でどれだけの長さにできるかを求めよ

方針

連続する0の列をK個以下含むような最長の部分列の長さを求めれば良い

実装例

n, k = map(int, input().split())
s = input()
ans = 0

# 連続する0の列が現れる回数を数える
cnt = 0

# lを左端、rを右端とする
r = 1
for l in range(0, n):
    if l == 0 and s[l] == '0':
        cnt += 1

    # 左端が0から1に変わるタイミングで、カウントを1減らす
    if l > 0 and s[l] == '1' and s[l-1] == '0':
        cnt -= 1

    while r <= n - 1:
        # 右端が1から0に変わるタイミング
        if s[r] == '0' and s[r-1] == '1':
            # カウントがK未満の場合は、単にカウントを増やす
            if cnt < k:
                cnt += 1
            # カウントがKに達している場合、while文を抜ける(左端:lを一つ進める)
            else:
                break
        r += 1

    # 最長部分列の長さを更新
    ans = max(ans, r - l)

print(ans)

文字列Sの部分文字列のうち、下記の条件を満たす最長の部分文字列Tの長さを求めよ

  • TはSに含まれる連続する部分文字列である
  • Tは3種類以上の文字を含んではならない

例1

入力

"eceba"

出力

3

"ece"が条件を満たす最長の部分文字列となる

例2

入力

"ccaabbb"

出力

5

"aabbb"が条件を満たす最長の部分文字列となる

実装例

条件を満たす最長の部分文字列の長さを求める
    # 条件判定のメソッドを用意しておく
    def isValid(t):
        charSet = set()
        for c in t:
            charSet.add(c)
            # 3種類以上の文字を含む場合はアウト
            if len(charSet) > 2:
                return False
        return True

    def longestSubstringLength(s):
        maxLen = 0

        for i in range(len(s)):
            l = i
            r = i + 1

            while l < r and r < len(s):
                # lからrの範囲の部分文字列を調べる
                temp = s[l:r+1]

                # 条件を満たす部分文字列が見つかったら、rを右にずらして探索範囲を広げる
                if isValid(temp):
                    if len(temp) > maxLen:
                        maxLen = len(temp)
                    r += 1
                # 部分文字列が条件を満たさない(3種類以上の文字を含む)場合、whileループから抜ける
                else:
                    break

        return maxLen

参考

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away