← 返回题目列表

AtCoder · joisc2008_election2

election2. 选举

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

選挙 (Election) - 原题 PDF 第 1 页
原题PDF第4页
選挙 (Election) - 原题 PDF 第 2 页
原题PDF第5页
選挙 (Election) - 原题 PDF 第 3 页
原题PDF第6页
選挙 (Election) - 原题 PDF 第 4 页
原题PDF第7页
可复制的 PDF 提取文本
Election: 選挙

出力のみの課題(OUTPUT ONLY TASK)・相対評価



input ファイル“election-ink” (k = 1, 2, 3, 4, 5)
output ファイル“election-outk” (k = 1, 2, 3, 4, 5)


  JOI 国で大統領選挙が行われることになった.その国にはn 個の都市S1, . . . , Sn があり,それ

ぞれの都市の位置は座標を用いてS1(x1, y1), . . . , Sn(xn, yn) で表される.都市Si には選挙権を持

つ有権者がpi 人住んでいる.同じ座標に2 つ以上の都市が存在することはない.都市Si と都市

Sj の距離は               √
                                         (xi −xj)2 + (yi −yj)2

である.

 あなたは,候補者の1 人であるA 候補の選挙参謀であり,A 候補のスケジュール管理を行っ

ている.選挙運動の期間はm 日間である.選挙運動の期間中,1 日あたり1 つの都市において,

A 候補の演説会を行うことにした.A 候補は演説の名手であり,ある都市でA 候補の演説会が

行われると,演説会が行われた都市の有権者は全員がA 候補に確実に投票することが知られて

いる.さらに驚くべきことに,演説会の効果は距離d 以下の都市にも波及する.すなわち,あ

る都市でA 候補の演説会が行われると,その都市からの距離がd 以下の都市の有権者も全員が

A 候補に確実に投票する.

 あなたの仕事は,できるだけ多くの有権者がA 候補に確実に投票するように,A 候補が演説

会を行うm 個の都市を選ぶことである.

 入力として都市の数n,選挙運動の日数m,演説会の効果が波及する距離d,それぞれの都市

の座標とそこに住む有権者の数が与えられたとき,A 候補の演説会が行われた都市からの距離

がd 以下の都市に住む有権者の総数ができるだけ多くなるように演説会の場所を選べ.


Input. 入力データは全部で5 つあり,ファイル名はelection-ink (k = 1, 2, 3, 4, 5) である.

 入力ファイルの1 行目には都市の数n (1 ≦n ≦10000) が書かれている.2 行目には選挙運

動の日数m (1 ≦m ≦1000, m ≦n) が書かれている.3 行目には演説会の効果が波及する距離

d (1 ≦d ≦5000) が書かれている.続くn 行は,各都市の座標とそこに住む有権者の数を表す.

i + 3 行目(1 ≦i ≦n) には3 つの整数xi, yi, pi (0 ≦xi, yi ≦5000, 1 ≦pi ≦10000) が空白を

区切りとして書かれており,都市Si の座標が(xi, yi) で,そこにpi 人の有権者が住んでいるこ

とを表す.




                            選挙–1/4

Output. 出力データはファイルで提出せよ.出力ファイルのファイル名はelection-outk

(k = 1, 2, 3, 4, 5) である.election-outk には,election-ink に対応した出力データを書け.

 各出力ファイルは全部でm + 1 行からなる.1 行目からm 行目にはA 候補が演説を行う都市

の番号を1 個ずつ書け.都市の番号は1 以上n 以下の整数である.都市の番号を書く順番は問

わないが,重複があってはならない.また,m + 1 行目には,A 候補の演説会が行われた都市

からの距離がd 以下の都市に住む有権者の総数を書け.

 出力ファイルのみを提出すること.出力ファイルを作成する際に,プログラムを作成し利用

してもよいし,しなくてもよい.プログラムの出力をそのまま提出しても良いし,必要に応じ

てテキストエディタなどで加工してから提出してもよい.また,テストデータごとに異なるプ

ログラムを作成してもよい.


モデル解法. この問題の解法として,次のようなものが考えられる.

 まず,各都市S1, . . . , Sn に対し,その都市を中心とした半径d の円内に住む有権者の総数を

