というわけで調べてみました

PKU2371 の qsort として通ったのは以下のような文字列です。

"YXZ\x83\xec\f\213\0+\x2\303"

これは以下のようなアセンブリ。

     pop %ecx
     pop %eax
     pop %edx
     sub $12, %esp
     mov (%eax),%eax
     sub (%edx),%eax
     ret

これだと全然長すぎる。nanagyouさんの

q(int*a){a=*a-*1[&a];}

というヤツより長くなっちゃいます。以下のコードだと、

     pop %ecx
     pop %eax
     pop %edx
     push %edx
     push %eax
     push %ecx
     mov (%eax),%eax
     sub (%edx),%eax
     ret

"YXZRPQ\213\0+\x2\303" と、命令長は同じなのですが、 ASCIIの文字が増えるので短くなるのですが、処理が遅くなるので TLE が出てしまいます。アホかと。

でもって、 ASCII しか通らないという制限は前からホントかなーと思ってたのですが、しゃーないから適当に自分で URI エンコードして wget でサブミットしてみるも通らず。

まぁ一個も成果無いのはシャクなので、昔解いた問題から適当に適用可能ぽいものを探してきました。 PKU1007 。 4B 縮みました。ていうか PKU1007 って私が記録持ってたんですね。あんま短そうに見えないのですが。下記コードの \0 と \x2 は自分で ASCII コード打ち込んでください。

char*p;
s['~~'];
v[110];
n=110;
k,q;
main(i,o){
    for(;o=gets(s+n*k);v[k]=i*n+k++)
        for(strcpy(s,o),i=0;o--;)
            for(p=s;q=p[1];p++)
                *p>q?p[1]=*p,*p=q,o=++i:0;
    for(qsort(v+1,k,4,"YZXPRQ\213\0+\x2\303");--k;)
        puts(s+v[k]%n*n);
}

まとめると、なるべく ASCII で、命令長の短いアセンブラコードを探さないといけない、あと TLE に気をつけて、って感じでしょうか。あと qsort 以外に適用するのは無理かなーと思います。

私が考えたアセンブリコードが最短かどうかも知りませんし、 8bit レジスタの命令とかキチンと見てませんし。スタックからの変数の取り方がこれで正しいかもあやしいです。テストケースが甘ければ汎用レジスタの同じ個所にかならず第一引数が入ってる…とかもあるかもしれません(PKU2371に関してCygwinで調べた限りはダメ)。

まぁ、 C ゴルフで今までに一番感動したのは qsort 回りのハック群なので、その方法がまた一つ増えたのは面白いことだなぁと思います。

でも体調悪いのに PKU のために何故かグラボ抜いたりしてるのはどうなんだというような。誰かもうちょい深く考えるといいんじゃないかと思います。 kurimura さんとか。名指しかよ。