以下页面来自日本信息收集官方发布的原题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 2 – Railway Trip
鉄道旅行(Railway Trip)
JOI 鉄道は1 本の鉄道路線を運営している.JOI 鉄道線には一直線上に並んだN 個の駅があり,それぞ
れ1 以上N 以下の整数で番号がつけられている.各i (1 ≦i ≦N −1) に対して,駅i と駅i + 1 の間は線路
で結ばれている.
JOI 鉄道は,K 種類の列車を双方向に走らせている.列車種別には1 以上K 以下の整数で番号がつけら
れている.また,各駅にはレベルと呼ばれる1 以上K 以下の整数が1 つ定まっており,駅i (1 ≦i ≦N) の
レベルはLi である.両端の駅,すなわち駅1 および駅N のレベルはK である.
種別j (1 ≦j ≦K) の列車はレベルがj 以上の駅すべてに停車し,それ以外の駅には停車しない.両端の
駅,すなわち駅1 および駅N のレベルはK なので,すべての列車が停車する.
毎日多くの利用者がJOI 鉄道線を利用する.JOI 鉄道線を利用する際には,途中で目的地と反対の方向
の列車に乗ったり,目的地を通り過ぎても構わないが,旅程の最後では目的地に停車する必要がある.利
用者は,駅での停車を極端に嫌うため,途中で通過する駅の数や,乗り換えの回数などによらず,できる
だけ途中の停車の回数が少なくなるような経路で駅間を移動しようとする.ただし,乗り換えのための停
車は,1 回の停車と数える.途中の停車の回数には,出発駅や目的地における停車は含めない.
あなたの仕事は,利用者の出発駅と目的地が与えられたときに,この2 駅の間を移動するための途中の
停車の回数の最小値を求めよという質問に回答するプログラムを作成することである.
課題
JOI 鉄道線の情報と,各利用者の出発駅,目的地が与えられたとき,各利用者について,出発駅から目
的地まで移動するための途中の停車の回数の最小値を求めよという質問に回答するプログラムを作成せよ.
入力
標準入力から以下のデータを読み込め.
• 1 行目には,整数N, K, Q が空白を区切りとして書かれている.これは,JOI 鉄道線にはN 個の駅,
K 種類の列車があり,2 駅間の移動の質問がQ 個与えられることを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Li が書かれている.これは,駅i のレベルがLi で
あることを表す.
• 続くQ 行のうちのk 行目(1 ≦k ≦Q) には,整数Ak, Bk が空白を区切りとして書かれている.これ
は,k 番目の利用者の出発駅,目的地がそれぞれ駅Ak,駅Bk であることを表す.
出力
標準出力にQ 行で出力せよ.k 行目(1 ≦k ≦Q) には,駅Ak から駅Bk まで移動するときの,途中の停
車の回数の最小値を出力せよ.
鉄道旅行– 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 2 – Railway Trip
制限
すべての入力データは以下の条件を満たす.
• 2 ≦N ≦100 000.
• 1 ≦K ≦N.
• 1 ≦Q ≦100 000.
• 1 ≦Li ≦K (1 ≦i ≦N).
• 1 ≦Ak ≦N (1 ≦k ≦Q).
• 1 ≦Bk ≦N (1 ≦k ≦Q).
• Ak , Bk (1 ≦k ≦Q).
小課題
この課題では小課題は全部で4 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [5 点]
• N ≦100.
• K ≦100.
• Q ≦50.
小課題2 [15 点]
• Q ≦50.
小課題3 [25 点]
• K ≦20.
小課題4 [55 点]
追加の制限はない.
鉄道旅行– 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 2 – Railway Trip
入出力例
入力例1 出力例1
9 3 3 1
3 3
1 0
1
1
2
2
2
3
3
2 4
4 9
6 7
この入力例では,2 駅間の移動の質問が3 個与えられる.
• 1 番目の質問は,駅2 から駅4 まで移動するものである.このとき,駅2 から駅4 まで種別1 の列
車を利用すると,途中停車する駅は駅3 の1 つのみとなる.
• 2 番目の質問は,駅4 から駅9 まで移動するものである.このとき,まず駅4 から駅5 まで種別1 の
列車を利用し,次に駅5 から駅1 まで種別2 の列車を利用し,最後に駅1 から駅9 まで種別3 の列
車を利用すると,途中停車する駅は順に駅5,駅1,駅8 の3 つとなる.
• 3 番目の質問は,駅6 から駅7 まで移動するものである.このとき,駅6 から駅7 まで種別2 の列
車を利用すると,途中他の駅に停車せずに移動することができる.
入力例2 出力例2
5 2 1 1
2
1
1
1
2
1 4
途中で目的地の駅を通り過ぎても構わないことに注意せよ.
鉄道旅行– 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 2 – Railway Trip
入力例3 出力例3
15 5 15 2
5 1
4 1
1 3
2 2
3 0
1 3
1 4
2 0
4 1
5 3
4 4
1 1
5 2
3 2
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9
鉄道旅行– 4 / 4