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






可复制的 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