−目次

AtCoder Regular Contest 196 (Div. 1) A,B,C問題メモ
- A - Adjacent Delete
  - 問題文
  - 制約
  - 解法
- B - Torus Loop
  - 問題文
  - 制約
  - 解法
- C - Strongly Connected
  - 問題文
  - 制約
  - 解法

AtCoder Regular Contest 196 (Div. 1) A,B,C問題メモ

AtCoder Regular Contest 196 (Div. 1)

A - Adjacent Delete

問題文

長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
あなたはこの数列の隣接する $2$ 数を選びどちらもこの数列から削除する、という操作を数列の長さが $1$ 以下になるまで繰り返します。
一度の操作で得られるスコアは選んだ $2$ 数の差の絶対値です。
得られるスコアの合計としてありうる最大値を求めてください。

制約

$2 \le N \le 3 \times 10^5$
$1 \le A_i \le 10^9$
入力はすべて整数

解法

分かってみれば単純なんだけどね。本番中は違う方針に走って時間かかっちゃった。

$K = \lfloor \frac{N}{2} \rfloor$ とする。操作は $K$ 回おこなうことになる。

$A$ の大きい方から $K$ 要素の多重集合を $S_l$ 、小さい方から $K$ 要素の多重集合を $S_s$ とする。

仮に、隣接でなくても自由にペアが作れるとした場合、達成できる最大値は $\mathrm{sum}(S_l)-\mathrm{sum}(S_s)$ である。
この時「 $S_l$ から1要素と $S_s$ から1要素をペアにする」ことを守れば、具体的なペアの組み方は関係ない。

$N$ が偶数の時、この最大値は必ず達成できる。
なぜなら、常に「 $S_l$ の要素と $S_s$ の要素が隣接する箇所」は存在するから。それを選び続ければいい。

奇数の場合が問題だが、これも「残す1要素」を固定すれば、左右に分割した長さ偶数の2区間それぞれで同じことが言える。
以下の2つがわかれば、奇数の $i$ に対して $L_{i-1}+R_{N-i}$ が、 $A_i$ を残すときの最大値となる。

$L_i:=$ 先頭 $i$ 要素だけで $S_l,S_s$ を考えたときの、 $\mathrm{sum}(S_l)-\mathrm{sum}(S_s)$ （偶数の $i$ に対してのみ定義）
$R_i:=$ 末尾 $i$ 要素だけで $S_l,S_s$ を考えたときの、 $\mathrm{sum}(S_l)-\mathrm{sum}(S_s)$ （偶数の $i$ に対してのみ定義）

$S_s,S_l$ をそれぞれ heapq などで実装して、先頭から常に2つの要素数が均一になるように調整しながら $A_i$ を加えていけば、 $L_i$ を作れる。
末尾からも同様に $R_i$ を作れば、答えが求められる。

Python3

B - Torus Loop

問題文

$H$ 行 $W$ 列のグリッドがあり、各マス $S_{i,j}$ には以下の2種類のタイルのいずれかが置かれています。
- 種類 A：タイルの表面に、隣接する $2$ 辺の中点どうしを結ぶ線分が一本描かれている
- 種類 B：タイルの表面に、向かい合う $2$ 辺の中点どうしを結ぶ線分が一本描かれている
- （具体的な絵は問題ページ参照）
タイルは自由に回転可能としたとき、タイルを配置する方法の数は、A のタイルの数 $a$ 、B のタイルの数 $b$ を用いて、 $4^a \times 2^b$ 通りあります。
このうち、グリッドをトーラスとして見たときにタイルに描かれた線分が行き止まりを持たないようにタイルを配置する方法の数を $998244353$ で割ったあまりを出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

$1 \le T \le 10^5$
$2 \le H,W$
$HW\leq 10^6$
$S_i\,(0\le i\le H-1)$ は A と B のみからなる長さ $W$ の文字列
すべてのテストケースにわたる $HW$ の総和は $10^6$ 以下
$T, H, W$ は整数

