← 返回题目列表

AtCoder · joiopen2020_b

B. 单色点

中文机器翻译题面 查看原题

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

白黒の点 (Monochrome Points) - 原题 PDF 第 1 页
原题PDF第1页
白黒の点 (Monochrome Points) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 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