kmjp's blog

競技プログラミング参加記です

TopCoder SRM 673 Div2 Medium BearSlowlySorts

Div1 Mediumが解けたのにこっちは1ミスした。
https://community.topcoder.com/stat?c=problem_statement&pm=14083

問題

N要素の異なる整数からなる数列が与えられる。
1回の処理で連続した(N-1)個の整数を任意に並べ替えられるとき、全体を昇順に並べるのにかかる最小処理回数を求めよ。

解法

まず最小値と最大値の位置だけ求めておく。
あとは丁寧に場合分けしよう。

  • 最小値が先頭にある場合、残りは(N-1)要素なので1回処理すれば並べ替えられる。
    • よって、全体が最初から昇順なら0回、そうでなければ1回
  • 最小値が先頭でも末尾でもない場合、まず1回並べ替えて最小値を先頭に持ってくる。最大値が末尾にあれば、その1回で先頭(N-1)要素を昇順にして終わり。そうでなければもう1回処理する。
  • 最小値が末尾にある場合、それを先頭に持ってくるのに最低2回かかる。また最大値が先頭にある場合、最初の2回でこの最大値を末尾に持って行けないのでもう1回処理する。
class BearSlowlySorts {
	public:
	int minMoves(vector <int> w) {
		int N=w.size();
		int ma=0,mi=0,i;
		
		FOR(i,N) {
			if(w[ma]<w[i]) ma=i;
			if(w[mi]>w[i]) mi=i;
		}
		
		if(mi==0) {
			for(i=1;i<N-1;i++) if(w[i]>w[i+1]) return 1;
			return 0;
		}
		else if(mi<N-1) return 1+(ma!=N-1);
		else return 2+(ma==0);
	}
}

まとめ

丁寧に場合分けしないと見落とす。
案の定正答率はちょっと低目。