Cache Strategy

Time Limit : 2 sec, Memory Limit : 262144 KB

問題 H : キャッシュ戦略

今,G○○gle Code Jam の地区大会が始まろうとしている. 斜め右前の席に座っている男の ID は lyrically と言うらしい. 東京大学時代の記憶に,似たような ID の仲間が居た覚えがあるが,僕の仲間は一人残さず美少女だったはずだ.

僕の記憶の中の lyrically は,アルゴリズムの力や実装の力もさながら, 気合で問題に正解することにも定評があった. 例えば,計算量が多少悪いプログラムでも,上手な実装をすることで高速にし, 正解とするようなことも得意としていた.

プログラムを高速にする上で,非常に大切になってくるのが, キャッシュメモリとの親和性である.

問題

ブロック毎に読み込みのコストが異なるメモリを考える. 起こる全てのメモリアクセスがあらかじめ分かった状態での, フルアソシアティブのキャッシュメモリでの最善なキャッシュ戦略を求めたい. 以下,平易な言葉で説明する.

M 個の箱と,N 個のボールがある. ボールには 1 から N までの番号が付いており, 各ボール i には重さ wi が決まっている. また,長さ K の数列 a1a2, …, aK が与えられる. 各 aj1 ≤ aj ≤ N を満たす整数である.

はじめは全ての箱は空である. j = 1, 2, …, K の順に,以下を行いたい.

  • ボール aj が入っている箱があれば,何もしない.
    • この操作にかかるコストは 0 である.
  • ボール aj が入っている箱がなければ,いずれかの箱にボール aj を入れる.
    • ボールを箱に入れる際,もし既にその箱に入っているボールがあれば,そのボールは外に出す.
    • この操作にかかるコストは waj である.(コストは,入れる箱や取り出すボール等にはよらない.)

コストの和の最小値を計算するプログラムを作成せよ.

入力

入力の最初の行は 3 つの整数 MNK を含む.

続く N 行の i 行目には整数 wi が書かれている.

続く K 行の j 行目には整数 aj が書かれている.

出力

コストの和の最小値を出力せよ.

制約

  • 1 ≤ M ≤ 10
  • 1 ≤ N ≤ 104
  • 1 ≤ K ≤ 104
  • 1 ≤ wi ≤ 104
  • 1 ≤ aj ≤ N

部分点

この問題の判定には,20 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は以下を満たす.

  • 1 ≤ M ≤ 3
  • 1 ≤ N ≤ 10
  • 1 ≤ K ≤ 103

入出力例

入力例 1

入力例 1:

3 3 6
10
20
30
1
2
3
1
2
3

入力例 1 に対する出力例:

60

入力例 2

入力例 2:

2 3 6
10
20
30
1
2
3
1
2
3

入力例 2 に対する出力例:

80

Source: University of Tokyo Programming Contest 2011 , Tokyo, Japan, 2011-05-14
Problem Setter:  Takuya Akiba
http://www.utpc.jp/2011/