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








可复制的 PDF 提取文本
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
JOIG ツアー(JOIG Tour)
あなたはJust Odd Ink 街道を知っているだろうか?この街道はEGOI 国を東西に横断する長さ10100 の街
道であり,「ただ奇妙なインク(just odd ink)」によって描かれたたくさんのアートで有名である.ここでは
略してJOI 街道と呼ぶ.
さて,JOI 街道には大小様々なアートが描かれているが,そのうちいくつかは文字が描かれているように
見える.
JOI 街道のツアーガイドである理恵さんは,JOIG 春合宿の参加者を案内することになった.JOIG 春合宿
の参加者を喜ばせたい理恵さんは,JOI 街道に描かれているアートのうち,‘J’, ‘O’, ‘I’, ‘G’ と読めるアート
をこの順に訪れるツアーの計画を考えている.訪れる候補となるアートはN 個あり,i 番目(1 ≦i ≦N) の
アートはJOI 街道の西端から距離Ai の地点にあり,このアートはCi と読める.
理恵さんはQ 個の計画を考えている.j 番目(1 ≦j ≦Q) の計画におけるツアーでは,以下の順に移動を
行う.
1. JOI 街道の西端から距離S j の地点からツアーを開始する.
2. ‘J’ と読めるアートがある地点を1 つ選び,その地点に移動する.
3. ‘O’ と読めるアートがある地点を1 つ選び,その地点に移動する.
4. ‘I’ と読めるアートがある地点を1 つ選び,その地点に移動する.
5. ‘G’ と読めるアートがある地点を1 つ選び,その地点に移動する.
6. JOI 街道の西端から距離T j の地点に移動し,ツアーを終了する.
ただし,ツアーの経路はJOI 街道を外れないものとする.
理恵さんはこの条件のもと,それぞれの計画についてなるべくツアーの総移動距離を短くしたい.
JOI 街道のアートの情報と理恵さんの計画の情報が与えられたとき,それぞれの計画について,ツアーの
総移動距離の最小値を求めるプログラムを作成せよ.
JOIG ツアー– 1 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力
入力は以下の形式で標準入力から与えられる.
N
A1 C1
A2 C2
...
AN CN
Q
S 1 T1
S 2 T2
...
S Q TQ
出力
標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,理恵さんのj 番目の計画におけるツアーの総移動
距離の最小値を出力せよ.
制約
• 4 ≦N ≦100 000.
• 1 ≦Ai ≦1 000 000 000 000 000 (= 1015) (1 ≦i ≦N).
• Ai < Ai+1 (1 ≦i ≦N −1).
• Ci (1 ≦i ≦N) は‘J’,‘O’,‘I’,‘G’ のいずれかである.
• Ci が‘J’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
• Ci が‘O’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
• Ci が‘I’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
• Ci が‘G’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
• 1 ≦Q ≦100 000.
• 1 ≦S j ≦1 000 000 000 000 000 (= 1015) (1 ≦j ≦Q).
• 1 ≦T j ≦1 000 000 000 000 000 (= 1015) (1 ≦j ≦Q).
• (S j, T j) , (S k, Tk) (1 ≦j < k ≦Q).
JOIG ツアー– 2 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
• N, Q は整数である.
• Ai は整数である(1 ≦i ≦N).
• S j, T j は整数である(1 ≦j ≦Q).
小課題
1. (4 点) N ≦80,Q ≦10.
2. (10 点) N ≦500,Q ≦10.
3. (6 点) N ≦3 000,Q ≦100.
4. (25 点) N ≦5 000,Q ≦1 000.
5. (12 点) Ci が‘O’ であるようなi (1 ≦i ≦N),C j が‘I’ であるようなj (1 ≦j ≦N),Ck が‘G’ である
ようなk (1 ≦k ≦N) はそれぞれただ1 つ存在する.
6. (8 点) Ci が‘O’ であるようなi (1 ≦i ≦N) ,C j が‘I’ であるようなj (1 ≦j ≦N) はそれぞれただ1
つ存在する.
7. (20 点) Ci が‘O’ であるようなi (1 ≦i ≦N) はただ1 つ存在する.
8. (15 点) 追加の制約はない.
入出力例
入力例1 出力例1
7 7
1 J 12
2 O
3 G
4 I
5 O
8 G
10 J
2
3 2
7 5
JOIG ツアー– 3 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
1 番目の計画は,JOI 街道の西端から距離3 の地点からツアーを開始し,西端から距離2 の地点でツアー
を終了するというものである.例えば,以下のように移動することで,ツアーの総移動距離を7 とすること
ができる.
1. JOI 街道の西端から距離3 の地点からツアーを開始する.
2. 西に距離2 だけ移動し,JOI 街道の西端から距離1 の地点にある‘J’ と読めるアートを訪れる.
3. 東に距離1 だけ移動し,JOI 街道の西端から距離2 の地点にある‘O’ と読めるアートを訪れる.
4. 東に距離2 だけ移動し,JOI 街道の西端から距離4 の地点にある‘I’ と読めるアートを訪れる.
5. 西に距離1 だけ移動し,JOI 街道の西端から距離3 の地点にある‘G’ と読めるアートを訪れる.
6. 西に距離1 だけ移動し,JOI 街道の西端から距離2 の地点でツアーを終了する.
ツアーの総移動距離を7 未満にすることはできないため,7 を1 行目に出力する.
2 番目の計画は,JOI 街道の西端から距離7 の地点からツアーを開始し,西端から距離5 の地点でツアー
を終了するというものである.例えば,以下のように移動することで,ツアーの総移動距離を12 とするこ
とができる.
1. JOI 街道の西端から距離7 の地点からツアーを開始する.
2. 東に距離3 だけ移動し,JOI 街道の西端から距離10 の地点にある‘J’ と読めるアートを訪れる.
3. 西に距離5 だけ移動し,JOI 街道の西端から距離5 の地点にある‘O’ と読めるアートを訪れる.
4. 西に距離1 だけ移動し,JOI 街道の西端から距離4 の地点にある‘I’ と読めるアートを訪れる.
5. 西に距離1 だけ移動し,JOI 街道の西端から距離3 の地点にある‘G’ と読めるアートを訪れる.
6. 東に距離2 だけ移動し,JOI 街道の西端から距離5 の地点でツアーを終了する.
ツアーの総移動距離を12 未満にすることはできないため,12 を2 行目に出力する.
この入力例は小課題1, 2, 3, 4, 8 の制約を満たす.
JOIG ツアー– 4 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例2 出力例2
10 13
5 J 19
7 O 20
10 J 21
11 G
12 J
13 I
17 J
18 J
19 J
20 J
4
4 9
15 14
6 20
7 20
この入力例はすべての小課題の制約を満たす.
JOIG ツアー– 5 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例3 出力例3
10 25
1 G 27
2 J 28
3 G 17
4 O 26
7 G 39
9 J 30
10 G
14 I
17 G
19 G
7
11 6
6 3
17 19
1 18
17 17
20 1
20 10
この入力例は小課題1, 2, 3, 4, 6, 7, 8 の制約を満たす.
JOIG ツアー– 6 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例4 出力例4
10 12
3 J 17
5 G 15
6 I 15
7 I 19
8 J 12
9 I
10 O
14 G
16 I
19 J
6
4 4
20 3
18 5
15 4
20 11
10 8
この入力例は小課題1, 2, 3, 4, 7, 8 の制約を満たす.
JOIG ツアー– 7 / 8
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例5 出力例5
12 583302366935305
179948747891578 I 805077987955000
263779425244614 I 591304613119987
320153642407146 G 757352272699625
383698990675423 J 478217003098189
478483318441339 J 869691499240121
505589213620811 G 805495866954969
507468309040564 O 1085532869547991
530441288489671 J 928541333618299
730036011088087 O 1205618838253516
896127332008998 I
899298512463927 O
915990785839829 J
10
744829561026263 366031656398270
700496830781726 684771674298690
314138534887378 222241904398827
695615197615084 632164325876673
418419052313523 409258287819812
932490604948180 62799105708059
738126150487131 45378717857226
320047965627255 918203067583346
859632377126681 967370566306944
115848334010451 834089404672067
この入力例は小課題1, 2, 3, 4, 8 の制約を満たす.
JOIG ツアー– 8 / 8