解法

ペンシルパズルなんかを解くときによくある考え方だが、「ここには線が通る」という情報と同じくらい、「線が通らない」という情報も重要である。

┼  ┼  ┼  ┼  ┼  ┼    この、┼ に挟まれたタテヨコの各隙間に、
  Ｂ  Ａ  Ａ  Ｂ  Ｂ      「線が通る」か「通らない」かを（矛盾なく）決めれば、
┼  ┼  ┼  ┼  ┼  ┼    タイルの向きは一意に決まる。
  Ａ  Ａ  Ｂ  Ａ  Ａ
┼  ┼  ┼  ┼  ┼  ┼    タイルの向きの代わりに、各隙間に
  Ａ  Ｂ  Ａ  Ａ  Ａ      「線が通る」「通らない」を決めることを考える。
┼  ┼  ┼  ┼  ┼  ┼    ただし、一番上の行と一番下の行、一番左の列と一番右の列は、
                          トーラスなので一致している必要がある。

左上のＢに横向きに線を引くと仮定すると、以下まで連鎖的に決まる。

┼×┼  ┼  ┼×┼×┼
━Ｂ━Ａ×Ａ━Ｂ━Ｂ━
┼×┼  ┼  ┼×┼×┼
  Ａ  Ａ  Ｂ  Ａ  Ａ
┼┃┼  ┼  ┼┃┼┃┼
  Ａ  Ｂ  Ａ  Ａ  Ａ  
┼×┼  ┼  ┼×┼×┼

縦向きに線を引くと仮定すると、全てが反転した形で同じ箇所が以下のように決まる。

┼┃┼  ┼  ┼┃┼┃┼
×Ｂ×Ａ━Ａ×Ｂ×Ｂ×
┼┃┼  ┼  ┼┃┼┃┼
  Ａ  Ａ  Ｂ  Ａ  Ａ
┼×┼  ┼  ┼×┼×┼
  Ａ  Ｂ  Ａ  Ａ  Ａ  
┼┃┼  ┼  ┼┃┼┃┼

隙間に線が通るか通らないかに着目したとき、各タイルは以下の性質を持つ。

タイルAの性質
- 左に線が通る（━）ことが決まったら、右は通らない（×）ことが決まる。
- 左に線が通らない（×）ことが決まったら、右は通ること（━）が決まる。
- 左右が決まっても、上下は決まらない。
タイルBの性質
- 左に線が通る（━）ことが決まったら、右も通り（━）、上下は通らない（×）ことが決まる。
- 左に線が通らない（×）ことが決まったら、右も通らず（×）、上下は通る（┃）ことが決まる。
※それぞれ、左右や上下を入れ替えても同じことが言える。

つまり、ある行における1つの隙間を「×」か「━」か決めれば、以下のことが発生する。

同じ行の隙間は全て「×」か「━」か決まる
その行にＢがあると、Ｂがある列も全て「×」か「┃」か決まる。
さらにその列に他のＢがあると、その行も全て「×」か「━」か決まる。
…というのが連鎖的に繰り返される。

ここで、矛盾するケースが2つある。

Ａが奇数個あるような行または列が1つでもある場合
- 1つの行・列内で、Ａによる━/×の反転はちょうど偶数回発生しないと、1周したときに合わなくなる。
Ｂが矛盾する場合

┼┃┼  ┼×┼…    左上のＢを仮定して通る通らないを決めていった結果、
×Ｂ×Ａ━Ｂ━      ここのＢが矛盾
┼┃┼  ┼×┼…    │
×Ｂ×Ａ━Ａ        │
┼┃┼  ┼┃┼…    │
×Ｂ×Ａ━Ｂ？    ←┘
┼┃┼  ┼？┼…
：  ：  ：  ：

