SRM389 div2 hard

全探索で間に合う、難しさの計算も2^6通り全て試してよい

#include <string>
#include <sstream>
#include <vector>

using namespace std;

class GuitarChords
{
	public:

		vector<int> strings;
		vector<int> chord;
		vector<int> play;
		int sN,cN,ans,all;

		int s2i(string s)
		{
			if(s=="A")	return 0;
			if(s=="A#")	return 1;
			if(s=="B")	return 2;
			if(s=="C")	return 3;
			if(s=="C#")	return 4;
			if(s=="D")	return 5;
			if(s=="D#")	return 6;
			if(s=="E")	return 7;
			if(s=="F")	return 8;
			if(s=="F#")	return 9;
			if(s=="G")	return 10;
			if(s=="G#")	return 11;
			else		return -1;
		}

		int difficulty()
		{
			int mask=0;
			for(int i=0;i<sN;i++)
				mask=(mask | (1<<play[i]));
			if(mask!=all)
				return (1<<28);

			vector<int> fred;
			for(int i=0;i<sN;i++)
			{
				int a=play[i]-strings[i];
				if(a!=0)
					fred.push_back(a%12);
			}
			
			if(fred.size()==0)
				return 0;
			int r=(1<<28);
			int fN=fred.size();
			for(mask=0;mask<(1<<fN);mask++)
			{
				int t=0;
				for(int i=0;i<fN;i++)
					for(int j=i+1;j<fN;j++)
					{
						int a=(mask & (1<<i)) ? fred[i]+12 : fred[i];
						int b=(mask & (1<<j)) ? fred[j]+12 : fred[j];
						if(a<b)
							swap(a,b);
						t=max(t,a-b);
					}
				t++;
				r=min(t,r);
			}
			return r;
		}

		void DFS(int index)
		{
			if(index==sN)
			{
				ans=min(ans,difficulty());
				return;
			}
			for(int i=0;i<cN;i++)
			{
				play[index]=chord[i];
				DFS(index+1);
			}
			return;
		}

		int stretch(vector<string> _strings,vector<string> _chord)
		{
			sN=_strings.size();
			cN=_chord.size();
			strings=vector<int>(sN);
			chord=vector<int>(cN);
			play=vector<int>(sN);

			for(int i=0;i<sN;i++)
				strings[i]=s2i(_strings[i]);
			all=0;
			for(int i=0;i<cN;i++)
			{
				chord[i]=s2i(_chord[i]);
				all=(all | (1<<chord[i]));
			}

			ans=(1<<28);
			DFS(0);

			return ans;
		}
};