TopCoder SRM 716 Div1 Easy ConstructLCS、Div2 Medium ConstructLCSEasy

EasyもMediumも1ミスしたので、結果的に出なくてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14623
https://community.topcoder.com/stat?c=problem_statement&pm=14624

問題

01で構成された文字列A,B,Cがあるとする。
ab=len(LCA(A,B))、bc=len(LCA(B,C))、ca=len(LCA(C,A))の3値が与えられたとき、条件を満たすA,B,Cを構成せよ。

解法

ab≦bc≦caの場合の例を示す。

• 以下の3つの文字列を考える。
  • X='0'*ab
  • Y='1'*(bc-ab)
  • Z='0'*(ca-ab)
• こうするとA,B,Cは以下のように表現できる。
  • A = X+Z
  • B = X+Y
  • C = X+Y+Z
• このときLCAは以下のようになるので条件を満たす。
  • LCA(A,B) = X
  • LCA(B,C) = X+Y
  • LCA(C,A) = X+Z

class ConstructLCS {
	public:
	string construct(int ab, int bc, int ca) {
		int P[3]={ab,bc,ca};
		sort(P,P+3);
		string X=string(P[0],'0');
		string Y=string(P[1]-P[0],'1');
		string Z=string(P[2]-P[0],'0');
		
		if(ab<=bc&&bc<=ca) return (X+Z)+" "+(X+Y)+" "+(X+Y+Z);
		if(ab<=ca&&ca<=bc) return (X+Y)+" "+(X+Z)+" "+(X+Y+Z);
		if(bc<=ab&&ab<=ca) return (X+Y+Z)+" "+(X+Y)+" "+(X+Z);
		if(bc<=ca&&ca<=ab) return (X+Y+Z)+" "+(X+Z)+" "+(X+Y);
		if(ca<=ab&&ab<=bc) return (X+Y)+" "+(X+Y+Z)+" "+(X+Z);
		return (X+Z)+" "+(X+Y+Z)+" "+(X+Y);
	}
}

まとめ

6通りの並びをさぼったらミスった。