2038 Team Rankings

問題概要

5チームのランキングがいくつか与えられる。
これらに対してmedian rankingを次のように定める。

median rankingと、それぞれのランキングについて任意の二つのチームの上下関係が逆転しているたびに値に1を足す。
この値が最小になるようなランキングがmedian rankingである。

与えられたランキングに対してmedian rankingを求めよ。

解法

チーム数は5,ランキングの数は100以下と少ないので全探索すればよい。

ソースコード

int n,tmp[5],ans[5];
int in[100][5]; char s[9];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)
		{
			scanf("%s",s);
			rep(j,5)in[i][s[j]-'A']=j;
		}
		int mn=inf;
		rep(i,5)tmp[i]=i;
		do
		{
			int cnt=0;
			rep(i,n)rep(j,5)rep(k,j)
			if((tmp[j]<tmp[k])!=(in[i][j]<in[i][k]))cnt++;
			if(mn>cnt)
			{
				mn=cnt; rep(i,5)ans[i]=tmp[i];
			}
		}while(next_permutation(tmp,tmp+5));
		
		rep(i,5)s[ans[i]]='A'+i;
		printf("%s is the median ranking with value %d.\n",s,mn);
	}
	return 0;
}