Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-07-27SRM513 Div1

SRM513 Div1 250 YetAnotherIncredibleMachine

| 15:18 | SRM513 Div1 250 YetAnotherIncredibleMachine - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM513 Div1 250 YetAnotherIncredibleMachine - SRM diary(Sigmar) SRM513 Div1 250 YetAnotherIncredibleMachine - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

どう見ても全探索するだけ

の割には時間かかってしまった。。。

と思いきや皆もっと時間かかっていた。不思議。みんな高速化を頑張ってたのかな。


ソースコード

const int MOD=1000000009; 

class YetAnotherIncredibleMachine { 
public: 
  int countWays(vector <int> mount, vector <int>len, vector <int> balls) { 
    int n=mount.size(); 
    int m=balls.size(); 

    ll res=1; 
    for(int i=0; i<n; i++) { 
      int cnt=0; 
      for(int k=mount[i]-len[i]; k<=mount[i]; k++) { 
        bool ok=true; 
        for(int j=0; j<m; j++) { 
          if(balls[j]>=k && balls[j]<=k+len[i]) ok=false; 
        } 
        if(ok) cnt++; 
      } 
      res=(res*cnt)%MOD; 
    } 
    return res; 
  } 
};

SRM513 Div1 500 PerfectMemory

| 15:18 | SRM513 Div1 500 PerfectMemory - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM513 Div1 500 PerfectMemory - SRM diary(Sigmar) SRM513 Div1 500 PerfectMemory - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

神経衰弱

ペアが両方Openしたマーク数(two)と片方だけOpenしたマーク数(one)を状態として持つDP

DP更新のパターンを漏れ無く考慮できていればすぐ終わる

私は最後まで漏れに気づきませんでした


ソースコード

double memo[1252][1252];

class PerfectMemory {
public:
	int N, M;
	double rec(int two, int one) {
		if(two==N*M/2) return 0;
		if(memo[two][one]>=0) return memo[two][one];
		double res=0;
		int back=N*M-two*2;
		int unopened=back-one;
		int noappear=unopened-one;
		if(one>0) res+=(rec(two+1, one-1)+1)*((double)one/unopened);
		if(noappear>=2) res+=(rec(two+1, one)+1)*((double)noappear/unopened)*((double)1/(unopened-1));
		if(one>0 && noappear>0) res+=(rec(two+1, one)+2)*((double)noappear/unopened)*((double)one/(unopened-1));
		if(noappear>=3) res+=(rec(two, one+2)+1)*((double)noappear/unopened)*((double)(noappear-2)/(unopened-1));
		memo[two][one]=res;
		return res;
	}
	double getExpectation(int N, int M) {
		double res;

		this->N=N; this->M=M;
		memset(memo, -2, sizeof(memo));
		res=rec(0, 0);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110727