Official
E - ピアノ / Piano Editorial
by
E - ピアノ / Piano Editorial
by
kyopro_friends
次に弾く音が鍵盤のどの位置にあるかを毎回愚直に探す解法では TLE となります(C++のvectorに対するfind、pythonのlistに対するindexなどもこれに該当します)
「Xヘルツの音を出す鍵盤は左から何番目か」を表す連想配列を予め作成し、実際に曲を弾く過程をシミュレーションすることで \(O(M\log N)\) でこの問題を解くことができます。
writer解(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<int>a(n),b(m);
for(int i=0;i<n;i++)cin >> a[i];
for(int i=0;i<m;i++)cin >> b[i];
map<int,int>pos;
for(int i=0;i<n;i++)pos[a[i]]=i;
long long ans=0;
for(int i=1;i<m;i++)ans+=abs(pos[b[i]]-pos[b[i-1]]);
cout << ans << endl;
}
posted:
last update:
