裏紙

ほぼ競プロ、たまに日記

CF 606C - Sorting Railway Cars

問題

http://codeforces.com/contest/606/problem/C

1~nまでの数字が1個ずつランダムに並べられている。これを昇順にソートしたい。1回の操作で、ある要素を先頭、または最後尾に移動させることが出来る。ソートするまでに必要な操作の最小回数は何回か。

イデア

時間内で考えついたのは、「先頭の数より小さいものを前に出してから、最高尾の数より大きいものを後ろにだす」または「最高尾の数より大きいものを後ろにだしてから先頭の数より小さいものを前に出す」の方法の小さい方が答えになると思ってた、pretestは通ったが他人に落とされた...(昨日はそのため2完、コンテスト時間内ではBよりもCを通してる人が多くて、マジかっておもってたけど結局終了後のSystem test後でCが大量死してたからBの方が通ってる人は結局多かった。)

ここからはeditorialとほぼ同じ。 まず、操作する数字を取り除いて残る数列を考える。すると、それはa,a+1,a+2,...,bと1刻みの増加数列になっている(つまりソートの必要がない)。 新たに配列posを用意する。その数字が数列内のどこにあらわれているのかを記録する。(pos[p[i]] = i) このposの部分列を考えた時に、pos[a],pos[a+1],...pos[b]が単調増加なら、a~bの数字を動かす必要がなく、逆にそれ以外の数字をaより小さいのを前に、bより大きい物を後ろに動かす操作をすればよいということになる。つまり、posが増加している部分で最長のものをもとめれば、それをnから引いたものが答えになる。

こう言われるとシンプルな感じがするんだけどなあ...確かにただ貪欲なだけではダメですね...

追記

今回は記事をMarkdownを使って書いてみてます。

実装(C++)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <iterator>
using namespace std;

typedef long long ll;
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)

int main(int argc, char const *argv[]) {
  long n;
  cin >> n;
  vector<long> p(n);
  vector<long> pos(n+1);
  for(long i=0; i<n; ++i){
    scanf(" %ld", &p[i]);
    pos[p[i]] = i;
  }

  //しゃくとり法
  long st=0;
  long val=-1;
  long ans=1;
  for(long i=1; i<=n; ++i){
    if(val<pos[i]){ //のばせる
      val = pos[i];
    }
    else{ //1個手前までの長さをチェック
      ans = max(ans, i-st-1);
      st=i-1;
      val=pos[i];
    }
    //cout << "st=" << st  << " , ans = " << ans <<endl;
  }
  ans = max(ans, n-st);

  cout << n-ans <<endl;
  return 0;
}