kojingharangの日記

SRM 585 Div1 250 TrafficCongestion

16:37 |

• 高さ TH の完全二分木がある。適当な２頂点を選んで２点間のエッジを塗る。
• １つのエッジは２回塗らないようにしたい。最低何回塗れば全エッジを塗れるか。
• 1≦TH≦1,000,000

• とりあえず長いのということで一番左の葉から一番右の葉まで塗ってみるも、結局余る点がちらほら出る
• 分かりやすそうな塗り方ということで下から∧状に塗ってみる
• (証明なしｗ)

• accepted

class TrafficCongestion {
	public:
	int theMinCars(int TH) {
		ll ans = 1;
		REP(i, TH-1) ans = (2 * ans + (i%2==0 ? 1 : -1)) % 1000000007LL;
		return ans;
	}
};

↓ちなみに modulo の数をコピペしてもコンパイル通る（けど 0 か 1 しか返らない）のでややこしい。。

class TrafficCongestion {
	public:
	int theMinCars(int TH) {
		ll ans = 1;
		REP(i, TH-1) ans = (2 * ans + (i%2==0 ? 1 : -1)) % 1,000,000,007LL;
		return ans;
	}
};

ツイートする

SRM 585 Div1 500 LISNumber

16:00 |

• 数字 i が CS[i] 個あるとき、それらを並び替えて最長部分増加列の個数が K 個になるようにしたい。何通りあるか求める問題。
• 1≦N≦36, 1≦CS[i]≦36, 1≦K≦1296

• dp[n][k] ... CS[i], i in [0, n) を使って k 個の LIS を作る方法の個数と置くのだろう
• 更新は dp[n][k] = Σ(pk in [0, k]) dp[n-1][pk] * (LISの個数がpk個からk個になるようなnの挿入箇所が何通りあるか)
• dp[N][K] が答え

• どんなときに LIS の個数が増えるか？
• 各 LIS の最後に n を置くと、LIS の個数は増えない（n-1までの数字しか置いてないので）。こういう場所は pk 個ある。
• 新しく置く CS[n] 個の n のうち、CS[n]-(k-pk) 個はこれらの場所から選んで 1 コずつおけばいい。
• なので Comb(pk, CS[n]-(k-pk)) 通り

• それ以外の場所に複数個 n を挿入すると、LIS の個数は置いただけ増える. その中から k-pk 個重複ありで置く。
• Homogeneous Product(いままで置いた数字の数+1 - pk, k-pk)
• Homogeneous Product(N, K) == Combination(N+K-1, K) ... 区切りを置くと考えるやつ
• としたがサンプル合わず→おわり

• (あとで)

• LIS の個数が増えないとこに置いたら、以降その場所は LIS の個数が増える場所に変わるのであった
• 0 0 0 (LIS 3コ)
• 0 0 0 1 (LIS 3コ)
• 0 0 0 1 1 (LIS 4コ)

• ということで LIS の個数が増えないとこに実際に置く数分だけ LIS の個数が増える場所を増やして
• Homogeneous Product(いままで置いた数字の数+1 - (pk-(CS[n]-(k-pk))), k-pk)
• としたら通った。

• accepted in practice

#define MOD 1000000007LL
#define N_MAX 1300
#define K_MAX 1300
int comb[N_MAX][K_MAX];
ll combf(int n, int k) {
	if(!(0<=n && n<N_MAX)) return 0;
	if(!(0<=k && k<K_MAX)) return 0;
	return comb[n][k];
}

class LISNumber {
	public:
	int count(vector <int> CS, int K) {
		REP(n, N_MAX) comb[n][0] = 1;
		RANGE(n, 1, N_MAX) RANGE(m, 1, K_MAX) comb[n][m] = ((ll)comb[n-1][m-1] + comb[n-1][m]) % MOD;
		
		int N=CS.size();
		VVI dp(N+1, VI(K+1)); // dp[n][k] ... CS[i], i in [0, n) を使って k 個の LIS を作る方法の個数 % MOD
		dp[0][0] = 1;
		ll sum = 1;
		RANGE(i, 1, N+1) {
			RANGE(k, 1, K+1) {
				RANGE(pk, 0, k+1) {
					int add = k-pk; // in [0, k]
					int rest = CS[i-1] - add;
					ll plus = dp[i-1][pk] * combf(sum-(pk-rest)-1+add, add) % MOD * combf(pk, rest) % MOD;
					dp[i][k] += plus;
					dp[i][k] %= MOD;
				}
			}
			sum += CS[i-1];
		}
		return dp[N][K];
	}
};

ツイートする