概要

区間ごとの「野菜合計」と「果物合計」が等しいかを、その差分の累積和に言い換える問題です。
累積差分が同じ位置同士を数えることで、全区間を高速に数えられます。

考察

各日について、
- V は \((v_i,f_i)=(1,0)\) なので差 \(v_i-f_i\) は \(+1\) - F は差が \(-1\) - B,N は差が \(0\)

と見られます。

区間 \([l,r]\) がバランス期間である条件 [ \sum_{i=l}^r vi = \sum{i=l}^r fi ] は、 [ \sum{i=l}^r (v_i-f_i)=0 ] と同値です。

ここで prefix（先頭からの累積）を [ Dk=\sum{i=1}^k (v_i-f_i),\quad D_0=0 ] と置くと、区間 \([l,r]\) の差分和は [ Dr-D{l-1} ] なので、バランス条件は [ Dr=D{l-1} ] になります。
つまり 同じ累積差分値を持つ2つの位置の組 を数えればよいです。

素朴に全区間 \((l,r)\) を試すと区間数は \(O(N^2)\) で、\(N\le 10^6\) では間に合いません。
そこで、左から1回走査しながら「これまでに各差分値が何回出たか」を連想配列で管理します。

• 現在の差分を diff とする
• その時点で cnt[diff] 回、同じ差分が過去に出ていれば、
  そのすべてが「現在位置を右端とするバランス期間」を作る
• よって ans += cnt[diff]
• その後 cnt[diff] += 1

これで重複なく全て数えられます。

アルゴリズム

1. diff = 0（累積差分）、ans = 0 を用意。
2. cnt（差分値 → 出現回数）を辞書で持ち、初期値として cnt[0]=1 を入れる。
   （長さ0の prefix \(D_0\) を表す。これがないと先頭から始まる区間を数え損ねる）
3. 文字列 S を左から順に処理：
   • V なら diff += 1
   • F なら diff -= 1
   • B, N なら変化なし
   • ans += cnt[diff]
   • cnt[diff] += 1
4. ans を出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)
  （差分値の種類数は高々 \(2N+1\)）

実装のポイント

• cnt[0] = 1 の初期化が重要です。

• B と N は差分が増減しないので、if/elif で V,F のみ更新すればOKです。

• 答えは最大で区間数 \(N(N+1)/2\) になり得るため、Python の int で安全に扱えます。

  ソースコード

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = input().strip()

    diff = 0
    cnt = defaultdict(int)
    cnt[0] = 1
    ans = 0

    for ch in S:
        if ch == 'V':
            diff += 1
        elif ch == 'F':
            diff -= 1
        # 'B' and 'N' do not change diff

        ans += cnt[diff]
        cnt[diff] += 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。