TopCoder SRM 715 Div1 Medium ClassicTowers

手間取ったけど一応一発AC。
https://community.topcoder.com/stat?c=problem_statement&pm=14591

問題

ハノイの塔の問題をアレンジした問題である。
計(A+B+C)個の大きさの異なるディスクが、初期状態で3つの杭にA,B,C個それぞれ上から小さい順に差さっているとする。
この時、全ディスクをどこか1つの杭に上から大きさが小さい順に並べるまでの最小手数がK回となるものがあれば、それを構築せよ。

解法

以下を考える。
F(a,b,c) := 3つの杭にa,b,c個ディスクがあるとき、3つめの杭にディスクを集めるまでの最短手数の最大値
G(a,b,c) := 同最小値
これらの値は、最大(a+b+c番目のサイズ)のディスクが3つの杭それぞれのどこかにある場合についてメモ化再帰の要領で考えれば求めることができる。

F(a,b,c)≦K≦G(a,b,c)であれば、3本の杭のうち最大のディスクを3つめの杭に置くことが可能である。
…という手順を繰り返し、残された最大サイズのディスクを3つの杭のどこに置くか順次考えていけばよい。

ll ma[53][53][53];
ll mi[53][53][53];

class ClassicTowers {
	public:
	ll getma(int A,int B,int C) {
		if(ma[A][B][C]>=0) return ma[A][B][C];
		ll ret=0;
		if(A) ret=max(ret,getma(A-1,C,B)+1+getma(0,A+B+C-1,0));
		if(B) ret=max(ret,getma(B-1,C,A)+1+getma(0,A+B+C-1,0));
		if(C) ret=max(ret,getma(A,B,C-1));
		return ma[A][B][C]=ret;
	}
	ll getmi(int A,int B,int C) {
		if(mi[A][B][C]>=0) return mi[A][B][C];
		if(A+B+C==0) return 0;
		ll ret=1LL<<60;
		if(A) ret=min(ret,getmi(A-1,C,B)+1+getmi(0,A+B+C-1,0));
		if(B) ret=min(ret,getmi(B-1,C,A)+1+getmi(0,A+B+C-1,0));
		if(C) ret=min(ret,getmi(A,B,C-1));
		return mi[A][B][C]=ret;
	}
	
	string hoge(int A,int B,int C,string a,string b,string c,ll k) {
		if(A<0 || B<0 || C<0) return string(51,'Z');
		if(A+B+C==0 && k==0) return "";
		if(k<getmi(A,B,C) || getma(A,B,C)<k) return string(51,'Z');
		
		int cnt=A+B+C;
		string s=string(51,'z');
		if(s.size()>cnt) s=hoge(A-1,C,B,a,c,b,k-(1LL<<(cnt-1)))+a;
		if(s.size()>cnt) s=hoge(B-1,C,A,b,c,a,k-(1LL<<(cnt-1)))+b;
		if(s.size()>cnt) s=hoge(A,B,C-1,a,b,c,k)+c;
		return s;
	}
	
	string findTowers(long long k, vector <int> count) {
		MINUS(ma);
		MINUS(mi);
		
		string s=string(51,'z');
		int c=count[0]+count[1]+count[2];
		if(s.size()>c) s=hoge(count[0],count[1],count[2]-1,"A","B","C",k)+"C";
		if(s.size()>c) s=hoge(count[1],count[0],count[2]-1,"B","A","C",k)+"C";
		if(s.size()>c) s=hoge(count[0],count[2],count[1]-1,"A","C","B",k)+"B";
		if(s.size()>c) s=hoge(count[2],count[0],count[1]-1,"C","A","B",k)+"B";
		if(s.size()>c) s=hoge(count[1],count[2],count[0]-1,"B","C","A",k)+"A";
		if(s.size()>c) s=hoge(count[2],count[1],count[0]-1,"C","B","A",k)+"A";
		if(s.size()>c) return "";
		return s;
	}
}

まとめ

コードはだいぶ複雑になってしまった。