yukicoder No.43 野球の試合

自分のチームの未消化試合は全勝すれば良さそうに見えるが、
「1位が2チームいてもその次は2位」というルールのせいで
「あえて負けることで、他チーム同士が同順位となり順位が上がる」という現象が起こる
具体的には次のような場合

#xxxx-
o#xoxo
oo#xox
oxo#ox
ooxx#o
-xoox#

そういうわけなので
全探索するしかなさそう
未消化の試合があればその結果を決めて再帰
すべての試合が終わっていれば順位を返す
という関数をつくりDFSで最高順位を求める

char a[7][7];

int q(int*a,int*b){return*b-*a;}

int x(char a[][7],int t){
//第一引数は現在までの試合表
//第二引数は残り試合数
	int b[7]={},f=1,i=0,j;
	char c[7][7];
	if(t){
	//未消化の試合があるなら
		memcpy(c,a,49);
		//試合表をコピーして
		for(;f&&++i;)for(j=0;f&&++j<7;f-=a[i][j]=='-');
		//未消化の試合を求めて
		c[i][j]='o';c[j+1][i-1]='x';f=x(c,t-1);
		c[i][j]='x';c[j+1][i-1]='o';j=x(c,t-1);
		//その試合結果を決めて再帰
		return f<j?f:j;
		//順位の良い方を返す
	}else{
	//全ての試合が終わったなら
		for(;i++<7;)for(j=0;j<7;b[i]+=a[i][j++]=='o');
		//各チームの勝利数を数えて
		qsort(b+2,5,4,q);
		//自分のチームを除いてソート（上位の重複を除くため）
		for(i=1;i++<6;f+=b[i]>b[1]&&b[i-1]!=b[i]);
		//自分より上位のチームの数を足す
		return f;
	}
}

int main(){
	int i,j,t;
	for(i=0;i<7;i++){
		gets(a[i]);
		//読み込みながら
		for(j=0;j<7;t+=a[i][j++]=='-');
		//未消化試合数を数える
	}
	printf("%d",x(a,t/2));
	return 0;
}

わざわざ2次元配列にしなくても普通の配列で渡せばいいよね
それから順位のカウントも、わざわざソートしなくても「既出でなくかつ自分より上位」をカウントすればいい
更に残り試合数を引数にしなくても、未消化試合を探して、見つかったかどうかで分岐すればいい

i;
char a[49];
x(char*a){
	int b[6]={},f=1,i=42,j=0;
	char c[42];
	for(;--i;b[i/7]+=a[i]==111);
	//各チームの勝数と
	for(;++i<6;j|=1<<b[i])f+=~j>>b[i]&b[i]>*b;
	//暫定順位を先に求める
	for(;++i<42&&a[i]!=45;);
	//未消化試合があるかどうか探して（※）
	return i-42?memcpy(c,a,42),c[i]='o',c[j=i%7*7+i/7]='x',f=x(c),c[i]+=9,c[j]-=9,j=x(c),f<j?f:j:f;
	//あれば試合表をコピーして再帰、なければ順位を返す
}
main(){
	for(;gets(a+i++*7););
	i=!printf("%d",x(a+7));
}

※の部分でiが0～6の時が調べられていないが、これは1チーム目の部分なので
この部分で見落としがあっても、相手チーム側でかならず見つけることができる
さらに言えば、関数にポインタを渡した時点でchar*と思わせればいいわけで、読み込みはint配列でもいい
更に、試合表を実際に'o'と'x'で埋めているが、探し方を工夫することで、ここも短縮できる

i;a[14];
x(char*a){
	int b[6]={},f=1,i=48,j=0;
	char c[48];
	for(;--i;b[i/8]+=a[i]&4);
	//'o'と'x'の分離にはこれで十分
	//'-'が残っていてるならこの値は使わないのでそこは気にしなくて良い
	for(;++i<6;j|=1<<b[i])f+=~j>>b[i]&b[i]>*b;
	//順位を求める
	for(;++i<48&&a[i]-45;);
	//未消化試合を探す
	return i-48?memcpy(c,a,48),c[i]=4,c[j=i%8*8+i/8]=0,f=x(c),c[i]=0,c[j]=4,j=x(c),f<j?f:j:f;
}
main(){
	for(;gets(a+i++*2););
	i=!printf("%d",x(a+2));
}

頑張ってループ圧縮

i;a[14];
x(char*a){
	int b[6]={},f=1,i=48,j=0;
	char c[48];
	for(;--i&&a[i]-45;b[i/8]+=a[i]&4);
	//処理順序を入れ替えた（まとめた）
	//a[i]-45が偽になるとしたらi>=8のときであることに注意
	for(;i<6;j|=1<<b[i++])f+=~j>>b[i]&b[i]>*b;
	//もしa[i]-45が偽で前のループを抜けていた時のためにiのincの場所を変えた
	return i>6?memcpy(c,a,48),c[i]=4,c[j=i%8*8+i/8]=0,f=x(c),c[i]=0,c[j]=4,j=x(c),f<j?f:j:f;
	//条件式が1文字削減された
}
main(){
	for(;gets(a+i++*2););
	i=!printf("%d",x(a+2));
}

271B

16/04/22追記

i;a[14];
x(int*a){
	int b[6]={},f=1,i=48,j=0;
	char c[48];
	for(memcpy(c,a,48);--i&&c[i]-45;b[i/8]+=c[i]&4);
	//先にmemcpyすることで引数の型をごまかせる。あわせて2B短縮
	for(;i<6;j|=1<<b[i++])f+=~j>>b[i]&b[i]>*b;
	return i>6?c[i]=4,c[j=i%8*8+i/8]=0,f=x(c),c[i]=0,c[j]=4,j=x(c),f<j?f:j:f;
}
main(){
	for(;gets(a+i++*2););
	i=!printf("%d",x(a+2));
}

269B

17/01/22追記

i;a[14];
x(int*a){
	int b[6]={},f=1,i=48,j=0;
	char c[48];
	for(bcopy(a,c,48);--i&&c[i]-45;b[i/8]+=c[i]&4);
	//memcpyをbcopyに変更
	for(;i<6;j|=1<<b[i++])f+=~j>>b[i]&b[i]>*b;
	return i>6?c[i]=4,c[j=i%8*8+i/8]=0,f=x(c),c[i]=0,c[j]=4,j=x(c),f<j?f:j:f;
}
main(){
	for(;gets(a+i++*2););
	i=!printf("%d",x(a+2));
}

268B

17/06/17追記

a[14];
x(int*a){
	int b[6]={},f=1,i=48,j=0;
	char c[48];
	for(bcopy(a,c,48);--i&&c[i]-45;b[i/8]+=c[i]&4);
	//memcpyをbcopyに変更
	for(;i<6;j|=1<<b[i++])f+=~j>>b[i]&b[i]>*b;
	return i>6?c[i]=4,c[j=i%8*8+i/8]=0,f=x(c),c[i]=0,c[j]=4,j=x(c),f<j?f:j:f;
}
main(i){
	for(;gets(a-i--*2););
//	*a=!printf("%d",x(a));
	//iをmain引数にすることで3-1=2B短縮
	printf("%d",x(a));
	//さらにC90→Cで返り値を気にする必要がなくなったので4B短縮
}

262B

メモ

yukicoderでゆるふわgolf

yukicoder No.43 野球の試合