TopCoderOpen 2016 Round1C Medium ThreeProgrammers

Hardで変に苦戦して書くの遅れた。
https://community.topcoder.com/stat?c=problem_statement&pm=14233

問題

A,B,C３人で取り組む仕事がある。
各人が取り組める仕事は決まっている。

毎日、誰か１人が自分担当の仕事を一つしなければならない。

• Aは毎日働ける。
• Bは1日働くと1日休みが必要である。
• Cは1日働くと2日休みが必要である。

仕事が与えられたとき、条件を満たす仕事順が存在するならそれを求めよ。

解法

総当たりして戻すだけ。
以下の状態を順に更新し、全仕事をやりきるケースがあるか求めよう。
dp[Aの残り仕事数][Bの残り仕事数][Cの残り仕事数][昨日の仕事][一昨日の仕事] := その状態に至る直前の仕事

後は直前の仕事を順に巻き戻していけば良い。

int from[51][26][18][3][3];

class ThreeProgrammers {
	public:
	string validCodeHistory(string code) {
		int i;
		int a=0,b=0,c=0;
		
		
		FORR(r,code) {
			if(r=='A') a++;
			if(r=='B') b++;
			if(r=='C') c++;
		}
		if(b>25 || c>17) return "impossible";
		
		MINUS(from);
		from[a][b][c][0][0]=0;
		int x,y,z,p,p2;
		for(z=c;z>=0;z--) for(y=b;y>=0;y--) for(x=a;x>=0;x--)
		FOR(p,3) FOR(p2,3) if(from[x][y][z][p][p2]>=0) {
			if(x) from[x-1][y][z][0][p] = p2;
			if(y && p!=1) from[x][y-1][z][1][p] = p2;
			if(z && p!=2 && p2!=2) from[x][y][z-1][2][p] = p2;
		}
		
		FOR(p,3) FOR(p2,3) if(from[0][0][0][p][p2]>=0) {
			string S;
			x=y=z=0;
			while(x!=a || y!=b || z!=c) {
				i = from[x][y][z][p][p2];
				S += 'A'+p;
				if(p==0) x++;
				if(p==1) y++;
				if(p==2) z++;
				p=p2;
				p2=i;
			}
			reverse(S.begin(),S.end());
			return S;
		}
		
		return "impossible";
	}
}

まとめ

面倒なだけで余り面白くないな…。