← 返回题目列表

AtCoder · joiopen2023_b

B. 元胞自动机

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

以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。

セルオートマトン (Cell Automaton) - 原题 PDF 第 1 页
原题PDF第1页
セルオートマトン (Cell Automaton) - 原题 PDF 第 2 页
原题PDF第2页
セルオートマトン (Cell Automaton) - 原题 PDF 第 3 页
原题PDF第3页
セルオートマトン (Cell Automaton) - 原题 PDF 第 4 页
原题PDF第4页
セルオートマトン (Cell Automaton) - 原题 PDF 第 5 页
原题PDF第5页
セルオートマトン (Cell Automaton) - 原题 PDF 第 6 页
原题PDF第6页
可复制的 PDF 提取文本
The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                                cell

           セルオートマトン(Cell Automaton)



 十分に広い2 次元のグリッドがある.このグリッドは上下左右の方向に正方形のマスが敷き詰められた

ものであり,ある基準となるマスから右方向にx 回,上方向にy 回進んだ場所にあるマスを(x, y) と表す.

ただし,左方向にa 回進むことは,右方向に−a 回進むことと等しいものとする.同様に,下方向にa 回進

むことは,上方向に−a 回進むことと等しいものとする.
 時刻0 では,マス(X1, Y1), (X2, Y2), . . . , (XN, YN) は黒色であり,それ以外のマスはすべて白色である.
   t = 0, 1, 2, . . . に対して,時刻t + 1 における各マスの色は,時刻t における各マスの色によって,以下の

ように定まる.

    • 時刻t で黒色のマスは,時刻t + 1 で灰色である.

    • 時刻t で灰色のマスは,時刻t + 1 で白色である.

    • 時刻t で白色のマスは,時刻t で辺で接している4 マスのうちいずれかが黒色であれば時刻t + 1 で

   黒色であり,そうでなければ時刻t + 1 で白色のままである.

 質問がQ 個与えられる.j 番目(1 ≦j ≦Q) の質問では,時刻T j で黒色であるマスの個数を答えなけれ

ばならない.

 時刻0 でのマスの色の情報と質問が与えられたとき,それぞれの質問に答えるプログラムを作成せよ.


入力


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


    N Q

      X1 Y1
      X2 Y2
                                 ...

     XN YN
      T1
      T2
                                 ...

     TQ





                    セルオートマトン– 1 / 6

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                                cell



出力

 標準出力に,Q 行で出力せよ.j 行目(1 ≦j ≦Q) には,時刻T j で黒色であるマスの個数を出力せよ.


制約

    • 1 ≦N ≦100 000.

    • 1 ≦Q ≦500 000.
    • |Xi| ≦109 (1 ≦i ≦N).
    •  |Yi| ≦109 (1 ≦i ≦N).
    • (Xi, Yi) , (Xj, Yj) (1 ≦i <  j ≦N).
    • 0 ≦T j ≦109 (1 ≦j ≦Q).
    • T j < T j+1 (1 ≦j ≦Q −1).
    • 入力される値はすべて整数である.


小課題

    1. (4 点) |Xi| ≦50 (1 ≦i ≦N),|Yi| ≦50 (1 ≦i ≦N),T j ≦50 (1 ≦j ≦Q).
    2. (12 点) |Xi| ≦1 000 (1 ≦i ≦N),|Yi| ≦1 000 (1 ≦i ≦N),T j ≦1 000 (1 ≦j ≦Q).
    3. (8 点) Xi = Yi (1 ≦i ≦N),Q = 1.
    4. (8 点) Xi = Yi (1 ≦i ≦N).
    5. (17 点) N ≦2 000,Q = 1.

    6. (25 点) N ≦2 000.

    7. (26 点) 追加の制約はない.





                    セルオートマトン– 2 / 6

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                                cell



入出力例

  入力例1              出力例1

   2 3                            2

   0 2                            8

   1 0                            12

   0

   1

   2

 以下の図は時刻0 のマスの色の様子を表す.黒色であるマスは2 個あるため,1 つ目の質問に対する答え

は2 である.





                    セルオートマトン– 3 / 6

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                                cell


 以下の図は時刻1 のマスの色の様子を表す.黒色であるマスは8 個あるため,2 つ目の質問に対する答え

は8 である.





                    セルオートマトン– 4 / 6

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                                cell


 以下の図は時刻2 のマスの色の様子を表す.黒色であるマスは12 個あるため,3 つ目の質問に対する答

えは12 である.





 この入力例は小課題1, 2, 6, 7 の制約を満たす.





                    セルオートマトン– 5 / 6

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                JOI Open Contest

                                                                          August 5, 2023


                                                                               cell


 入力例2              出力例2

 3 5                            3

 0 0                            12

 2 2                            21

 5 5                            24

 0                              26

 1

 2

 3

 4

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


 入力例3              出力例3

 4 10                           4

 -3 -3                          16

 3 3                            32

 -4 4                           48

 4 -4                           56

 0                              56

 1                              55

 2                              56

 3                              60

 4                              64

 5

 6

 7

 8

 9

この入力例は小課題1, 2, 6, 7 の制約を満たす.





                   セルオートマトン– 6 / 6