AOJ 2015 リズムマシーン

問題概要

N個のリズムパターンが与えられたとき、それをまとめたリズムパターンを出力せよ。
答えが2048文字以下にならない場合"Too complex."を出力せよ。

リズムパターンは16進数の2桁がm組並んできたものである。
i番目のリズムは1小節のi/mのタイミングで演奏される。
また、16進数が表すのは音で、j番目のビットがonであることは、jの高さの音が鳴っていることを意味する。

N≦8であり、それぞれのリズムパターンの文字数は2048を超えない。
また、入力のリズムパターンにおいて、各パターンのonであるビットの数は高々1つであり、同じタイミングで同じ音が複数個鳴ることはないと仮定してよい。

解法

各パターンの長さの最小公倍数が答えのパターンの長さである。
また、同一リズムを演奏するパターンには最も短いものがある

例
10002000は
1020と同一である

ため、各パターンに約分のような操作をあらかじめ施す必要がある。
（というかその部分がコードの大部分）

ソースコード

int n;
int rythm[8][1024],len[8];

int toi(char c)
{
	if(isdigit(c))return c-'0';
	return c-'A'+10;
}
char toa(int a)
{
	if(a<10)return '0'+a;
	return 'A'+a-10;
}
int minimize(int *r,int l)
{
	int mxi=1;
	for(int i=2;i<=l;i++)if(l%i==0)
	{
		bool fail=0;
		rep(j,l)if(j%i&&r[j]){fail=1;break;}
		
		if(!fail)mxi=i;
	}
	rep(i,l/mxi)r[i]=r[i*mxi];
	return l/mxi;
}

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		cin>>n;
		rep(i,n)
		{
			char c[2100]; cin>>c;
			for(int j=0;c[j];j+=2)rythm[i][j/2]=toi(c[j])*16+toi(c[j+1]);
			len[i]=minimize(rythm[i],strlen(c)/2);
		}
		int ans[1024]={0},anslen=1;
		rep(i,n)
		{
			int g=__gcd(anslen,len[i]);
			anslen*=len[i]/g;
			if(anslen>1024)
			{
				cout<<"Too complex."<<endl; goto END;
			}
		}
		rep(i,n)rep(j,len[i])ans[j*anslen/len[i]]|=rythm[i][j];
		rep(i,anslen)cout<<toa(ans[i]/16)<<toa(ans[i]%16);
		cout<<endl;
		
		END:;
	}
	return 0;
}