Codeforces Round 119(Div.2)

結果

oo--- (+0/-0) 1290pts 357th
1536->1501
敗戦…勝ちがTopcoderに、負けがCodeforcesに集中している気がする。

A

全探索やるだけ、とかいって4000^3投げる->TLE
ですよねーといいつつ4000^2投げる->WA
n-(a*i+b*j)>0のチェックを入れてなかった…

• >pretest passed.

B

菱形という英単語を覚えた。全探索やるだけ。

C

解けなかった、解けるべきだった。
元の数列をA、目的の数列をBとすると
あるk番目までは整列されているようなkを探す。
(a[0]...a[k]までの任意のx,yについて、a[i]=x,a[j]=yとしたときにi

#include <iostream>

int a[200001], pos[200001];

using namespace std;

int main(){
    int n,t;
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        cin >> t;
        pos[t] = i;
    }

    int k = 1;
    while(1){
        if(pos[a[k]] <= pos[a[k-1]]) break;
        k++;
    }
    cout << n - k << endl;
}