同じ行・列内にある2つのＢは、間に挟まれるＡの個数によって、一方の向きが決まったとき、もう一方が同じ向きか違う向きか決まる。この時、行からの制約と、列からの制約が、矛盾することがある。
二部グラフ判定やポテンシャル付きUnionFindなどで、判定をおこなえる。

矛盾が無い場合、各行・各列を1頂点とした $H+W$ 頂点のグラフを考える。
$(i,j)$ がＢだったとすると、行 $i$ と列 $j$ を連結にしていく。

連結になった行・列は、どこか1箇所の通る通らないが決まれば全て決まる。
一方、連結でない行・列同士は独立に決められる。

最終的な連結成分の個数を $d$ とすると、 $2^d$ 通りの決め方がある。

Python3

        
          
          
              
              from collections.abc import Callable
from operator import xor
from typing import Generic, TypeVar
 
T = TypeVar('T', int, float, tuple)  # データ構造に載せそうな型のうち、Immutable なもの（漏れてたら追加可）
 
 
class UnionFindWithPotential(Generic[T]):
    """ポテンシャル付きUnion-Find
 
    以下の2つのクエリを処理する。
      * unite(x,y,d): 2要素間の差分に対する制約 (x - y = d) を決める。
      * diff(x,y):    2要素間の差を返す。未定義（x と y が連結でない）なら None を返す。
 
    載せられるのはアーベル群に限る(?)。
    つまり2項間の「加算演算」「減算演算」が定義でき、また「加算演算が可換」である場合に限る。
 
    Attributes:
        table (list[int]): 各頂点の、親の頂点番号を表すList。または親である場合は(-要素数)
        values (list[T]): 各頂点の、親との差分を表すList
    """
 
    def __init__(self,
                 n: int,
                 init: T,
                 func: Callable[[T, T], T],
                 rev_func: Callable[[T, T], T]):
        """コンストラクタ
 
        Args:
            n: 要素数
            init: 単位元
            func: 2項間加算演算 (add)
            rev_func: 2項間減算演算 (sub)
        """
        self.table = [-1] * n
        self.values = [init] * n
        self.init = init
        self.func = func
        self.rev_func = rev_func
 
    def root(self, x: int) -> int:
        stack = []
        tbl = self.table
        vals = self.values
 
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        if stack:
            val = self.init
            while stack:
                y = stack.pop()
                val = self.func(val, vals[y])
                vals[y] = val
                tbl[y] = x
        return x
 
    def is_same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)
 
    def diff(self, x: int, y: int) -> T | None:
        """ x と y の差（y - x）を取得。同じグループに属さない場合は None。
        """
        if not self.is_same(x, y):
            return None
        vx = self.values[x]
        vy = self.values[y]
        return self.rev_func(vy, vx)
 
    def unite(self, x: int, y: int, d: T) -> bool:
        """ x と y のグループを、y - x = d となるように統合（順序に注意）
        既に x と y が同グループで、矛盾する場合は AssertionError。矛盾しない場合はFalse。
        同グループで無く、新たな統合が発生した場合はTrue。
        """
        rx = self.root(x)
        ry = self.root(y)
        vx = self.values[x]
        vy = self.values[y]
        if rx == ry:
            assert self.rev_func(vy, vx) == d
            return False
 
        rd = self.rev_func(self.func(vx, d), vy)
        self.table[rx] += self.table[ry]
        self.table[ry] = rx
        self.values[ry] = rd
        return True
 
    def get_size(self, x: int) -> int:
        return -self.table[self.root(x)]
 
 
