Hatena::Grouptopcoder

flowlighTの日記

 | 

2011-10-05

SRM520

| 11:51

実装遅すぎ

問題文よまなすぎ

結果

EasyMediumHardChallengeScore
194.91CompiledUnopened0194.91

351位でratingは1816->1799(-17)と微減。

Easy SRMCodingPhase

20:51

問題文

割り当てるluckの量と問題を解く順で全探索するだけ。

得点の与えられ方をCodeforcesルールと勘違いしていて無駄に時間がかかってしまった。

10分以内で解きたかった。

以下ソースコード


#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
const double EPS = 1E-9;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef complex<double> xy_t;
const int INF = 1 << 30;


class SRMCodingPhase {
public:
	int countScore(vector <int> ps, vector <int> skills, int luck) {
		int res = 0;
		int dec[3] = {2, 4, 8};
		int p[3] = {0, 1, 2};
		int t[3], t2[3], d[3], t3[3];;
		int points[3];
		do{
			rep(i, 3) t[i] = skills[p[i]];
			rep(i, 3) points[i] = ps[p[i]], d[i] = dec[p[i]];;
			rep(i, luck + 1)rep(j, luck + 1) rep(k, luck + 1){
				if(i + j + k <= luck){
					t2[0] = max(1, t[0] - i);
					t2[1] = max(1, t[1] - j);
					t2[2] = max(1, t[2] - k);
					t3[0] = t2[0];
					t3[1] = t2[1] + t3[0];
					t3[2] = t3[1] + t2[2];
					int score = 0;
					rep(l, 3) if(t3[l] <= 75) score += (points[l] - d[l] * t2[l]);
					
					res = max(res, score);
				}
			}
		}while(next_permutation(p, p + 3));

		return res;
	}
}

Medium SRMIntermissionPhase

20:51

問題文

dp[i][j]: i-1人目のスコアがj以上となる場合の数

cnt[i][j]: i人目がj点をとる場合の数

とすると、

for(int i = 0; i < description.size(); i++){

for(int j = 200005; j >= 0; j--){

dp[i+1][j] = (dp[i+1][j+1] + (dp[i][j+1] * (ll)cnt[i][j] % mod) % mod;

}

}

と漸化式を計算していけばdp[description.size()][0]が答えになる。

そして各(i, j)に対してcnt[i][j]がO(2^(問題の数))で計算できる。

a + b + c = jかつ(0 <= a <= amax, 0 <= b <= bmax, 0 <= c <= cmax)

となる(a, b, c)の数を直接求める方法がわからなかったので包除原理で

a + b + c = jかつ(a > amax または b > bmax または c > cmax)

となる(a, b, c)の数を求めてからcnt[i][j]を求めた。

蟻本に重複組み合わせのテーブルをO*1で作れる方法が書いてあった。

勉強しなおそう。

本番では時間切れ。

以下ソースコード

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
const double EPS = 1E-9;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef complex<double> xy_t;
const int INF = 1 << 30;

const ll mod = 1000000007;
const int sz = 200010;
int n;
int cnt[21][sz];
ll dp[21][sz]; //dp[i][j] : i-1盤目のスコアがj以上となる数

ll C(ll n, ll r){
	if(r == 0) return 1;
	else if(r == 1) return n;
	else{
		return (n * (n - 1) / 2) % mod;
	}
}

ll lower(ll sum, ll num){
	if(sum < 0) return 0;
	return C(sum + num - 1, num - 1);
}

ll calc(int *s, int *e, int sum){
	rep(i, 3){
		sum -= s[i];
		e[i] -= s[i];
	}
	ll total = lower(sum, 3);
	ll a = e[0], b = e[1], c = e[2];
	ll acnt = lower(sum - a - 1,3);
	ll bcnt = lower(sum - b - 1, 3);
	ll ccnt = lower(sum - c - 1, 3);
	ll abcnt = lower(sum - a - b - 2, 3);
	ll bccnt = lower(sum - b - c - 2, 3);
	ll cacnt = lower(sum - a - c - 2, 3);
	ll abccnt = lower(sum - a - b - c - 3, 3);
	//cout << sum << " " << "**" << total << "**" <<  acnt << " " << bcnt << " "<< ccnt << endl;
	//cout << abcnt << " " << bccnt << " " << cacnt << " " << abccnt << endl;
	return (total - (acnt + bcnt + ccnt - (abcnt + bccnt + cacnt) + abccnt) + mod * 3) % mod; 
}


class SRMIntermissionPhase {
public:
	int countWays(vector <int> points, vector <string> des) {
		n = des.size();
		int s[3], e[3];
		
		rep(i, n){
			rep(j, sz){
				rep(k, 3){
					if(des[i][k] == 'Y') s[k] = 1, e[k] = points[k];
					else s[k] = 0, e[k] = 0;
				}
				cnt[i][j] = calc(s, e, j);
			}
		}

		rep(i, sz) dp[0][i] = 1;
		rep(i, n){
			for(int j = sz - 1; j >= 0; j--){
				dp[i+1][j] = (dp[i+1][j+1] + (dp[i][j+1] * (ll)cnt[i][j]) % mod) % mod;
			}
		}
		return dp[n][0];
	}
}

*1:問題の数)*(点数

 |