Hatena::Grouptopcoder

TopCoder Memo@kagamiz

02.07.2013 (Thu)SRM 569 Div2

テスト前の予備日だったので, 出場してみました. 学校の日だと2 番目に出やすい時間の開催なので助かります.

結果 : ooo +2/-0 1222.08pts 4th. 1178 → 1433 (+255)

JOI 前ということで色々練習していたのが功を奏したようです. よかったー!

Easy (250 pts.) TheJediTestDiv2

問題文 :

N個のグループにそれぞれA[i]人の人がいる. コーチひとりは1つのグループに居るJ 人の人を鍛えることが出来る.コーチは最低何人必要か?

ただし 1 人だけY 人を鍛えることが出来るコーチがいる(この人は数に含まなくて良い).

解法 :

N は高々50 なので, 全てのNについて全探索すれば良い. O(N^2).

(一番大きい要素を探してそれからY 人を引いても良い. こっちはO(N))

Y 人を引いた後, A[i] が負になるコードがちらほらあったが, Challengeしそびれてしまった.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long lint;

class TheJediTestDiv2 {
	public:
		int countSupervisors(vector <int> s, int Y, int J)
		{
			int res = INT_MAX;
			
			for (int i = 0; i < s.size(); i++){
				vector<int> t = s;
				t[i] -= min(t[i], Y);
				int temp = 0;
				for (int j = 0; j < s.size(); j++){
					temp += (t[j] + J - 1) / J;
				}
				res = min(res, temp);
			}
			
			return (res);
		}
};

Medium (500 pts.) TheDeviceDiv2

問題文 :

長さM のビット列がN 個与えられる. N 個の中から2 つのビット列を選んで, i 番目のビットにAND, OR, XOR のいずれかの操作を行う(各ビットごとに異なって良い). このとき, それぞれのビットにどの操作をしたか特定できるか?

解法 :

AND, OR, XOR の操作は, 1 が2 つ, 0 が1 つあれば識別できるので, 各列で1 と 0 を数えて, それぞれが必要な数なければNO を返す.

1 と 0 の両方が1つ以上あれば良いと判断している人のコードを2 つ落とした(1 0 などで落ちる.)

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long lint;

class TheDeviceDiv2 {
	public:
		string identify(vector <string> p)
		{
			string res;
			int h = p.size(), w = p[0].size();
			int col[2][64] = {{0}};
			
			for (int i = 0; i < h; i++){
				for (int j = 0; j < w; j++){
					col[p[i][j] - '0'][j]++;
				}
			}
			
			for (int i = 0; i < w; i++) if (col[0][i] < 1 || col[1][i] < 2) return ("NO");
			
			return ("YES");
		}
};	

Hard (1000 pts.) MegaFactorialDiv2

問題文 :

正の整数n , m について, n!m = (n - 1)!m * n!(m - 1) と定義する. (n = 0のときは1, m = 0のときはn) このとき, N!K の相異なる約数の個数を求めよ.

解法 :

まず, 2 ~ 1000 までの数を素因数分解しておく. 約数の個数は, n!mの素因数p[i]がA[i]個あるとすると,

Π(A[i] + 1)

となるので, 素因数の個数をDPで求める.

数Aの素因数p[i]がA[i]個, 数Bの素因数p[i]がB[i]個あるとすると, かけた数C[i]の素因数p[i]の個数はA[i] + B[i]個になるので,

O(N * K * (1000までの素数の個数)) = O(N * K * 178) = O(NK)

でN!K のそれぞれの素因数の個数が求まる. ここまでできれば, あとは N!K について Π(A[i] + 1) を計算してやれば良い.

数が大きいので, MOD を取り忘れないように注意.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long lint;

int nums[2][101][170];
map<int, int> primes;
int fact[1001][170];

#define MOD (1000000009)

void factorize(int x)
{
	int X = x;
	for (int i = 2; ; i++){
		if (x == 1) return;
		while (x % i == 0){
			fact[X][primes[i]]++;
			x /= i;
		}
	}
}

class MegaFactorialDiv2 {
	public:
		int countDivisors(int N, int K)
		{
			lint res;
			
			int idx = 0;
			primes[1] = idx++;
			for (int i = 2; i <= 1000; i++){
				bool ok = true;
				for (int j = 2; j < i; j++){
					if (i % j == 0) ok = false;
				}
				if (ok) primes[i] = idx++;
			}
			
			memset(fact, 0, sizeof(fact));
			for (int i = 1; i <= 1000; i++){
				factorize(i);
			}
			
			memset(nums, 0, sizeof(nums));
			
			/*
			for (int j = 1; j <= N; j++){
				for (int k = 0; k < 170; k++){
					nums[j & 1][0][k] += fact[j][k];
				}
			}
			*/
			
			for (int i = 1; i <= N; i++){
				memset(nums[i & 1], 0, sizeof(nums[i & 1]));
				for (int j = 0; j <= K; j++){
					if (j){
						for (int k = 0; k < 170; k++){
							nums[i & 1][j][k] += nums[i & 1][j - 1][k];
							nums[i & 1][j][k] %= MOD;
							nums[i & 1][j][k] += nums[(i - 1) & 1][j][k];
							nums[i & 1][j][k] %= MOD;
						}
					}
					else {
						for (int k = 0; k < 170; k++){
							nums[i & 1][0][k] = fact[i][k];
							nums[i & 1][0][k] %= MOD;
						}
					}
				}
			}
			
			res = 1ll;
			
			for (int i = 0; i < 170; i++){
				res *= (nums[N & 1][K][i] + 1);
				res %= MOD;
			}
			return (res);
		}
};