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





可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 4 – Worst Reporter 4
最悪の記者4 (Worst Reporter 4)
ビ太郎の職業は記者であり,主に競技プログラミングに関する記事を執筆している.数日後に国際的な競
技プログラミングの大会が開催されるため,ビ太郎はこの大会についての記事を執筆することにした.
この大会にはN 人の選手が参加予定であり,選手には1 からN までの番号が付けられている.また,各
選手には競技プログラミングの強さの指標となるレーティングが定まっている.なお,レーティングは1 以
上1 000 000 000 以下の整数で表される.
ビ太郎は各選手にインタビューを行い以下の情報を得た.
選手i (1 ≦i ≦N) のレーティングは選手Ai (1 ≦Ai ≦N) のレーティング以上である.(ここで,
Ai = i となるかもしれないことに注意せよ.)
すべてのインタビューを終えた後,ビ太郎はレーティングのシステムを管理する会社から各選手のレー
ティングが書かれた表を受け取った.この表には以下の情報が書かれていた.
選手i (1 ≦i ≦N) のレーティングはHi である.
ビ太郎がこれらの情報をもとに記事を執筆しようとしたところ,各選手のレーティングが書かれた表には
誤りが含まれている可能性があるということが判明した.
記事の締め切りが近いため,正しいレーティングが書かれた表を入手する時間はない.そこで,ビ太郎
は,この表に書かれた選手のレーティングを書き換えることで,インタビューによって得た情報と矛盾しな
いようにすることにした.表に記された選手i (1 ≦i ≦N) のレーティングを書き換えるのにかかるコスト
はCi である.コストCi をかけることで,表に記された選手i のレーティングを1 以上1 000 000 000 以下
の任意の整数に書き換えることができる.記事の締め切りに間に合わせるために,コストの総和をできるだ
け小さくしたい.
選手の人数と,インタビューによって得た情報,レーティングが書かれた表,および,表に記された各選
手のレーティングを書き換えるのにかかるコストが与えられたとき,インタビューによって得た情報と矛盾
しないように表を書き換えるために必要なコストの総和の最小値を求めるプログラムを作成せよ.
最悪の記者4– 1 / 5
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 4 – Worst Reporter 4
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1 H1 C1
...
AN HN CN
出力
標準出力に,必要なコストの総和の最小値を1 行で出力せよ.
制約
• 2 ≦N ≦200 000.
• 1 ≦Ai ≦N (1 ≦i ≦N).
• 1 ≦Hi ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N).
小課題
1. (14 点) N ≦5 000,A1 = 1,Ai ≦i −1 (2 ≦i ≦N).
2. (65 点) A1 = 1,Ai ≦i −1 (2 ≦i ≦N).
3. (21 点) 追加の制約はない.
最悪の記者4– 2 / 5
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 4 – Worst Reporter 4
入出力例
入力例1 出力例1
6 14
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
表に記された各選手のレーティングを以下のように書き換えることで,インタビューによって得た情報と
矛盾しないようにすることができる.
• 選手1 のレーティングを6 から1 に書き換える.このとき,コスト5 がかかる.
• 選手3 のレーティングを8 から4 に書き換える.このとき,コスト4 がかかる.
• 選手5 のレーティングを2 から1 000 000 000 に書き換える.このとき,コスト5 がかかる.
このように書き換えると,コストの総和は5 + 4 + 5 = 14 となる.これが最小値なので14 を出力する.
この入力例は小課題1, 2, 3 の制約を満たす.
入力例2 出力例2
5 0
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1
この入力例では,インタビューによって得た情報と表に記された各選手のレーティングが矛盾しない.し
たがって,必要なコストの総和の最小値は0 である.よって0 を出力する.
最悪の記者4– 3 / 5
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 4 – Worst Reporter 4
入力例3 出力例3
20 2711043927
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
この入力例は小課題1, 2, 3 の制約を満たす.
最悪の記者4– 4 / 5
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 4 – Worst Reporter 4
入力例4 出力例4
20 4012295156
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030
最悪の記者4– 5 / 5