計算する.その値が最も大きい都市をSi1 とおく.(もし総数が等しい都市が複数個あったら,そ
の中で添字i が最も小さい都市Si を選び,それをSi1 とおく.)S1, . . . , Sn から,Si1 からの距離
がd 以下の都市を全て取り除き,残った都市に対して同様の計算を行い,都市Si2 を選ぶ.これ
をm 回繰り返して,m 個の都市Si1, . . . , Sim を順に選ぶ.Si1, . . . , Sim において演説会を行う.

 この解法では,必ずしも最適解が得られるとは限らない.なお,もし途中で全ての都市が取

り除かれてしまった場合,JOI 国に住む全ての有権者がA 候補に投票することになるから,そ

の場合は最適解を与えることが分かる.


採点方法について. 入力データは全部で5 つある.それぞれの入力データごとに配点を定め,以

下の要領で採点を行う.(配点はoverview sheet に記載してある.)

 あなたが提出した解答におけるA 候補の演説会が行われた都市からの距離がd 以下の都市に

住む有権者の総数をT,モデル解法によって得られる値をTmodel,提出された全てのデータの

うちA 候補に確実に投票する有権者の総数が最も多いものをTmax とおく.

   • 出力データが未提出の場合や,出力データが誤っている場合は,その出力データに関する

   得点は0 点である.

   • T < Tmodel の場合の得点は0 点である.

   • T ≧Tmodel の場合は相対評価により採点を行う.

     Tmax = Tmodel(= T) の場合: すなわち,モデル解法を上回るデータの提出者がいなかった

     場合は,配点の20%分の得点が与えられる.
                     (              )
                              T −Tmodel
     Tmax > Tmodel の場合: 配点の         × 80 + 20 % 分の得点が与えられる.
                                  Tmax −Tmodel

                            選挙–2/4

例

  入力例  出力例
   15        2
   3         8
   4         10
   4 2 22    661
   1 2 58
   7 6 27
   2 3 28
   8 7 57
   9 9 96
   5 0 46
   3 8 72
   9 2 52
   9 6 53
   2 7 17
   0 3 53
   4 8 70
   4 1 4
   5 6 52



 この入力例において都市の数はn = 15 である.選挙運動の日数はm = 3 日間である.また,

演説会の効果が波及する距離はd = 4 である.


 この入力例に対してモデル解法を適用してみよう.

 まず,各都市S1, . . . , S15 に対し,そこを中心とした半径4 の円内に住む有権者の総数を求め

る.そして,その値が最も大きい都市を選ぶ.この場合,S3 がそのような都市であり,S3 を中

心とした半径4 の円内には,S3, S5, S6, S10, S13, S15 の6 つの都市が含まれる.そこに住む有権

者の総数は355 人である.

 この6 つの都市を除いて同様の計算を行い,都市S4 を選ぶ.S4 を中心とした半径4 の円内に

は,S1, S2, S4, S11, S12, S14 の6 つの都市が含まれており,そこに住む有権者の総数は182 人で

ある.

 これらの都市を除き,残った3 つの都市S7, S8, S9 に対して同様の計算を行い,都市S8 を選

ぶ.残った都市の中で,S8 を中心とした半径4 の円内に含まれているのはS8 のみである.S8 に

は72 人の有権者が住んでいる.

 したがって,モデル解法により,S3, S4, S8 の3 つの都市が演説会の会場として選ばれ,それ

らの都市からの距離がd 以下の都市に住む有権者の総数は609 人となる.


                            選挙–3/4

3 つの都市S2, S8, S10 でA 候補の演説会を行う場合を考えよう.

  S2 を中心とした半径4 の円内には,S1, S2, S4, S12, S14 の5 つの都市がある.S8 を中心とし

た半径4 の円内には,S8, S11, S13, S15 の4 つの都市がある.S10 を中心とした半径4 の円内に

は,S3, S5, S6, S9, S10, S15 の6 つの都市がある.したがって,演説会の会場であるS2, S8, S10

と,上に挙げた都市のいずれかに住む有権者はA 候補に確実に投票する.S7 を除く14 個の都

市の有権者がA 候補に確実に投票することになり,その総数は661 人である.これは,モデル

解法により得られた人数よりも多い.また,これが,A 候補の演説会が行われた都市からの距

離がd 以下の都市に住む有権者の総数の最大値である.

 この例からも,モデル解法では,必ずしも最適な結果が得られるわけではないことが分かる.




                 y

                                                                S6

                                  S8   S13

                               S11                           S5

                                                S15       S3         S10





                    S12       S4

                        S2             S1                       S9

                                          S14

                                            S7
                                                           x





                            選挙–4/4