yukicoder No.366 ロボットソート

for(i=0;i<n;i++)for(j=0;j+1<n;j++)if(x[j]>x[j+1])swap(x[j],x[j+1]);

とするところを

for(i=0;i<n;i++)for(j=0;j+k<n;j++)if(x[j]>x[j+k])swap(x[j],x[j+k]);

とすればよい
（あとで縮める都合上、普通のバブルソートより定数倍悪いのは許して）

int main(){
	int x[1010],s=0,i,j,n,k,f;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++)scanf("%d",x+i);
	for(i=0;i<n;i++)for(j=0;j+k<n;j++)if(x[j]>x[j+k]){
		x[j+k]^=x[j]^=x[j+k]^=x[j];
		s++;
	}
	//ソートできているかチェック
	f=1;
	for(i=1;i<n;i++)if(x[i-1]>x[i])f=0;
	printf("%d",f?s:-1);
	return 0;
}

・読み込みの改善
全部まとめて配列に読み込んで良さそう。nの値は不要なことに注意する
・判定の改善
判定とソートをまとめてやりたい。
上のようなソートは、与えられた数列を添字のmod kによりk個のグループに分けて各々バブルソートしていると考えることが出来る。
内側のループ1回ごとに、各グループの一番後ろの要素は正しく入れ替えが行われているので最大になっている。
よってk≧2のとき、ループ毎に後ろからk個が正しく並べられていくので、x[n-2-i]<x[n-1-i]か成立しているか確かめることで最終的にソートが上手くいっているかを調べることが出来ることがわかる。
k=1の時はもちろん必ずソートは上手くいっていて、かつこの条件はかならず成立している
iをカウントダウンにすれば条件式の添字が簡単になる

やりたいことはだいたいこんな感じ

x[1010],s,i,j;
main(){
	for(i=-1;~scanf("%d",x+i);i++);
	//この時点でiはnになっている
	for(;--i>1&&~s;){
		for(j=1;x[j+*x];j++)if(x[j]>x[j+*x]){x[j+*x]^=x[j]^=x[j+*x]^=x[j],s++;}
		if(x[i]<x[i-1])s=-1;
	}
	s=!printf("%d",s);
}

ということでiをmainの第一引数にし、正負を反転させることで次を得る

x[1010],s,j;
main(i){
	for(;~scanf("%d",x-i);i--);
	for(;~++i&&~s;x[-i]<x[~i]?s=-1:0)for(j=1;x[j+*x];j++)x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],s++:0;
	s=!printf("%d",s);
}

167B

2016/10/15追記
jの初期化をぐっと睨むことで2B短縮

x[1010],s,j;
main(i){
	for(;~scanf("%d",x-i);i--);
	for(;~++i&&~s;j=x[-i]<x[~i]?s=-1:0)for(;x[++j+*x];)x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],s++:0;
	s=!printf("%d",s);
}

ループの終了条件をちょっと書き換えてみる

for(;~++i&&~s;j=x[-i]<x[~i]?s=-1:0)for(;x[++j+*x];)x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],s++:0;
for(;++i<-1;j=x[-i]<x[~i]?i=s=-1:0)for(;x[++j+*x];)x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],s++:0;

これにより、iがずれても多少融通がきくようになったので、ループ圧縮してみる

for(;++i<-1;j=x[-i]<x[~i]?i=s=-1:0)for(;x[++j+*x];)x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],s++:0;
for(;!x[++j+*x]?j=x[~i]<x[~-~i]?i=s=-1:0,++i<-2:x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],++s:1;);

for(;~scanf("%d",x-i);i--);for(;!x[++j+*x]?j=x[~i]<x[~-~i]?i=s=-1:0,++i<-2:x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],++s:1;);
for(;~scanf("%d",x-i)?i--,1:!x[++j+*x]?j=x[~i]<x[~-~i]?i=s=-1:0,++i<-2:x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],++s:1;);

5B短縮
ということで全体では7B短縮の160B

x[1010],s,j;
main(i){
	for(;~scanf("%d",x-i)?i--,1:!x[++j+*x]?j=x[~i]<x[~-~i]?i=s=-1:0,++i<-2:x[j]>x[j+*x]?x[j+*x]^=x[j]^=x[j+*x]^=x[j],++s:1;);
	s=!printf("%d",s);
}

メモ

yukicoderでゆるふわgolf

yukicoder No.366 ロボットソート