← 返回题目列表

AtCoder · joiopen2021_a

A. 穿越

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

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

交配 (Crossing) - 原题 PDF 第 1 页
原题PDF第1页
交配 (Crossing) - 原题 PDF 第 2 页
原题PDF第2页
交配 (Crossing) - 原题 PDF 第 3 页
原题PDF第3页
交配 (Crossing) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                                  JOI Open Contest

                                                                            June 6, 2021


                                                                            crossing

                      交配(Crossing)



 あなたはJust Odd Investigations 研究所を知っているだろうか?この研究所の業務は「ただ奇妙な研究

(just odd investigations)」をすることである.ここでは略してJOI 研究所と呼ぶ.

 ここ数年,世界各地の遺跡で絢爛と咲き誇る広大な花畑が発見されてきたことは記憶に新しいだろう.

JOI 研究所は,これらの花畑に咲く花々が新種であり,その遺伝子が共通の特徴を持つことを発見した.こ

れらの新種の花の遺伝子はJ, O, I からなる長さN の文字列で表すことができ,これを遺伝子の情報と呼ぶ.

  JOI 研究所の研究員であるあなたは,3 株の新種の花を入手した.それぞれの花の遺伝子の情報は
S A, S B, S C である.
 あなたは,2 株の新種の花から新たに1 株の新種の花を作ることができる.この操作を交配と呼ぶ.交配

によって生成される花の遺伝子の情報のi 文字目(1 ≦i ≦N) は,次の法則に従って定まる.

    • もとの2 株の花の遺伝子の情報のi 文字目が一致する場合,それと同じ文字になる.

    • もとの2 株の花の遺伝子の情報のi 文字目が異なる場合,J, O, I のうちそのどちらでもない文字に

   なる.

 つまり,もとの2 株の花の遺伝子の情報のi 文字目がそれぞれc1, c2 であるとき,新たな花の遺伝子の情
報のi 文字目c3 は次の表のように定まる.

                                   c1   J  J  J  O  O  O  I  I  I
                                   c2   J  O  I  J  O  I  J  O  I
                                   c3   J  I  O  I  O  J  O  J  I


 なお,同じ花を何度でも交配に使用してよいほか,交配の結果得られた花をそれ以降の交配に使用しても

よい.

  JOI 研究所はより美麗な花を作り出すため,0 からQ までの番号が付けられたQ + 1 個の遺伝子を候補
遺伝子として提案し,提案書をあなたに渡した.提案書には文字列T0 と,各j (1 ≦j ≦Q) について整数
Lj, R j および文字C j が書かれている.それぞれの候補遺伝子の情報は以下の通りである.

    • 候補遺伝子0 の情報はT0 である.
    • 候補遺伝子j (1 ≦j ≦Q) の情報は,候補遺伝子j −1 の情報のLj 文字目からR j 文字目までをそれぞ
   れC j に置き換えた文字列と一致する.

 整数N,あなたが入手した3 株の花の遺伝子の情報および提案書の内容が与えられたとき,各候補遺伝子

を持つ花が,その3 株の花をもとに交配を0 回以上繰り返すことで得られるかどうかを判定するプログラ

ムを作成せよ.




                          交配– 1 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                                  JOI Open Contest

                                                                            June 6, 2021


                                                                            crossing



入力


 入力は以下の形式で標準入力から与えられる.


    N

      S A
      S B
      S C

    Q

      T0
      L1 R1 C1
                                 ...

     LQ RQ CQ


出力

 標準出力にQ + 1 行出力せよ.j + 1 行目(0 ≦j ≦Q) には,候補遺伝子j を持つ花が,あなたの持つ3 株

の花をもとに交配を0 回以上繰り返すことで得られるならばYes を,得られないならばNo を出力せよ.


制約

    • 1 ≦N ≦200 000.
    • S A, S B, S C の長さはN であり,各文字はJ, O, I のいずれかである.
    • 1 ≦Q ≦200 000.
    • T0 の長さはN であり,各文字はJ, O, I のいずれかである.
    • 1 ≦L j ≦R j ≦N (1 ≦j ≦Q).
    • C j はJ, O, I のいずれかである(1 ≦j ≦Q).


小課題

    1. (3 点) S A = S B = S C,N ≦100.
    2. (23 点) S A = S B = S C.
    3. (23 点) N ≦100.

    4. (51 点) 追加の制約はない.



                          交配– 2 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                                  JOI Open Contest

                                                                            June 6, 2021


                                                                            crossing



入出力例

  入力例1              出力例1

   4                              Yes

   JOJO                           No

   JJOI                           Yes

   OJOO                           Yes

   3

   IJOJ

   1 4 O

   2 2 J

   2 4 I

 あなたが最初から持っている3 株の新種の花の遺伝子の情報はJOJO, JJOI, OJOO である.以降は新種の

花をその遺伝子の情報で表す.

    1. T0 はIJOJ である.JJOI とOJOO を交配してIJOJ を得られるため,Yes を出力する.
    2. T1 はOOOO である.あなたの持つ3 株の花をもとに交配を繰り返してもOOOO は得られないため,No

   を出力する.

    3. T2 はOJOO である.あなたは交配せずともはじめからOJOO を持っているため,Yes を出力する.
    4. T3 はOIII である.JJOI とOJOO を交配してIJOJ を得て,さらにJOJO とIJOJ を交配してOIII
   を得られるため,Yes を出力する.

 この入出力例は小課題3, 4 の制約を満たす.





                          交配– 3 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                                  JOI Open Contest

                                                                            June 6, 2021


                                                                            crossing


  入力例2              出力例2

   3                              No

   JOI                            No

   JOI                            Yes

   JOI

   2

   OJI

   1 2 O

   1 1 J

 あなたの最初から持っている3 株の新種の花の遺伝子の情報はすべてJOI であり,交配を繰り返しても

得られる花はJOI のみである.

    1. T0 はOJI である.これは交配で得られないため,No を出力する.
    2. T1 はOOI である.これは交配で得られないため,No を出力する.
    3. T2 はJOI である.これは交配で得られるため,Yes を出力する.

 この入出力例は小課題1, 2, 3, 4 の制約を満たす.





                          交配– 4 / 4