問題はこちら
No.43 野球の試合 - yukicoder
自分のチームの未消化試合は全勝すれば良さそうに見えるが、
「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