☆操作(AGC024B - Backfront)

atcoder.jp

師匠の問題で操作するゲーム系のやつ、前も見た。確か後ろの状態から戻ってく感じだった…
ここでも使えそう…と思ってその方針で長いこと考えたけど使えなかった、もっと簡単だった

解法

与えられた数列の部分数列をとって、それが連続（）であり単調増加であるような大きさnの数列である時、その部分は動かさないで間の数字を動かすだけでソートできる。
間の数字については、x_1より小さいものは大きい順にx_1より前に、x_nより大きいものは小さい順に後ろに動かせば良い。（部分数列を「核」にするイメージ）
明らかにこれが一番早い（なんでかはあんまり明確に示せない…）

実装

上の方法でやった時の手数は、N-部分数列の大きさになる。つまり部分数列の大きさを調べたい。
与えられた数列における1,2,3...の場所を記した番号A[1],A[2]...をこの順に見ていって、それがA[i+1]>A[i]となっているところの最大の長さを取れば良い。

なんか最近精進を長いことサボっていたからか500点が閃かないしレートが劇冷えする。辛い。

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back

int N;
int P[200004];
int A[200004];
signed main(){
    scanf("%lld",&N);
    int ans=N;
    rep(i,N){
        scanf("%lld",&P[i]);
        A[P[i]]=i+1;//A[i]はi番目にある
    }
    int sub=0;
    int subnow=1;
    rep(i,N){
        if(i>0&&A[i+1]>A[i]){
            subnow++;
            if(i==N-1)sub=max(subnow,sub);
        }else{
            sub=max(subnow,sub);subnow=1;
        }
    }
    printf("%lld",ans-sub);
}