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




可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Abduction 2
誘拐2 (Abduction 2)
ある晴天の日のこと,ある交差点で,誘拐事件が発生した.犯人はAnna とBruno であり,二人は車に
乗って誘拐現場から逃走したと考えられている.誘拐犯の車は未だ見つかっておらず,警察は今なお車の
行方を追っている.
誘拐犯の車の走った市街地は,東西にのびる道路がH 本,南北にのびる道路がW 本走る碁盤目状の街
である.2 つの隣接する交差点間の距離は,1 キロメートルである.
それぞれの道路について,人通りの多さを表す整数が与えられる.北からi 本目(1 ≦i ≦H) の東西方向
の道路の人通りの多さはAi であり,西からj 本目(1 ≦j ≦W) の南北方向の道路の人通りの多さはBj で
ある.これらH + W 個の値は互いに異なる.それぞれの道路について,道路の人通りの多さは,道路上の
どの地点においても同じである.
また,警察による捜査の結果,誘拐犯は市街地で移動する際,次のような方法で移動をしていたことが
明らかとなった.
• 市街地の外や,道路ではない場所に出ることはない.
• 最初は,誘拐犯は,誘拐した交差点から移動可能な方向のうちどれか1 つを選んで移動する.
• ある交差点に差し掛かったとき,今まで移動してきた道路よりも交わっている道路の方が人通りが多
いときは,その交差点で曲がる.もし,2 方向どちらにも曲がることができる場合は,どちらを選ん
だ可能性もある.
• ある交差点に差し掛かったとき,今まで移動してきた道路の方が交わっている道路よりも人通りが多
いときは,そのまま直進する.ただし,市街地の端におり直進できないときは,そこで移動を終了
する.
誘拐現場の候補地として,Q 箇所の交差点が候補に挙がっている.Q 箇所の候補地は互いに異なる.警
察は,調査チームの人数を決めるときの参考として,それぞれの誘拐現場の候補地に対し,誘拐事件がそ
こで発生したと仮定したとき,誘拐犯がその場所から最長で何キロメートル移動できるかを知りたい.
Q 個のクエリについて,与えられた誘拐現場の候補地から移動可能な経路の最長の長さを求めよ.
課題
市街地の道路の人通りの多さと,Q 箇所の誘拐現場の候補地が与えられたとき,それぞれの候補地から
移動可能な経路の長さの最大値を求めるプログラムを作成せよ.
誘拐2– 1 / 4
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Abduction 2
入力
標準入力から以下の入力を読み込め.
• 1 行目には,3 個の整数H, W, Q が空白を区切りとして書かれている.これは,市街地は東西方向に
のびるH 本の道路と南北方向にのびるW 本の道路からなり,誘拐現場の候補地としてQ 箇所が与
えられることを表す.
• 2 行目には,H 個の整数A1, A2, . . . , AH が空白を区切りとして書かれている.これは,北からi 本目
(1 ≦i ≦H) の東西方向の道路の人通りの多さがAi であることを表す.
• 3 行目には,W 個の整数B1, B2, . . . , BW が空白を区切りとして書かれている.これは,西からj 本目
(1 ≦j ≦W) の南北方向の道路の人通りの多さがBj であることを表す.
• 続くQ 行のうちのk 行目(1 ≦k ≦Q) には,2 個の整数S k, Tk が空白を区切りとして書かれている.
これは,k 番目の誘拐現場の候補地が,北からS k 本目の東西方向の道路と西からTk 本目の南北方
向の道路の交差点であることを表す.
出力
標準出力にQ 行出力せよ.k 行目(1 ≦k ≦Q) には,k 番目の誘拐現場の候補地から移動を開始したと
きの移動可能な経路の長さの最大値を,キロメートル単位で出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 2 ≦H ≦50 000.
• 2 ≦W ≦50 000.
• 1 ≦Q ≦100.
• 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦H).
• 1 ≦Bj ≦1 000 000 000 (1 ≦j ≦W).
• H + W 個の整数A1, A2, . . . , AH, B1, B2, . . . , BW は互いに異なる.
• 1 ≦S k ≦H (1 ≦k ≦Q).
• 1 ≦Tk ≦W (1 ≦k ≦Q).
• (S k, Tk) , (S l, Tl) (1 ≦k < l ≦Q).
誘拐2– 2 / 4
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Abduction 2
小課題
この課題では小課題は全部で5 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [13 点]
• H ≦8.
• W ≦8.
• Q = 1.
小課題2 [10 点]
• H ≦2 000.
• W ≦2 000.
• Q = 1.
小課題3 [17 点]
• Q = 1.
小課題4 [4 点]
• H ≦2 000.
• W ≦2 000.
小課題5 [56 点]
追加の制限はない.
誘拐2– 3 / 4
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Abduction 2
入出力例
入力例1 出力例1
3 3 5 4
3 2 6 5
1 4 5 4
1 1 4
1 2 2
2 2
3 1
3 3
例えば,3 番目のクエリに関しては,次のように移動する場合が最長となる.
• 北から2 本目の道路と西から2 本目の道路の交差点から,東方向に1 キロメートル移動する.
• 北から2 本目の道路と西から3 本目の道路の交差点からは,南もしくは北に移動可能であり,南方
向に1 キロメートル移動する.
• 北から3 本目の道路と西から3 本目の道路の交差点からは,西にのみ移動可能であり,西方向に1 キ
ロメートル移動する.
• 北から3 本目の道路と西から2 本目の道路の交差点からは,西にのみ移動可能であり,西方向に1 キ
ロメートル移動する.
• 北から3 本目の道路と西から1 本目の道路の交差点からは,もうどの方向にも移動することはでき
ないので,ここで移動を終了する.
このように移動すると,移動した経路の長さは4 キロメートルとなる.
入力例2 出力例2
4 5 6 7
30 10 40 20 6
15 55 25 35 45 9
1 3 4
4 3 6
2 2 9
4 1
2 5
3 3
誘拐2– 4 / 4