TLE2011

2/11から2/14にかけて、TLEという変則プログラミングコンテストに[twitter:@Mi_Sawa]と参加してました。
どういうコンテストかは[twitter:@kinaba]さんのtweetが端的に表しているので引用すると

という感じのコンテストです。
結果は総合8位。二人で出たんならもっと上いけるだろーという感じもするけど、とりあえず一桁に入れたので良しとします。
以下コード解説みたいなもの。ただし自分はHASHとARRANGはあんまり手を触れていないし理解してないので、[twitter:@Mi_Sawa](id:basuku)が解説してくれるはず！

追記

解説してくれました。

COUNTI

ソースコードのn文字目にある文字が、コード全体で何回出現するかを数える。
最初に解いた。たしかPOSTできるようになるまでの3時間をいっぱいに使って、

char*s="char*s=qq,*p;main(i,j){for(gets(j);~scanf(q%dq,&i,j=0);printf(q%dq,i<161&&s[i]-113?j*2:8)&&puts(qq)){i%=322;i-=(i>169?161:i>7?8:0);for(p=s;*p;*p++==s[i]&&++j);}}",*p;
main(i,j){
    for(gets(j);~scanf("%d",&i,j=0);printf("%d",i<161&&s[i]-113?j*2:8)&&puts("")){
        i%=322;i-=(i>169?161:i>7?8:0);for(p=s;*p;*p++==s[i]&&++j);
    }
}

こんなのを書いた。sに"をqでエンコードしたソースを持たせ、nがsの中身を指しているときは適宜indexをずらすことで対処しつつカウントしていく。
当然ながらあまりスコア出ず、しばらく悩んでいわゆる自明解

main(i){for(scanf("%dmmmaann{{{ffooorrrssccc%%%ddd,,,&&&;--pppuuuttt444}}}",&i);i--;puts("4"));}

を思いつく。自分には全然自明でなかった上、途中で点数計算の式が変わったらしくこれは役立たずで終わる……。
そのあと相方がQuineを使ったODDEVENを書いたので、ソレダ！と気づいて

main(i,j){
    char*s="main(i,j){char*s=%c%s%1$c,t[999];sprintf(t,s,34,s);for(gets(j);~scanf(%1$c%%d%1$c,&i);){for(s=j=0;j<304;)t[j++]-t[i%304]||++s;printf(%1$c%%d%1$c,s);puts(%1$c%1$c);}}",t[999];
    sprintf(t,s,34,s);
    for(gets(j);~scanf("%d",&i);){
        for(s=j=0;j<304;)t[j++]-t[i%304]||++s;printf("%d",s);puts("");
    }
}

よくあるQuineを使った解。最初にこれ思いつくべきだった。
そして13日にWikipediaのQuineを見ててプリプロセッサ解を思いつく。最終的には

#define B(x,y)x"B("#x","#y")"y
B(char*s="#define B(x,y)x\"B(\"#x\",\"#y\")\"y\n",;main(i,j,k){for(gets(j);~scanf("%d",&i);printf("%d\n",k))for(k=j=0;s[j];)k+=s[j++]==s[i%177];})

こうなった。他の人の解を見ると、この方法だとこれが限界っぽい。上位陣はsprintfのQuineとプリプロセッサを組み合わせてて、なるほどという感じ。

ODDEVEN

nを読んで、偶数ならソースコードの偶数文字目、奇数なら奇数文字目だけを出力する。
これも基本方針はCOUNTIと一緒で、基本的なアルゴリズムをゴルフしてしまえばあとはQuineの生成法の違いだけになるので、COUNTIと一緒に伸びてった。

#define B(x,y)x"B("#x","#y")"y
B(char*s="#define B(x,y)x\"B(\"#x\",\"#y\")\"y\n",;main(i){while(~scanf("%d",&i))for(i&=1;s[i];i+=2)putchar(s[i]);})

HEART

350*252のでかいアスキーアートが与えられて、だいたいそれっぽい出力を生成するという問題。
ソースコード1byteのペナルティが出力AA3byte分の不一致と同じペナルティなので、適当に合わせればいいんだなーと理解。これが間違いだった。

main(i,j,k){
    for(k=86,i=0;i<251;puts(""),++i,k+=i<30?-1:i<60?-i%2:i<100?0:i<140?!!(i%3):i<230?i%2:2)
        for(j=0;++j<351;)
            putchar(j<k||j>350-k?32:i<70?(130<j&&j<190)?43:58:i<100?43:i<149?(j<130-i+100?43:j<370-i?42:35):i<214?(j<420-i?35:64):i<239?64:42);
} 

最終形はこんなの。かなりアバウトに雰囲気合わせした図形を吐くシロモノ。元AA。出力。画像を見ると明らかに違うゲームをしていたことが分かりますね。

LETTER

アルファベット26文字のAAが与えられているので、入力から文字を判定する問題。
ナイーブにアルファベットを圧縮して比較。入力が横13x縦8なので、効率よくするために13行全部読んでから縦方向にbyte変換し、あらかじめ用意したバイトデータと比較。
これだけじゃ縮まないなー、と思いながらデータを眺めてると、0が妙に連続することに気づいたので0にだけRLEを掛けることで30byteくらい縮めた。

char*r="圧縮バイト列",p[999],b[8][20],k;
main(i,j,f,n,m){
    for(j=i=-1;++i<255;)r[i]?p[++j]=r[i]:(j+=r[++i]);
    for(scanf("%d",&n);gets(b),n--;){
        for(i=0;i<8;gets(b+i++));
        for(f=1,j=0;j<26*f;++j)
            for(f=i=0;i<13*!f;f=p[i++*26+j]!=k)
                for(m=0;m<8;)
                    k=(b[m++][i]>48)|k<<1;printf("%c\n",j+f<27?j+64:63);
    }
}

これでも30ちょっとくらいしか行かなくて疑問だったんだけど、蓋を開けてみれば上位陣はみんなHash化してた……。言われてみれば確かにHashが最適解だよなぁ。これを思いつかなかったのは反省すべき。

KD

これも方針がよく分からなかったのを、Updateだけ記録しておいてQueryごとに毎回舐めればいいことに相方が気づいたのでさくっと実装。最初の数回は普通に通ったけど、コードを縮めていくとだんだんTLEが発生するように……。どうやらかなりギリギリのラインらしく、命令のちょっとした違いが命取りになっているらしい。最後の方では同じソースを投げてもTLEだったりACだったりしてかなり不安定だった。

c[9999][9],v[18],p,T,K,Q,s,f;
main(i,j){
    for(scanf("%d",&T);T--;p=0)
        for(scanf("%d%*d%d",&K,&Q);Q--;){
            scanf("%d",&i);
            if(s=--i){
                for(;i++<K;)scanf("%d",c[p]+i);++p;
            }else{
                for(;i<K*2;)scanf("%d",v+i++);
                for(i=-1;++i<p;s+=f?0:c[i][K])
                    for(j=-1;++j<K&&!(f=c[i][j]<v[j]||c[i][j]>v[K+j]););
                printf("%d\n",s);
            }
        }
}

これがまぐれで通ったコード……のはず。一度通したあともう一度投げたらTLEした。