← 返回题目列表

AtCoder · joisc2016_f

F. 厕所

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

トイレ - 原题 PDF 第 1 页
原题PDF第8页
トイレ - 原题 PDF 第 2 页
原题PDF第9页
トイレ - 原题 PDF 第 3 页
原题PDF第10页
トイレ - 原题 PDF 第 4 页
原题PDF第11页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                            Contest Day 2 – Toilets


                         トイレ(Toilets)



 国際情報オリンピック日本大会の競技会場の近くにはトイレが2 つある.片方は女性専用トイレで,も
う片方は男女共用トイレである.女性はどちらのトイレも利用できるが,男性は男女共用トイレのみ利用
できる.
 競技が終了したので,2N 人の選手がトイレを利用するために一列に並んだ.並んだ選手はいずれも男性
または女性のどちらかである.選手は次の規則に従い,順番にトイレを利用する.

   • 列の先頭の選手が女性の場合,先頭の選手は空いているトイレに入る.ただしトイレが両方とも空い
   ている場合は,女性専用トイレに入る.

   • 列の先頭の選手が男性の場合は次の規則に従う.

    ◦男女共用トイレが空いている場合は,先頭の選手は男女共用トイレに入る.

    ◦男女共用トイレが空いておらず,女性専用トイレが空いている場合は,列に並んでいる女性の
     うちで最も前の選手が列から抜けて女性専用トイレに入る.

 すべての選手はトイレに入ってから出るまでに1 分かかる.選手がトイレに向かうのにかかる時間は無
視してよい.
 列をあらかじめ並べ替えることで,N 分後の時点で全員がトイレの利用を終えているようにしたい.
 列の並べ替え方に対して,選手の不満度を次のように定義する.

   • ある選手の不満度とは,列の並べ替えの前には自分より後ろにいたが,並べ替えによって自分より前
   に移った選手の人数である.

不満度の定義において,実際にトイレに入るときに発生する順番の入れ替えは考慮しない.
 N 分後の時点で全員がトイレの利用を終えているような列の並べ替えをうまく定めることで,選手の不
満度の最大値をできるだけ小さくしたい.


課題

 トイレに並んでいる2N 人の選手に関する情報が与えられたとき,N 分後の時点で全員がトイレの利用
を終えているように列を並べ替えることができるかを判定し,できる場合は,選手の不満度の最大値とし
て考えられる値のうち,最小の値を求めるプログラムを作成せよ.





                        トイレ– 1 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                            Contest Day 2 – Toilets


入力

 標準入力から以下のデータを読み込め.

   • 1 行目には,整数N が書かれている.これは,2N 人の選手が列に並んでいることを表す.

   • 2 行目には,整数M が書かれている.M の値と続くM 行のデータは,列に並んでいる選手の情報を
   表す.

   • 続くM 行のうちのi 行目(1 ≦i ≦M) には,文字列S i と整数Ki が空白を区切りとして書かれている.

 これらのデータから,選手の列を表現する長さ2N の文字列X を次のように定める.

   • 文字列X は,文字列X1, . . . , XM をこの順に連結することでできる文字列である.

   • 文字列Xi (1 ≦i ≦M) は,文字列S i をKi 個連結することでできる文字列である.

 このようにして定めた文字列X のうち左からj 番目(1 ≦j ≦2N) の文字は,列の先頭からj 番目の選手
の性別を表す.この文字が‘M’ のときは男性であることを表し,‘F’ のときは女性であることを表す.


出力

 標準出力に,選手の不満度の最大値として考えられる値のうちの,最小の値を1 行で出力せよ.ただし,
どのように列を並べ替えてもN 分後に全員がトイレの利用を終えることが不可能な場合は,-1 を出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦N ≦1 000 000 000 000 000 000 (= 1018).

   • 1 ≦M ≦100 000.

   • 1 ≦Ki ≦2N (1 ≦i ≦M).

   • 1 ≦(文字列S i の長さ) ≦2N (1 ≦i ≦M).

   • 文字列S i (1 ≦i ≦M) の各文字は,‘M’ または‘F’ のいずれかである.

   • (文字列S 1 の長さ) + (文字列S 2 の長さ) + · · · + (文字列S M の長さ) ≦200 000.

   • 入力データから定まる文字列X の長さは2N である.





                        トイレ– 2 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                            Contest Day 2 – Toilets


小課題1 [14 点]

 以下の条件を満たす.

   • N ≦10.

   • M = 1.

   • K1 = 1.


小課題2 [22 点]

 以下の条件を満たす.

   • N ≦100 000.

   • M = 1.

   • K1 = 1.


小課題3 [64 点]

 追加の制限はない.


入出力例

  入力例1        出力例1
   6                    2
   1
   FFFMMMMMMFFF 1

 入力例1 では12 人の選手が一列に並んでいる.次のように列を並べ替える.

   1. 前から4 番目の選手を,2 人分だけ前に移動させる.

   2. 前から5 番目の選手を,2 人分だけ前に移動させる.

この並べ替え方において,選手の不満度の最大値は2 である.並べ替えた後,選手の列を表す文字列は
FMMFFMMMMFFF となる(‘M’ は男性を,‘F’ は女性を表す).並べ替えた後の列において,前からi 番目(1 ≦
i ≦12) の選手を選手i とする.選手は次のようにトイレを利用する.

   1. 選手1 と選手2 がトイレを利用する.

   2. 1 分経過後に,選手3 と選手4 がトイレを利用する.




                        トイレ– 3 / 4

Japanese Olympiad in Informatics 2015/2016
                                                         Spring Training Camp/Qualifying Trial
                                             March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                          Contest Day 2 – Toilets



 3. さらに1 分経過後に,選手5 と選手6 がトイレを利用する.

 4. さらに1 分経過後に,選手7 と選手10 がトイレを利用する.

 5. さらに1 分経過後に,選手8 と選手11 がトイレを利用する.

 6. さらに1 分経過後に,選手9 と選手12 がトイレを利用する.

選手の不満度の最大値が2 より小さくなる並べ替え方は存在しないので,2 を出力する.



 入力例2        出力例2
 6                    -1
 1
 MMFFMMMMFFMF 1

6 分後に全員がトイレの利用を終えるような列の並べ替え方は存在しない.



 入力例3        出力例3
 6                    0
 1
 MFFFMFMMFFFM 1


 入力例4        出力例4
 6                    0
 4
 M 1
 F 2
 FM 2
 MFFFM 1

入力例3 と入力例4 において,入力データから定まる文字列X は同じであり,MFFFMFMMFFFM である.





                      トイレ– 4 / 4