ヒューリスティクスという言葉がある。確実にうまくいくという保証はないけれども大抵の場合はうまくいく、比較的単純なアプローチのことだ。単純にして強力であるがゆえに、この世の中は多くのヒューリスティクスで満ち溢れている。
ヒューリスティクスの一例として、こんなものが挙げられる。アニメ番組において、あるキャラクターの人気度は、そのアニメ本編中における登場時間の総和に比例する。確かにこれは多くの場合に成り立っているようだ。しかし、どうやら僕は少数派に属するらしい。影の薄いキャラ、背景にちらりと映るモブキャラなんかに限って可愛く見えたりするのだ。
自分の好きなキャラのことを、他人がどう思っていようがいいじゃないか。とは言ってられない事情が、残念ながらある。関連商品、フィギュアやキャラクターソングCDなどは、人気のあるキャラのものから優先的に発売される傾向にあるのだ。商業的には当然の選択だとはいえ、不人気キャラのファンの肩身は狭い。
そこで重要となってくるのが、アニメ番組の制作会社によって行われる人気投票である。実際の人気がどうであれ、ここで多くの票を獲得すれば、関連商品への道が開かれるのだ。どんな手段を使っても票を集めねばなるまい。
厳正なる投票のために、ある関連商品を1つ購入するたびに1票の投票権が与えられる。この仕組を厳正と呼ぶべきかどうかは今大きく議論されているが、とにかく僕は L 票の投票権を得た。投票の対象となるキャラは全部で N 人いて、より多くの票を獲得した K 人のキャラ (同票の場合は名前の辞書順) の関連商品が企画されることになる。僕の好きなキャラは全部で M 人いて、その中からできるだけ多くのキャラを上位 K 人に入れたいと思っている。
僕はまず、それぞれのキャラがどれだけの票を獲得するかを予測した(難しいことではない。あるキャラクターの人気度は、その登場時間の総和に比例すると仮定しただけだ)。この予測が正しいとして、より多くの僕の好きなキャラの関連商品が発売されるようにするためには、僕はこの L 票を誰にどれだけ投じればいいだろうか。
入力は複数のケースからなる。 各ケースは以下のフォーマットで与えられる。
N M K L name0 x0 . . . nameN-1 xN-1 fav0 . . . favM-1
N、M、K、Lの意味は問題文に記されているとおりである。
namei はキャラクターの名前、xi はi 番目のキャラクターの票の総数を表す。
favi はあなたがひいきしているキャラクターの名前を表す。これらの名前は必ず異なり、また必ずキャラクターの名前の入力の中に含まれる。
入力の終わりはN = 0 かつ M = 0 かつ K = 0 かつ L = 0からなる行によって与えられる
また各値は以下の条件を満たす
1 ≤ N ≤ 100,000
1 ≤ M ≤ N
1 ≤ K ≤ N
1 ≤ L ≤ 100,000,000
0 ≤ xi ≤ 100,000,000
nameiはアルファベットのみを含み、長さは10文字以下である。
テストケースの数は150を超えない。
また20,000 ≤ N となるケースの数は20を超えないことが保証されている。
ジャッジデータは大きいので、速い入力を使うことを推奨する。
M 人のキャラの中から最大で何人を上位K 人に入れることが出来るかを1行で出力せよ。
4 1 3 4 yskwcnt 16 akzakr 7 tsnukk 12 fnmyi 13 akzakr 4 1 3 5 akzakr 7 tsnukk 12 fnmyi 13 yskwcnt 16 akzakr 4 2 2 1 akzakr 4 tsnukk 6 yskwcnt 6 fnmyi 12 akzakr fnmyi 5 2 3 28 knmmdk 6 skrkyk 14 tmemm 14 akmhmr 15 mksyk 25 knmmdk skrkyk 5 2 3 11 tmemm 12 skrkyk 18 knmmdk 21 mksyk 23 akmhmr 42 skrkyk tmemm 14 5 10 38 iormns 19 hbkgnh 23 yyitktk 31 rtkakzk 36 mmftm 43 ykhhgwr 65 hrkamm 66 ktrotns 67 mktkkc 68 mkhsi 69 azsmur 73 tknsj 73 amftm 81 chyksrg 88 mkhsi hbkgnh mktkkc yyitktk tknsj 14 5 10 38 mktkkc 24 rtkakzk 25 ykhhgwr 25 hrkamm 27 amftm 37 iormns 38 tknsj 38 yyitktk 39 hbkgnh 53 mmftm 53 chyksrg 63 ktrotns 63 azsmur 65 mkhsi 76 mkhsi hbkgnh mktkkc yyitktk tknsj 0 0 0 0
0 1 1 2 1 4 5
The University of Aizu Programming Contest 2011 Summer
原案: Tomoya Sakai
問題文: Takashi Tayama