yukicoder No.490 yukiソート

制約が小さいので、問題文の指示通りに実装すれば良い。
以下ではO(n^2)より早い解法を考える。

いくつか実験してみれば分かる通り、yukiソートをおこなうと「ほぼ」通常の昇順ソートになっていることがわかる。
そこで次のようなソートを考える

yukiソート改
1. i=1,2,…,2n-3 に対して、i の小さい順に 2. を行う
2. p+q=i (0≦p<q≦n−1) を満たす整数の組 (p,q) 全てに対して、ap>aq ならば ap と aq を交換する

オリジナルのyukiソートとの違いはi=2n-3の場合も手順2を行うところである。
このyukiソート改を行うと昇順にソートされる。

証明
nに関する帰納法による。n=2のとき明らか
一般に $i_j$ が相異なるなら( $a_{i_1},a_{i_2}$ )の比較/swapと( $a_{i_3},a_{i_4}$ )の比較/swapは順序を交換することができる
( $a_k,a_{n-1}$ )という形の組をyukiソート改において比較/swapをする際、それ以降には $a_k$ を含む組は登場しないので、 $a_{n-1}$ が登場する組を除く全ての組と比較/swapの順序を入れ替えることができる。よって
( $a_0,a_1$ ),( $a_0,a_2$ ),( $a_1,a_2$ )……,( $a_{n-2},a_{n-1}$ )
というもとの比較順序は
（ $a_{n-1}$ を含まない組たち）,( $a_0,a_{n-1}$ ),……,( $a_{n-2},a_{n-1}$ )
という順序に入れ替える事ができる。
帰納法の仮定より、 $a_{n-1}$ を含まない組たちに対する操作を行った時点で、 $a_0$ から $a_{n-2}$ までは昇順にソートされているので、残りの操作により数列全体が昇順にソートされる。
証明終わり

実際のyukiソートでは最後のswapが行われないので、上記証明によりyukiソートを行った結果が昇順ソートにならないための必要十分条件は「 $\{a_i\}$ の唯一の最大値が $a_{n-1}$ でない」となることがわかる
特にこれは、「 $a_{n-1}\neq \max a_i$ ならば、ソート後の数列の最後の2つを入れ替える」と同値であることがわかる。

#define swap(p,q)(p^=q^=p^=q)
a[3000],i,n,s;
c(int*p,int*q){return*p-*q;}
main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",a+i);
	}
	s=a[n-1];
	qsort(a,n,4,c);
	if(a[n-1]!=s)swap(a[n-1],a[n-2]);
	for(i=0;i<n;i++)printf("%d ",a[i]);
}

ソートを逆向きにしていい感じにする

a[3000],s,x;
c(int*p,int*q){x=*q-*p;}
main(i){
	for(;~scanf("%d",a-i);s=a[-i--]);
	for(qsort(a,-i,4,c);i++;printf("%d ",s-*a&&i>-2?a[i+1]:a[-i]));
}

141B

メモ

yukicoderでゆるふわgolf

yukicoder No.490 yukiソート