メモ

yukicoderでゆるふわgolf

yukicoder No.490 yukiソート

問題はこち
No.490 yukiソート - yukicoder


制約が小さいので、問題文の指示通りに実装すれば良い。
以下では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})の組に対し、それ以降にはa_kは登場しないので、a_{n-1}が登場する組を除く全てと順序を入れ替えることができるので
(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[i];
	}
	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