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である。


コードの難易度の最小値を求めよ。

制約条件

stringsの要素数≦6
chordの要素数≦6
strings[i]およびchord[i]は音階のいずれかである。

方針

全探索。
再帰で書いて、最後に全部の音がカバーされているかを見る。


12個音をずらした弾き方があるので、それは最も低い音を12個ずらすというのをk通り全部試してみれば十分。

ソースコード

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;
  }
};