시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 46 | 23 | 15 | 46.875% |
時は 21XX 年,競技プログラミングはマインドスポーツの 1 つとして広く認知されており,テレビ,新 聞などのメディアで取り上げられることも多い.
あなたは JOI 新聞社の記者であり,競技プログラミングの記事を担当している.
昨日,N 人の選手による国際的な競技プログラミングのコンテストが開催された.このコンテストにつ いての記事を書くために,あなたには次の情報が与えられた.
しかしながら,記事を書く段階になって,順位表の出身国の表示に不具合があったことが判明した.選 手の出身国の情報が間違って表示されていた可能性がある.表示されていた選手の点数は正しいことが分 かっている.
そこで,あなたは,与えられた情報にできるだけ少ない修正を加えることで,順位表の情報として矛盾 のない (同じ選手の出身国がコンテスト中に変わったり,選手の獲得した点数がコンテスト中に減少したり しない) ものを推測することにした.すなわち,2N 個の値 A1, . . . , AN, C1, . . . ,CN のうちのできるだけ少な い箇所を変更することで,次の条件を満たすようにしたい:
あなたは,与えられた情報に,最少で何箇所の修正を加える必要があるだろうか.
コンテストの参加者数と,コンテスト開始後 2 時間経過した時点とコンテスト終了時点の順位表につい ての情報が与えられたとき,順位表を矛盾のない状態にするために必要な,出身国情報の変更箇所の個数 の最小値を求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
標準出力に,順位表を矛盾のない状態にするために必要な,出身国情報の変更箇所の個数の最小値を 1 行で出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | N ≦ 16 を満たす. |
2 | 15 | N ≦ 50 を満たす. |
3 | 30 | N ≦ 5000 を満たす. |
4 | 40 | 追加の制約はない. |
3 3 500 2 200 1 100 1 1000 3 700 3 400
1
C3 の値を 2 に修正すると,次のように矛盾のない順位表になる:
ここで,C2 の値を 2 に修正した場合,国 3 出身の選手がコンテスト開始後 2 時間経過した時点において 500 点を獲得しているにも関わらず,コンテスト終了時点において 400 点となっているため,矛盾した順 位表となる.
1 箇所より少ない修正によって矛盾のない順位表を得ることは不可能であるから,1 を出力する.
3 3 3 3 2 1 1 3 4 3 2 1 1
0
この場合,出身国情報を修正しなくても矛盾のない順位表となっている.コンテスト開始後 2 時間経過 した時点の点数から点数を増やしていない選手が存在するかもしれないことに注意せよ.また,順位表に おいて,同じ出身国の選手が複数いる可能性があることに注意せよ.
6 1 70 4 50 1 30 2 20 1 10 3 0 6 100 2 90 1 80 2 60 4 40 1 10
3
この入力例において,A1 の値を 2 に修正し,A6 の値を 4 に修正し,C1 の値を 4 に修正すると,矛盾の ない順位表になる.