Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-05SRM520 Div1

  • 250:218.59, 500:Opened, score:218.59, rank:204, rating:2079(-5)
  • 500が最近全然解けない。だめだ・・・・

SRM520 Div1 250 SRMCodingPhase

| 22:21 | SRM520 Div1 250 SRMCodingPhase - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM520 Div1 250 SRMCodingPhase - SRM diary(Sigmar) SRM520 Div1 250 SRMCodingPhase - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

どう見てもイテレーションするだけ。

随分計算量が余裕すぎる。まあいいか・・・

書いた

ストレートフォワードに書いたらえらくもっさりしたコードになった


ソースコード

割り振るluckを全探索して、解く順番を全探索する

しかし、解く問題を2^3のビットマスクで決めて、得点の高い問題からGreedyにluckを割り振ったほうが書くのは楽そうだと思った

class SRMCodingPhase {
public:
	int countScore(vector <int> points, vector <int> skills, int luck) {
		int res=0;

		int mul[3]={2,4,8};
		int l[3];
		for(l[0]=0; l[0]<=luck; l[0]++) {
			for(l[1]=0; l[1]<=luck-l[0]; l[1]++) {
				l[2]=luck-l[0]-l[1];
				vector <int> sk(3);
				for(int i=0; i<3; i++) sk[i]=max(1, skills[i]-l[i]);
				vector <int> perm(3);
				for(int i=0; i<3; i++) perm[i]=i;
				do {
					int pass=0;
					int sum=0;
					for(int i=0; i<3; i++) {
						if(75-pass>=sk[perm[i]]) {
							pass+=sk[perm[i]];
							sum+=points[perm[i]]-sk[perm[i]]*mul[perm[i]];
						}
					}
					res=max(res, sum);
				} while(next_permutation(perm.begin(), perm.end()));
			}
		}

		return res;
	}
};

SRM520 Div1 500 SRMIntermissionPhase

| 22:21 | SRM520 Div1 500 SRMIntermissionPhase - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM520 Div1 500 SRMIntermissionPhase - SRM diary(Sigmar) SRM520 Div1 500 SRMIntermissionPhase - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

仮にways[i][val](=i番目の人がval点取る場合の数)を計算できたとすると、

愚直にやれば、dp[i-1][val+j]+=dp[i][val]*ways[i-1][val+j]でi-1番目の人がval+j点取るようなDPが計算できる

まあでもjの範囲が広くDP更新の計算量が200000とかあって全然無理・・

ways[i][val]の計算方法も全然分からん。だめだ・・・

色々考えたが結局無為に1時間のコーディングフェーズを過ごしてしまった

こんな難しい問題で100人も解けるなんてどうなってるんだ。みんな頭いい


後で

色々調べたらすごく典型的なDPで解ける問題だった。むしろ100人しか解けなかったのが不思議なくらい。

なんでこんな解法に気づかなかったのか。。。


かなり色んな解法があるみたいだけど、簡単なのは以下のようなsumを計算する方式と思う。(こういうのはいっぱい解いてるはずなのだが・・)

dp[i-1][val+j]+=dp[i][val]*ways[i-1][val+j]という更新式を考えていたが、

dp[i][val]+=dp[i+1][val-j]*ways[i][val]という式に変えてみる。

jをイテレートするので、更に変形すると

dp[i][val]=(dp[i+1][val-1]+dp[i+1][val-2]+...+dp[i+1][0])*ways[i][val]

というわけで、dpsum[i+1][val-1]みたいな変数で、dp[i+1][0]+...+dp[i+1][val-1]の和を計算しておけばO(1)で更新できる

これが分かれば、waysの計算も全く同じような方法で計算できることがわかる。

(waysの場合は、各問題ごとに得点の上限が決められているため、引き算が必要になる)


ソースコード

色々書きやすいように変形してるので、上記で書いたまんまの式は使ってません

書いてみて思ったが、直感的な感覚よりかなりコーディングが複雑になる

const int MOD=1000000007;

class SRMIntermissionPhase {
public:
	int countWays(vector <int> points, vector <string> description) {
		int res;

		//waysはi番目の人ではなく、NとYの組み合わせに対応して2^3のマスクで計算
		int ways[1<<3][200010];
		int wayssum[200010];
		for(int mask=0; mask<(1<<3); mask++) {
			memset(ways[mask], 0, sizeof(ways[mask]));
			ways[mask][0]=1;
			for(int i=0; i<3; i++) {
				if(!(mask&(1<<i))) continue;
				memset(wayssum, 0, sizeof(wayssum));
				wayssum[0]=ways[mask][0];
				for(int val=1; val<=200000; val++) wayssum[val]=(wayssum[val-1]+ways[mask][val])%MOD;
				memset(ways[mask], 0, sizeof(ways[mask]));
				for(int val=1; val<=200000; val++) {
					ways[mask][val]=wayssum[val-1];
					if(val-points[i]-1>=0) ways[mask][val]-=wayssum[val-points[i]-1];
					if(ways[mask][val]<0) ways[mask][val]+=MOD;
				}
			}
		}

		int dp[200010];
		int dpsum[200010];
		for(int i=0; i<=200001; i++) dpsum[i]=1;
		reverse(description.begin(), description.end());
		int n=description.size();
		for(int i=0; i<n; i++) {
			int mask=0;
			for(int j=0; j<3; j++) if(description[i][j]=='Y') mask|=(1<<j);
			memset(dp, 0, sizeof(dp));
			for(int val=1; val<=200001; val++) dp[val]=(ll)dpsum[val-1]*ways[mask][val-1]%MOD;
			memset(dpsum, 0, sizeof(dpsum));
			dpsum[0]=dp[0];
			for(int val=1; val<=200001; val++) dpsum[val]=(dpsum[val-1]+dp[val])%MOD;
		}

		res=dpsum[200001];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111005