def solve(h, w, field):
    rows = [[] for _ in range(h)]
    cols = [[] for _ in range(w)]
    bcnt = 0
    mapping = {}
    for i in range(h):
        for j in range(w):
            if field[i][j] == 'A':
                continue
            rows[i].append(j)
            cols[j].append(i)
            mapping[i, j] = bcnt
            bcnt += 1
    all_a_row_cnt = 0
    all_a_col_cnt = 0
    for i in range(h):
        if (w - len(rows[i])) % 2 == 1:
            return 0
        if len(rows[i]) == 0:
            all_a_row_cnt += 1
    for j in range(w):
        if (h - len(cols[j])) % 2 == 1:
            return 0
        if len(cols[j]) == 0:
            all_a_col_cnt += 1
 
    uft = UnionFindWithPotential(bcnt, 0, xor, xor)
    try:
        for i in range(h):
            row = rows[i]
            for ri in range(len(row) - 1):
                j1 = row[ri]
                j2 = row[ri + 1]
                x = mapping[i, j1]
                y = mapping[i, j2]
                uft.unite(x, y, (j2 - j1 + 1) % 2)
        for j in range(w):
            col = cols[j]
            for ci in range(len(col) - 1):
                i1 = col[ci]
                i2 = col[ci + 1]
                x = mapping[i1, j]
                y = mapping[i2, j]
                uft.unite(x, y, (i2 - i1 + 1) % 2)
    except AssertionError:
        return 0
 
    free = all_a_row_cnt + all_a_col_cnt
    for i in range(bcnt):
        if uft.table[i] < 0:
            free += 1
    return pow(2, free, 998244353)
 
 
t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    field = [input() for _ in range(h)]
    ans = solve(h, w, field)
    print(ans)

            

        
      

考察の最初の方にＢの矛盾条件に気付いていたはずなのに、詰めていくうちにいつの間にかどっか行ってた。ううむ。

C - Strongly Connected

問題文

$2N$ 頂点 $2N-1$ 辺の有向グラフがあります。
- 頂点には $1, 2, \ldots, 2N$ の番号がついており、 $i$ 番目の辺は頂点 $i$ から頂点 $i+1$ に向かう有向辺です。
- $N$ 個の W と $N$ 個の B からなる長さ $2N$ の文字列 $S=S_1S_2\ldots S_{2N}$ が与えられます。
- 頂点 $i$ は $S_i$ が W のとき白、B のとき黒で塗られています。
あなたは以下の一連の操作を行います。
- $2N$ 個の頂点を白の頂点と黒の頂点 $1$ つずつからなる $N$ 組のペアに分ける。
- 各ペアについて白の頂点から黒の頂点に向かう辺を追加する。

操作において頂点を $N$ 組のペアに分ける方法のうち、最終的に得られるグラフが強連結となるような方法の数を $998244353$ で割ったあまりを出力してください。

制約

$1 \le N \le 2\times 10^5$
$S$ は $N$ 個の W と $N$ 個の B からなる長さ $2N$ の文字列
$N$ は整数

解法

B問題と比べて一気に難易度が上がる。
以下のアルゴリズムの組合せとなる。特に分割統治FFTで、配列を変換してからおこなうタイプは初めて見た。

包除原理DP
- 特に、DP[i] から DP[j] への遷移時、 $i～j$ 間で1単位採用するパターン数を $c$ として、 $\mathrm{DP}[j]+=-1 \times \mathrm{DP}[i] \times c$ みたいに負で寄与させることで、個数の次元を省略できるやつ
分割統治FFT
- 分割統治FFTは「DP[i] から DP[j] への遷移時、 $j-i$ が一緒なら遷移係数は一緒」という場合に使われるのがよくある
- 今回はそれが満たされないが、FFT前に一度情報を変換してからおこなうと上手くいく

包除原理DP

$S$ の各文字間は $2N-1$ 個ある。
この文字間を境に右から左に遡れないとき、その文字間は「切れ目」であるとする。

