以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
JOI Open Contest
September 6, 2020
monochrome
白黒の点(Monochrome Points)
円周上に2N 個の点があり,時計回りに順に1, 2, . . . , 2N と番号がついている.各点は白と黒の一方の色
で塗られており,白い点と黒い点はそれぞれN 個ずつある.
ここで以下の2 つの条件を満たすように,これらの点をN 本の線分で結ぶことを考える.
• 各点はちょうど1 つの線分の端点となっている.
• 各線分は白い点と黒い点を結んでいる.
N 本の線分のうち,互いに交わるような線分の組の個数を交点数と呼ぶことにする.各点の色の情報が与
えられたとき,条件を満たすようにN 本の線分を引いたときの交点数の最大値を求めるプログラムを作成
せよ.
入力
入力は以下の形式で標準入力から与えられる.
N
S
S は各点の色を表す長さ2N の文字列である.S の各文字はB,W のいずれかであり,i 番目の文字
(1 ≦i ≦2N) はi 番目の点の色を表す.B は黒い点であることを,W は白い点であることを表す.
出力
条件を満たすようにN 本の線分を引いたときの交点数の最大値を標準出力に1 行で出力せよ.
制約
• 1 ≦N ≦200 000.
• S はB,W それぞれN 文字ずつからなる長さ2N の文字列である.
小課題
1. (4 点) N ≦8.
2. (21 点) N ≦300.
3. (10 点) N ≦2 000.
4. (65 点) 追加の制約はない.
白黒の点– 1 / 2
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
JOI Open Contest
September 6, 2020
monochrome
入出力例
入力例1 出力例1
3 2
BBWWBW
左図のように線分を引くと交点数は2 となる.一方で右図のように線分を引くと交点数は3 となるが,こ
れは条件を満たさない.
1 1
6 2 6 2
5 3 5 3
4 4
入力例2 出力例2
5 8
BWBWBBWBWW
入力例3 出力例3
10 41
WBBBWBBWWBWWBWWBWBWB
入力例4 出力例4
16 105
WWWBWBBBBWWBWWBWWBBWWBBBWBBBWWBW
白黒の点– 2 / 2