TopCoder SRM 389 Div1 Medium GuitarChords
問題
音階には12種類があり、それぞれの名前は、
A, A#, B, C, C#, D, D#, E, F, F#, G, G#
である。
G#の一つ上の音はAである。12の倍数個だけ離れた音は同じ音階である。
今、何も抑えないとそれぞれstrings[i]の音がなるギターがある。
これを、フレットを抑えてchord[i]のコードがなるようにしたい。
コードは、全ての弦がコードのどれかの音をなっていてかつ、全てのコードの音がどれかの弦によって鳴っていなければならない。
1番目のフレットを抑えると、その弦の音は1つだけ高い音になる。
抑え方の難易度を、抑える必要のあるフレットのうち(最も番号の高いもの)-(最も番号の低いもの)+1
で定義する。
ただし、抑える必要のないフレットはカウントにはいれない。
フレットを一つも抑える必要のないコードの難易度は0である。
コードの難易度の最小値を求めよ。
ソースコード
const char *name[]={"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"}; int n,m,str[6],chd[6]; int f[6],tmp[6],ans; bool use[6]; void rec(int c){ if(c==n){ rep(i,m)if(!use[i])return; int k=0; rep(i,n)if(f[i])tmp[k++]=f[i]; if(k==0)ans=0; rep(i,k){ sort(tmp,tmp+k); ans=min(ans,tmp[k-1]-tmp[0]+1); tmp[0]+=12; } return; } rep(i,m){ bool tuse=use[i]; use[i]=1; f[c]=chd[i]-str[c]; if(f[c]<0)f[c]+=12; rec(c+1); use[i]=tuse; } } class GuitarChords { public: int stretch(vector <string> strings, vector <string> chord) { n=strings.size(); m=chord.size(); rep(i,n)rep(j,12)if(strings[i]==name[j])str[i]=j; rep(i,m)rep(j,12)if(chord[i]==name[j])chd[i]=j; ans=inf; rec(0); return ans; } };