i 0   1   2   3   4   5   6   7   8    （両端にも i=0 と i=2N を便宜的に追加し、必ず切れ目と扱う）
   ❶→②→③→❹→❺→⑥→❼→⑧
    ^--'    `--^---^   |    ^--'       ○:白 ●:黒   
               `-------'
   切れ目↑  ↑切れ目    ↑切れ目

文字間の集合 $S=\{s_1,...,s_m\}$ が切れ目であり、他は切れ目であってもなくてもよいパターン数を $f(S)$ とすると、包除原理で全ての ${1,...,2N-1}$ の部分集合に対して $\displaystyle \sum (-1)^{|S|}f(S)$ が答えとなる。

当然これはそのまま求められないが、以下の包除原理DPによって求められる。

$\mathrm{DP}[i]:=i$ 番目の文字間まで見て、 $i$ が切れ目であるような状態の中で、
- $0,1,...,i$ の中で $S$ として採用した個数が「偶数個の状態数 - 奇数個の状態数」

「 $i$ が切れ目である状態」とはどういう状態かを考えると、

$i$ より左の黒が、全て $i$ より左の白とペアになった状態

といえる。白に関しては $i$ より右の黒とペアになっていても良い。
状態数は、 $i$ より左の白、黒の個数を $W_i,B_i$ として、 ${}_{W_i}P_{B_i} = \dfrac{W_i!}{(W_i-B_i)!}$ で表せる。
ただし、 $W_i \lt B_i$ の場合は、値は $0$ とする。

これを踏まえ、 $\mathrm{DP}[j]$ から $\mathrm{DP}[i]$ への遷移を考える。（ $j \lt i$ ）
切れ目 $j～i$ 間にある $B_i-B_j$ 個の黒を、 $i$ より左の白とペアにする方法を数えればよい。
ただし、白のうち $B_j$ 個は、既に $\mathrm{DP}[j]$ において $j$ より左の黒とのペアが確定している。

その方法の数は、 ${}_{W_i-B_j}P_{B_i-B_j} = \dfrac{(W_i-B_j)!}{(W_i-B_i)!}$ となる。
（いずれかの階乗の中身が負となる場合は、値は $0$ とする）

結局、遷移は、

$\displaystyle \mathrm{DP}[i] = -1 \times \sum_{j=0}^{i-1} \mathrm{DP}[j] \times \frac{(W_i-B_j)!}{(W_i-B_i)!}$

となる。これで $O(N^2)$ で解くことはできるようになった。
これを分割統治FFTで高速化する。

分割統治FFT

よくある分割統治FFTは、遷移が以下のようになっていて、

$\displaystyle \mathrm{DP}[i] = \sum_{j=0}^{i-1} \mathrm{DP}[j] \times C_{i-j}$

この $C_{i-j}$ が、 $i-j$ が同じなら $i,j$ によらず一定というのが重要な性質だった。

今回は、そのままでは成り立たないが、 $W_i,B_i$ 基準でまとめなおすと良い形になっている。

「 $W_i=w$ となるような位置 $i$ のDP結果」は、「 $B_j=b$ となるような、 $i$ 未満の全ての位置 $j$ のDP結果の総和」を $dp_b$ として、

$\displaystyle \mathrm{DP}[i] = -1 \times \sum_{b=0} dp_b \frac{(w-b)!}{(w-B_i)!} = -\frac{1}{(w-B_i)!} \sum_{b=0}dp_b (w-b)!$

より、 $dp_b$ と $(w-b)!$ の部分でたたみ込める。

分割統治FFTにおいても、 $[l,m)$ から $[m,r)$ への寄与を求める際に、

$[l,m)$ のDP結果を $dp_b$ を表す数列に変換する
- そのままだと $b=0～B_l-1$ の部分は $0$ が埋まり無駄があるので、indexを左にずらし必要な箇所だけ作る
階乗の数列と畳み込む
- 畳み込んだ結果を $cnv_w$ とする。
$[m,r)$ の各 $i$ につき、 $-\dfrac{cnv_{W_i}}{W_i-B_i}$ を計算し、 $\mathrm{DP}[i]$ に加算する

とすることで、 $O(N(\log{N})^2)$ で計算できる。

Python3

        
          
          
              
              import os
import sys
 
import numpy as np
 
 
def solve(n, s):
    MOD = 998244353
    SUM_E = np.array(
        [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456,
         131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443,
         56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)
    SUM_IE = np.array(
        [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882,
         927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183,
         824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)
 
    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x
 
    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x
 
    def pow_mod(x, n, m):
        r = 1
        y = x % m
        while n > 0:
            if n & 1 == 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r
 
    def butterfly(aaa):
        n = aaa.size
        h = bit_length(n)
 
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p] * now % MOD
                    aaa[i + offset] = (l + r) % MOD
                    aaa[i + offset + p] = (l - r) % MOD
                now = now * SUM_E[bit_scan_forward(~s)] % MOD
 
    def butterfly_inv(aaa):
        n = aaa.size
        h = bit_length(n)
 
        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % MOD
                    aaa[i + offset + p] = ((l - r) * inow) % MOD
                inow = inow * SUM_IE[bit_scan_forward(~s)] % MOD
 
    def ntt(aaa, bbb):
        n = aaa.size
        m = bbb.size
        k = n + m - 1
        z = 1 << bit_length(k)
        raaa = np.zeros(z, np.int64)
        rbbb = np.zeros(z, np.int64)
        raaa[:n] = aaa
        rbbb[:m] = bbb
        butterfly(raaa)
        butterfly(rbbb)
        for i in range(z):
            raaa[i] = raaa[i] * rbbb[i] % MOD
        butterfly_inv(raaa)
        iz = pow_mod(z, MOD - 2, MOD)
        for i in range(k):
            raaa[i] = raaa[i] * iz % MOD
        return raaa[:k]
 
    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1 == 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret
 
    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions
 
    if s[0] != 0 or s[-1] != 1:
        return 0
 
    facts, finvs = prepare_factorials(n * 2, MOD)
 
    b_cnt = np.zeros(n * 2 + 1, np.int64)
    for i in range(n * 2):
        if s[i] == 0:
            b_cnt[i + 1] = b_cnt[i] + 1
        else:
            b_cnt[i + 1] = b_cnt[i]
    w_cnt = np.arange(n * 2 + 1, dtype=np.int64)
    w_cnt -= b_cnt
 
    dp = np.zeros(n * 2 + 1, np.int64)
 
    def bruteforce(l, r):
        for i in range(l, r - 1):
            for j in range(i + 1, r):
                b = b_cnt[j] - b_cnt[i]
                w = j - b_cnt[i] - b_cnt[j]
                if b > w:
                    continue
                c = facts[w] * finvs[w - b] % MOD
                dp[j] -= c * dp[i]
                dp[j] %= MOD
 
    dp[0] = -1
    tasks = [(0, n * 2 + 1, -1)]
    while len(tasks) > 0:
        l, r, m = tasks.pop()
        if m == -1:
            if r - l < 500:
                bruteforce(l, r)
                continue
            m = (l + r) // 2
            tasks.append((m, r, -1))
            tasks.append((l, r, m))
            tasks.append((l, m, -1))
        else:
            bc = b_cnt[m] - b_cnt[l]
            fff = np.zeros(bc + 1, np.int64)
            for i in range(l, m):
                key = b_cnt[i] - b_cnt[l]
                fff[key] += dp[i]
            ggg = facts[:(r - l) * 2]
            hhh = ntt(fff, ggg)
            for i in range(m, r):
                wb = w_cnt[i] - b_cnt[i]
                if wb < 0:
                    continue
                dp[i] -= hhh[w_cnt[i] - b_cnt[l]] * finvs[wb] % MOD
                dp[i] %= MOD
 
    return dp[n * 2]
 
 
SIGNATURE = '(i8,i1[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()
 
if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit
 
    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)
 
n = int(input())
s = np.fromiter(map('BW'.index, input()), dtype=np.int8)
ans = solve(n, s)
print(ans)

            

        
      