SRM 539Div2 - Particle

Div1は550を誰かが解かないとノーコン(Div1)になるらしいです(2012/04/15 15:01)
~~問題見てみたいけど、Div2だと見れないみたいです。~~practiceに入りました。

Easy(174.03 / 250)
遺伝子の情報が与えられて、1つの家族として考えられるものの中で、最も人数の多いものを求める。

全探索すれば良い O(n^4)

class PlatypusPaternity{
	vector<string> f,m,s;
	int flen,mlen,slen,clen;
public:
	int solve(int a,int b){
		int ans = 0;
		vector<int> c(clen);
		for(int i = 0; i < clen; i++){
			c[i] = f[a][i] == 'Y' && m[b][i] == 'Y';
		}
		for(int i = 0; i < slen; i++){
			int res = 0;
			for(int j = 0; j < clen; j++){
				if(!c[j] && s[i][j] == 'Y'){
					res = 0;
					break;
				}
				if(c[j] && s[i][j] == 'Y')res++;
			}
			ans = max(ans,res);
		}
		return ans?ans+2:0;
	}
	
	int maxFamily(vector <string> femaleCompatibility, vector <string> maleCompatibility, vector <string> siblingGroups) {
		f = femaleCompatibility; m = maleCompatibility; s = siblingGroups;
		flen = f.size(); mlen = m.size(); slen = s.size(); clen = f[0].size();
		int ans = 0;
		for(int i = 0; i < flen; i++){
			for(int j = 0; j < mlen; j++){
				ans = max(ans,solve(i,j));
			}
		}
		return ans;
 	}
};

Medium(248.09 / 500)
デバッグに20分くらい使いました…。手元で実行したときのバグは取れませんでしたが、Arenaの方でtestしたら大丈夫だったから、そのまま投げました。
コードが少し冗長ですが、デバッグしてたらこうなってました。

a以上a+k以下の範囲が解に含まれる場所である場合
dp[a] = k+1
として、後で
dp[i] = max(dp[i],dp[i-1]-1)
とするとO(n)で数えることができます。2012年のJOI本戦にも同じ考え方で解ける問題があります。(因みに、その問題の他の解法をこの問題に使うこともできます)
いもす法で解いたと言ったが、いもす法では無かったかもしれない。
解いてないから分かりませんが、segtreeでも解けそうです。

int dp[16000000];

class Over9000Rocks{
public:
	int countPossibilities(vector <int> low, vector <int> up) {
		int len = low.size(),res = 0;
		for(int i = 1; i < (1<<len); i++){
			int l=0,u=0;
			for(int j = 0; j < len; j++){
				if(i&(1<<j)){
					l += low[j];
					u += up[j];
				}
			}
			l = max(l,9001);
			if(u>=l)dp[l] = max(dp[l],u-l+1);
		}
		
		for(int i = 9001; i < 16000000; i++){
				dp[i+1] = max(dp[i+1],dp[i]-1);
		}
		for(int i = 9001; i < 16000000; i++){
			if(dp[i]){
				res++;
				//cout<<i<<endl;
			}
		}
		return res;
 	}
};

Hard(Failed System Test / 1000)
Hardは初submit

全部'O'か全部'X'になるときだけ奇数になりそうだったから、それを実装したらWAでした。
そもそも嘘解法かもしれないし、問題を勘違いしていたり、見落としてることがあるかもしれない。

正解コードを見てもよく分からない…

3回challengeして1回だけ撃墜(TLE)できました。マイナスにならなくて良かった。
部屋内で自分以外はMediumを間違えてるのが分かっていたから、もう少し頑張りたかったです。

Score 422.12
Rating 1086 -> 1192