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




可复制的 PDF 提取文本
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
heat
熱中症(Heat Stroke)
JOI 島は東西一列に並んだL 個の地区からなり,各地区は西から順に1 からL までの番号が付けられて
いる.また,JOI 島にはL −1 本の道路があり,具体的には各1 ≦i ≦L −1 について,地区i と地区i + 1 を
双方向に結ぶ道路がある.ここで,地区i と地区i + 1 を結ぶ道路は,道路i と呼ばれている.
道路1 道路2
地区1 地区2 地区3 … 地区𝐿
さて,20XX 年,国際情報オリンピックがJOI 島で開催されることになった.JOI 島は酷暑で有名な島で
あるため,暑さに慣れていない海外の選手にとって,熱中症のリスクが高い.そこで国際情報オリンピック
の運営は,次のような対策を立てることにした.
• 各地区i (1 ≦i ≦L) に,Ci 人が入院できる病院を準備する.ただしCi = 0 の場合もある.
• 国際情報オリンピックの開催期間中,道路x (1 ≦x ≦L −1) 上で熱中症患者が発生した場合,次のよ
うな手順にしたがって患者を搬送し,入院させる.
– その時点で,地区x の病院と地区x + 1 の病院のうち入院できる方に救急車で搬送し,入院させ
る.両方に入院できる場合はどちらに搬送される可能性もある.どちらの病院にも入院できない
場合は,ドクターヘリで島外の総合病院に搬送し,入院させる.
しかし,ドクターヘリでの搬送は費用がかかるため,運営は最大何人の患者がドクターヘリで搬送される
かを知りたい.そこで1 つのシナリオとして,以下を考える.
• 国際情報オリンピックが始まった時点では,どの病院にも入院患者がいない.
• 国際情報オリンピックの開催期間中,合計N 人の熱中症患者が発生する.j 番目(1 ≦j ≦N) の患者
は道路Xj 上で熱中症になる.
• 各1 ≦j ≦N −1 について,j + 1 番目の患者が熱中症になった時点では,j 番目までの患者は既に入
院している.また,熱中症患者はみな重症であるため,開催期間中に退院することはない.
地区の数,病院および熱中症患者に関する情報が与えられたとき,上記のシナリオにおいて,最大何人の
患者がドクターヘリで搬送されるかを求めるプログラムを作成せよ.
熱中症– 1 / 4
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
heat
入力
入力は以下の形式で標準入力から与えられる.
L
C1 C2 · · · CL
N
X1 X2 · · · XN
出力
標準出力に,最大何人の患者がドクターヘリで搬送されるかを1 行で出力せよ.
制約
• 2 ≦L ≦8 000.
• 0 ≦Ci ≦8 000 (1 ≦i ≦L).
• 1 ≦N ≦8 000.
• 1 ≦X j ≦L −1 (1 ≦j ≦N).
• 入力される値はすべて整数である.
小課題
1. (6 点) X1 ≦X2 ≦· · · ≦XN.
2. (7 点) L ≦18,N ≦18,Ci = 1 (1 ≦i ≦L).
3. (7 点) L ≦18,N ≦100,Ci = 1 (1 ≦i ≦L).
4. (25 点) L ≦100,N ≦100,Ci = 1 (1 ≦i ≦L).
5. (25 点) L ≦100,N ≦100.
6. (10 点) L ≦600,N ≦600.
7. (15 点) L ≦3 500,N ≦3 500.
8. (5 点) 追加の制約はない.
熱中症– 2 / 4
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
heat
入出力例
入力例1 出力例1
3 1
1 1 1
3
1 2 2
以下のようなケースの場合,1 人の患者がドクターヘリで搬送される.
1. 1 番目の患者を地区2 の病院に搬送し,入院させる.地区1, 2, 3 の病院における入院者数が0, 1, 0 人
になる.
2. 2 番目の患者を地区3 の病院に搬送し,入院させる.地区1, 2, 3 の病院における入院者数が0, 1, 1 人
になる.
3. 3 番目の患者については,地区2 と地区3 の両方の病院が既に入院できない状態になっているため,
ドクターヘリで搬送し,入院させる.
2 人以上の患者がドクターヘリで搬送されるようなケースはないため,1 を出力する.
この入力例は小課題1, 2, 3, 4, 5, 6, 7, 8 の制約を満たす.
入力例2 出力例2
6 3
1 1 1 1 1 1
7
1 3 5 4 2 2 3
以下のようなケースの場合,3 人の患者がドクターヘリで搬送される.
1. 1 番目の患者を地区2 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が
0, 1, 0, 0, 0, 0 人になる.
2. 2 番目の患者を地区4 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が
0, 1, 0, 1, 0, 0 人になる.
3. 3 番目の患者を地区5 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が
0, 1, 0, 1, 1, 0 人になる.
4. 4 番目の患者については,地区4 と地区5 の両方の病院が既に入院できない状態になっているため,
ドクターヘリで搬送し,入院させる.
熱中症– 3 / 4
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
heat
5. 5 番目の患者を地区3 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が
0, 1, 1, 1, 1, 0 人になる.
6. 6 番目の患者については,地区2 と地区3 の両方の病院が既に入院できない状態になっているため,
ドクターヘリで搬送し,入院させる.
7. 7 番目の患者については,地区3 と地区4 の両方の病院が既に入院できない状態になっているため,
ドクターヘリで搬送し,入院させる.
4 人以上の患者がドクターヘリで搬送されるようなケースはないため,3 を出力する.
この入力例は小課題2, 3, 4, 5, 6, 7, 8 の制約を満たす.
入力例3 出力例3
6 1
4000 1 1 0 4000 1
5
1 1 2 3 5
この入力例は小課題1, 5, 6, 7, 8 の制約を満たす.
入力例4 出力例4
5 2
1 2 2 2 1
8
2 3 2 1 4 1 2 3
この入力例は小課題5, 6, 7, 8 の制約を満たす.
入力例5 出力例5
10 3
2 2 2 2 2 2 2 2 2 2
18
1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8
この入力例は小課題5, 6, 7, 8 の制約を満たす.
熱中症– 4 / 4