kmjp's blog

競技プログラミング参加記です

TopCoder SRM 815 : Div1 Easy Div2 Hard EllysKeys

色々いまいちでレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=13907&rd=18891

問題

N個のカギがある。
各カギの大きさはMで、それぞれ各Mか所が出っ張っているかへこんでいるかという情報が与えられる。

ここからいくつかのカギを重ね合わせ新たなカギを作ることを考える。
その際、

  • 最低1か所出っ張っていなければならない
  • 同じ箇所が出っ張っているカギが2個以上あってはならない

としたとき、カギの組み合わせは何通りか。

解法

f(n,mask) := n個目までのカギのうちいくつかを合わせたとき、出っ張っている箇所がmaskに該当するのは何通りか
を考えると、これは単純なDPでO(N*2^M)で解ける。

int dp[1<<20];

class EllysKeys {
	public:
	int getMax(vector <string> keys) {
		ZERO(dp);
		int N=keys.size();
		int W=keys[0].size();
		int mask;
		int ret=0;
		FORR(s,keys) {
			int ma=0;
			FORR(c,s) {
				ma=ma*2;
				if(c=='^') ma++;
			}
			for(mask=(1<<W)-1;mask>=0;mask--) {
				if((mask&ma)==0) dp[mask|ma]=max(dp[mask|ma],dp[mask]+1);
			}
			
		}
		for(mask=(1<<W)-1;mask>=0;mask--) {
			ret=max(ret,dp[mask]);
		}
		return ret;
		
	}
}

まとめ

問題を解くより問題文を理解することの方が疲れる…。