roiti46's blog

主に競プロ問題の解説を載せてます

Codeforces #293 Div.2 C: Anya and Smartphone

人によってはAより簡単に思えるかも。

問題はこちら

問題

スマートフォンにn個のアプリが入っている。1画面にはk個のアプリが表示でき、あるアプリを起動するときに必要な操作数は、アプリのタップと画面のスワイプを合わせた数とする。起動されたアプリは1つ前に移動する。アプリの並びと起動するアプリのリストを与えるので、必要な操作回数を答えよ。

解法

素直に問題文通りにやっていけばいい。 ただし、毎回起動するアプリがどこにあるのかを探索していては間に合わないので、アプリの並びの列と、i番目のアプリがどこにあるかの列を持って、アプリの起動があるごとに更新していく。 個人的にAより簡単に思える。

n,m,k = map(int,raw_input().split())
a = map(int,raw_input().split())
b = map(int,raw_input().split())

where = [0]*n
for i in xrange(n): where[a[i]-1] = i
ans = 0
for bi in b:
    pos = where[bi-1]
    ans += 1 + pos/k
    if pos > 0:
        a[pos],a[pos-1] = a[pos-1],a[pos]
        where[a[pos]-1]   += 1
        where[a[pos-1]-1] -= 1

print ans