TLE2011

Program CodeGolf C

TLEなるプログラミングコンテストに@osa_k(id:osa_k)と参加しました。
なにやら相方の記事で振られているいるようなので、参戦記的な物を。

結果は8位。
自分が主にやっていた二つともmain再帰を見逃していたとか、色々と後悔の残る所はあったけれど、7位までは65点差があるので厳しかったでしょう、はい。
HASHとARRNG以外はほぼノータッチな上に、この二つも相方に色々手伝ってもらったというていたらくっぷり。
そもそも問題が読めないという時点で実にアレであった。

以下、相方から解説投げられたHASHとARRNGについて軽く。

HASH

最初にやったやつ。
入力全部を1行に繋げ、前半後半を分けて、それぞれを与えられているHASH関数を使って同じになればyes、違えばnoを出力する問題。
但し、そのコード自身もyesな物でなければならない。

HASH関数自体を間違えて書いていたのと、「コード自身を突っ込むとyesでなければいけない」を見逃していて、最初しばらくWA。
それを相方に指摘され、

char s[10000],t[10000];i,l,h[2];main(){while(gets(t))strcat(s,t);while(i++<(l=strlen(s)))h[i&1]=((h[i&1]<<8)+s[l/((i&1)+1)-(i+1)/2])%1009;puts(h[0]-h[1]||l&1?"no":"yes");}//char s[10000],t[10000];i,l,h[2];main(){while(gets(t))strcat(s,t);while(i++<(l=strlen(s)))h[i&1]=((h[i&1]<<8)+s[l/((i&1)+1)-(i+1)/2])%1009;puts(h[0]-h[1]||l&1?"no":"yes");}//

こんな感じのでACになった。
ほぼ愚直に計算して、HASH合わせは後ろにまんま同じコード入れてるだけなので、スコアは酷い。
その後、HASHは高々1009通りしか無いので変数名変えれば行ける(26C(変数の個数)パターンくらい？)んじゃね？と思いつき、rubyで適当に合わせる物を

loop{
	v=("a".."z").to_a.sample(5)
	source="ソースの変数名の所を#{v[変数の順番]}にしたの"
	if solvflg(source)
		print source
		break
	end
}

こんな感じにを書いて適当にHASH合わせ。これで長さが半分になった。
更に相方が入力部を詰めてくれたりとかして、ほぼ完成形に近づき、
後はHASH関数そのままだと後ろから順番に計算するので、indexが長くなってしまうという事で、
「256の1009を法とした逆元である942」を使って、前から順番に計算出来るようにして微妙に縮めたり、
「+942*a == -(1009-942)*a = -67*a」
を用いて縮めたりして、結局出来たコードは

char n[9999];z,v;main(e){for(;n[e++]||gets(n+--e)||z++<e/2&&~(v=(n[z]-n[e/2+z]-v*67)%1009););puts(!v&e%2?"yes":"no");}

上位陣の解を見てみると、入力に「長さが奇数」が無いとか、実は<<8のままの方が短かったっぽいとか、main再帰使うべきだったとか、反省点は色々ある。
久々に逆元とか使ったし、個人的に面白い問題ではあった。
200ptsまで後6byteくらいだったけど、まぁ無理ですよねー･･･

ARRNG

与えられたn個の数をソートし、並べ替えて作ったn個の数列をまたソートして配置するような問題。
但し、for、while等のループを使ってはいけないのと、半角スペース・セミコロンはコストが大きい。

そもそも並べ替えの規則を間違えていて、良い感じの解法を思い付いたものの、変なコーナーケースとかを想定してしまってやめてしまった。
フォーラムを見て規則がちゃんとわかったものの、しばらくコーナーケースを考えたままだったので、

t,n,i,j,a[999],b[999];c[999][999];
f(){i<n&&(b[i]=!scanf("%d",a+i++))^f();}
int(*z)(int*a,int*b)="YXZQQQ\x8b\x00+\x02\xc3";
g(int*a,int*b){
	for(i=0;i<n;++i){
		if(z(a+i,b+i))return z(a+i,b+i);
	}
	return 0;
}
main(){
	scanf("%d",&t);
	for(;t--;){
		scanf("%d",&n);
		i=0;f();
		qsort(a,n,4,z);
		for(i=1;i<=n;i){
			j=-1;
			while(b[++j]);
			while(j<n){
				b[j]=i++;
				while(b[++j]);
				while(b[++j]);
			}
		}
		for(i=0;i<n;++i)for(j=0;j<n;++j)c[i][j]=a[(b[i]+b[j]-2)%n];
		qsort(c,n,3996,g);
		for(i=0;i<n;++i){
			for(j=0;j<n;++j){
				printf("%d ",c[b[i]-1][j]);
			}puts("");
		}
	}
}

こんな感じのを再帰になおし、"文;"を"if(文){}"としてセミコロンを減らした、愚直な感じのコードであった。
ちなみに、zに突っ込んでる文字列はAnarchy Golfにあったソートの問題のagliasさんの解からパクって来たもの。
しばらくこのまま頑張っていたが、想定していた2回目の並び替えでのコーナーケースが無い事が解り、
「0からn-1までを完全に配列したB[i][j]を用意した後、入力をソートしたA[i]を用意し、(i,j)の出力をA[ B[i][j] ]とすればいい」
として、B[i][j]をどう用意するかという問題になり、最終的に相方と相談しつつ数学的に順番を解く事に。
「n人のトーナメントで、常に左側の人が負けた時の、負け落ちる順番」的な物に出来そうだと気づき、色々と変形してみたが、
TOPのshinhさんの解を見るとどうやらその手法で、n/2人のトーナメントに帰着させた感じの模様。
自分たちは別の式に行き着き、最終的には

t,n,i,a[999],c,e,x;
g(q){if(scanf("%d",q)){}}
f(){if(i<n&&f(g(a+i++))){}}
k(){if(l(e=0),c+=n-(n>>e)+x/2){}}
l(){if(x&1||l(x/=2,++e)){}}
o(){if(i<n*n&&o(c=0,k(x=i/n+1)^k(x=i%n+1)^printf("%d\x20",a[c%n])^(++i%n?:puts("")))){}}
m(){if(t--&&g(&n)^f(i=0)^qsort(a,n,4,"YXZQQQ\x8b\x00+\x02\xc3")^o(i=0)^m(puts(""))){}}
main(){if(m(g(&t))){}}

というコードに。
実にぐろい。見てて気持ち悪くなってくる。
TOP陣に比べ、main再帰を使っていなかったり、関数の数がかなり多いのが長くなった要因の一つだと思う。