← 返回题目列表

AtCoder · joisc2016_l

L. 最差记者2

中文机器翻译题面 查看原题

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

最悪の記者2 - 原题 PDF 第 1 页
原题PDF第14页
最悪の記者2 - 原题 PDF 第 2 页
原题PDF第15页
最悪の記者2 - 原题 PDF 第 3 页
原始PDF第16号
最悪の記者2 - 原题 PDF 第 4 页
原题PDF第17页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                  Contest Day 4 – Worst Reporter 2


           最悪の記者2 (Worst Reporter 2)



 時は21XX 年,競技プログラミングはマインドスポーツの1 つとして広く認知されており,テレビ,新
聞などのメディアで取り上げられることも多い.
 あなたはJOI 新聞社の記者であり,競技プログラミングの記事を担当している.
 昨日,N 人の選手による国際的な競技プログラミングのコンテストが開催された.このコンテストにつ
いての記事を書くために,あなたには次の情報が与えられた.

   • 国際情報オリンピックなどと同様,このコンテストにはいくつかの国から選手が参加した.国には1
   からN までのいずれかの番号が付けられている.一つの国から複数の選手が参加することもあり得
   る.また,選手が参加しない国があるかもしれない.

   • このコンテストの競技時間は5 時間である.

   • コンテスト中に選手の獲得した点数が,その後減らされることはない.

   • コンテスト開始後2 時間経過した時点において,同点の選手はいなかった.その時点の順位表におい
   て,i 位(1 ≦i ≦N) の選手は国Ai の出身で,その選手の点数はBi 点であった.

   • コンテスト終了時点において,同点の選手はいなかった.コンテスト終了時点の順位表において,i
    位(1 ≦i ≦N) の選手は国Ci の出身で,その選手の点数はDi 点であった.

 しかしながら,記事を書く段階になって,順位表の出身国の表示に不具合があったことが判明した.選
手の出身国の情報が間違って表示されていた可能性がある.表示されていた選手の点数は正しいことが分
かっている.
 そこで,あなたは,与えられた情報にできるだけ少ない修正を加えることで,順位表の情報として矛盾
のない(同じ選手の出身国がコンテスト中に変わったり,選手の獲得した点数がコンテスト中に減少したり
しない) ものを推測することにした.すなわち,2N 個の値A1, . . . , AN,C1, . . . ,CN のうちのできるだけ少な
い箇所を変更することで,次の条件を満たすようにしたい:

   • 1, 2, . . . , N のある並び替えx1, x2, . . . , xN であって,各i = 1, 2, . . . , N に対してAi = Cxi かつBi ≦Dxi
   が成り立つものが存在する.

 あなたは,与えられた情報に,最少で何箇所の修正を加える必要があるだろうか.


課題

 コンテストの参加者数と,コンテスト開始後2 時間経過した時点とコンテスト終了時点の順位表につい
ての情報が与えられたとき,順位表を矛盾のない状態にするために必要な,出身国情報の変更箇所の個数
の最小値を求めるプログラムを作成せよ.





                     最悪の記者2– 1 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                  Contest Day 4 – Worst Reporter 2


入力

 標準入力から以下のデータを読み込め.

   • 1 行目には,整数N が書かれている.これは,コンテストにN 人の選手が参加したことを表す.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai, Bi が空白を区切りとして書かれている.これは,
   コンテスト開始後2 時間経過した時点の順位表において,i 位の選手は国Ai 出身と表示され,獲得し
   た点数はBi 点であったことを表す.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ci, Di が空白を区切りとして書かれている.これは,
   コンテスト終了時点の順位表において,i 位の選手は国Ci 出身と表示され,獲得した点数はDi 点で
   あったことを表す.


出力

 標準出力に,順位表を矛盾のない状態にするために必要な,出身国情報の変更箇所の個数の最小値を1
行で出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 2 ≦N ≦200 000.

   • 1 ≦Ai ≦N (1 ≦i ≦N).

   • 0 ≦Bi ≦1 000 000 000 (1 ≦i ≦N).

   • Bi > Bi+1 (1 ≦i ≦N −1).

   • 1 ≦Ci ≦N (1 ≦i ≦N).

   • 0 ≦Di ≦1 000 000 000 (1 ≦i ≦N).

   • Di > Di+1 (1 ≦i ≦N −1).

   • A1, . . . , AN,C1, . . . ,CN の値を何箇所か変更することにより,順位表を矛盾のない状態にすることがで
   きる.


小課題

小課題1 [15 点]

   • N ≦16 を満たす.



                     最悪の記者2– 2 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                  Contest Day 4 – Worst Reporter 2


小課題2 [15 点]

   • N ≦50 を満たす.


小課題3 [30 点]

   • N ≦5000 を満たす.


小課題4 [40 点]

 追加の制約はない.


入出力例

  入力例1        出力例1
   3                    1
   3 500
   2 200
   1 100
   1 1000
   3 700
   3 400

  C3 の値を2 に修正すると,次のように矛盾のない順位表になる:

   • コンテスト開始後2 時間経過した時点において500 点で1 位だった国3 出身の選手は,コンテスト
   終了時点において700 点で2 位となった.

   • コンテスト開始後2 時間経過した時点において200 点で2 位だった国2 出身の選手は,コンテスト
   終了時点において400 点で3 位となった.

   • コンテスト開始後2 時間経過した時点において100 点で3 位だった国1 出身の選手は,コンテスト
   終了時点において1000 点で1 位となった.

 ここで,C2 の値を2 に修正した場合,国3 出身の選手がコンテスト開始後2 時間経過した時点において
500 点を獲得しているにも関わらず,コンテスト終了時点において400 点となっているため,矛盾した順
位表となる.
  1 箇所より少ない修正によって矛盾のない順位表を得ることは不可能であるから,1 を出力する.





                     最悪の記者2– 3 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                  Contest Day 4 – Worst Reporter 2



  入力例2        出力例2
   3                    0
   3 3
   3 2
   1 1
   3 4
   3 2
   1 1

 この場合,出身国情報を修正しなくても矛盾のない順位表となっている.コンテスト開始後2 時間経過
した時点の点数から点数を増やしていない選手が存在するかもしれないことに注意せよ.また,順位表に
おいて,同じ出身国の選手が複数いる可能性があることに注意せよ.



  入力例3        出力例3
   6                    3
   1 70
   4 50
   1 30
   2 20
   1 10
   3 0
   6 100
   2 90
   1 80
   2 60
   4 40
   1 10

 この入力例において,A1 の値を2 に修正し,A6 の値を4 に修正し,C1 の値を4 に修正すると,矛盾の
ない順位表になる.





                     最悪の記者2– 4 / 4