読者です 読者をやめる 読者になる 読者になる

AOJ 1234: GIGA Universe Cup

AOJ

←この人らもういいんじゃないかな…

ということで難易度表収録を願って解きました。

サッカーの順位表を日ごろから見ていると、ソート基準は問題文を読む必要がなくなるので、確率の式と入力の何文字目が数字なのか数えるくらいしかやることがないです。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[10][40];
int pt[10];
int ge[10];
int sh[10];
int hl[10];
double prob[10];
int val[10][10];
int to[10];

int main(){
	int T;
	scanf("%d",&T);
	for(int i=0;i<=8;i++){
		double ks=1;
		for(int j=0;j<i;j++){
			ks*=(8-j);
			ks/=(j+1);
		}
		for(int j=0;j<8-i;j++)ks*=3;
		for(int j=0;j<8;j++)ks/=4;
		prob[i]=ks;
	}
	while(T--){
		for(int i=0;i<5;i++)scanf("%s",str[i]);
		int num=0;
		for(int i=0;i<4;i++)if(str[i+1][0]=='*')num=i;
		for(int i=0;i<4;i++)for(int j=i+1;j<4;j++){
			if(str[i+1][6+j*5]=='_'){
				to[i]=j;
				to[j]=i;
				continue;
			}
			int l=str[i+1][6+j*5]-'0';
			int r=str[i+1][8+j*5]-'0';
			val[i][j]=l;
			val[j][i]=r;
		}
		double ret=0;
		for(int i=0;i<=8;i++)for(int j=0;j<=8;j++)for(int k=0;k<=8;k++)for(int l=0;l<=8;l++){
			double ks=prob[i]*prob[j]*prob[k]*prob[l];
			val[0][to[0]]=i;
			val[1][to[1]]=j;
			val[2][to[2]]=k;
			val[3][to[3]]=l;
			for(int x=0;x<4;x++)hl[x]=0;
			bool chg=false;
			int rem=4;
			int ue=0;
			do{
				chg=false;
				for(int x=0;x<4;x++)pt[x]=ge[x]=sh[x]=0;
				for(int x=0;x<4;x++)for(int y=x+1;y<4;y++){
					if(hl[x]||hl[y])continue;
					if(val[x][y]>val[y][x])pt[x]+=3;
					else if(val[x][y]<val[y][x])pt[y]+=3;
					else{pt[x]++;pt[y]++;}
					ge[x]+=val[x][y]-val[y][x];
					ge[y]+=val[y][x]-val[x][y];
					sh[x]+=val[x][y];
					sh[y]+=val[y][x];
				}
				for(int x=0;x<4;x++){
					if(hl[x])continue;
					if(x==num)continue;
					if(pt[x]>pt[num]){
						chg=true;ue++;rem--;
						hl[x]=1;continue;
					}
					if(pt[x]<pt[num]){
						chg=true;rem--;
						hl[x]=1;continue;
					}
					if(ge[x]>ge[num]){
						chg=true;ue++;rem--;
						hl[x]=1;continue;
					}
					if(ge[x]<ge[num]){
						chg=true;rem--;
						hl[x]=1;continue;
					}
					if(sh[x]>sh[num]){
						chg=true;ue++;rem--;
						hl[x]=1;continue;
					}
					if(sh[x]<sh[num]){
						chg=true;rem--;
						hl[x]=1;continue;
					}
					
				}
			}while(chg&&rem>1);
			if(ue>=2)continue;
			ret+=ks*min(1.0,(2.0-ue)/rem);
		}
		printf("%.7f\n",ret);
	}
}