084 - There are two types of characters（★3）

https://atcoder.jp/contests/typical90/tasks/typical90_cf

概要

o, x で構成される長さNの文字列Sがある。 lからr文字目までにo, x が両方含まれることを条件として、l, r の組み合わせの数を求めよ。

解き方

しゃくとり法で解いた。問題の性質が、けんちょんさんのしゃくとり法解説にある

「条件」を満たす区間 (連続する部分列) を数え上げよ

とまさに合致している。 https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

考え方は、S[i] を left として採用するとき、rightとして有効な要素はいくつあるかを求めて、その合計が答えになる。S[-1]はleftとして採用できない(rightが作れない)ため、除く。

S[i]をleftとしたときに、rightとして有効な要素はいくつあるかは、S[i]より後ろに自分と異なる文字が最初にどこに出現するか分かればいい。自分と異なる文字を最初に見つけられたら、その文字以降はすべてrightとして採用できる。

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

left = 0
# leftとして、S[i] を採用するときの組み合わせ数
# 例えば (1, 2), (1, 3) の組み合わせが有効な場合、S[1]は2になる
ans = [0] * N

for right in range(1, N):
    if S[left] == S[right]:
        continue

    # left から right まで見る。
    for l in range(left, right):
        # S[l] とS[right]が異なる文字になればいい
        # したがってright以降はすべて採用できるので、 lを採用するときの組み合わせ数は S[right:] の個数になる
        ans[l] = len(S[right:])
    left = right

# S[-1] は left として採用できないため、最後は省く
print(sum(ans[:N - 1]))

https://atcoder.jp/contests/typical90/submissions/52622119

hxrxchang / atcoder

084 - There are two types of characters（★3） #28

概要

解き方