Hatena::Grouptopcoder

TopCoder Memo@kagamiz

03.13.2014 (Thu)

SRM 612 Div2 Hard - PowersOfTwo

| 22:04 | はてなブックマーク -  SRM 612 Div2 Hard - PowersOfTwo - TopCoder Memo@kagamiz

問題文 : PowersOfTwo

概要 :

2 のべきからなる配列 A が与えられる. これらを幾つか足しあわせて出来る数の総数を求めよ.

制約 :

1 ≦|A| ≦ 50

1 ≦ A_i ≦ 2^50

A_i は2 のべき

続きを読む

03.05.2014 (Wed)

SRM 610 div2

| 21:45 | はてなブックマーク -  SRM 610 div2 - TopCoder Memo@kagamiz

KawigiEdit の設定ついでに解きました.

続きを読む

08.13.2013 (Tue)SRM 588 div1

\/ 大敗北 \/

xx-...

1508 -> 1416 (-84).

悔い改めましょう.

250 GUMIAndSongsDiv1

tone[i] の整列された順をうれしい順序としてDP を行うか, tone[i]の上限・下限を定めてgreedy を行えば良い. O(n^3).

なぜか謎1 次元DP をしてしまった... が, 自信なかったし遅くても確実に自信が持てるアルゴリズムを考える必要がありますね.

#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 GUMIAndSongsDiv1 {
	public:
		int maxSongs(vector <int> duration, vector <int> tone, int T)
		{
			int res;
			int dp[51][51];
			vector<pair<int, int> > v;
			
			for (int i = 0; i < tone.size(); i++)
				v.push_back(make_pair(tone[i], duration[i]));
			
			sort(v.begin(), v.end());
			for (int i = 0; i < 51; i++)
				for (int j = 0; j < 51; j++)
					dp[i][j] = 1000000000;
			
			for (int i = 0; i <= tone.size(); i++)
				dp[0][i] = 0;
			
			res = 0;
			for (int i = 1; i <= tone.size(); i++){
				for (int j = 1; j <= i; j++){
					for (int k = 1; k <= i; k++){
						if (k != 1 && i == j) continue;
						dp[k][i] = min(dp[k][i], dp[k - 1][j] + v[i - 1].second + (k != 0) * (v[i - 1].first - v[j - 1].first));
						if (dp[k][i] <= T) res = max(res, k);
					}
				}
			}
			
			return (res);
		}
};

450 KeyDungeonDiv1

dp[訪れた先][持っている赤鍵] = もっている緑鍵の最大値, でdp をする. 白鍵は分配してやれば良い.

#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>
#include <cassert>

using namespace std;

typedef long long lint;

int dp[4096][265];

class KeyDungeonDiv1 {
	public:
		int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
		{
			int res;
			int N = doorR.size();
			
			memset(dp, -1, sizeof(dp));
			
			for (int i = 0; i <= keys[2]; i++)
				dp[0][keys[0] + i] = keys[1] + keys[2] - i;
			
			res = 0;
			for (int i = 0; i < 1 << N; i++){
				for (int j = 0; j < N; j++){
					if (!(i >> j & 1)){
						for (int k = 0; k < 265; k++){
							if (k >= doorR[j] && dp[i][k] >= doorG[j]){
								for (int l = 0; l <= roomW[j]; l++){
									dp[i | (1 << j)][k - doorR[j] + roomR[j] + l] = max(dp[i | (1 << j)][k - doorR[j] + roomR[j] + l], dp[i][k] - doorG[j] + roomG[j] + roomW[j] - l);
								}
							}
						}
					}
				}
			}
			
			for (int i = 0; i < 1 << N; i++) for (int j = 0; j < 265; j++) if (~dp[i][j]) res = max(res, dp[i][j] + j);
			
			return (res);
		}
};

05.25.2013 (Sat)SRM 579 Div1

ものすごく眠い中参加しました.

結果 : o-- +0/-0 143.42 pts 1494 → 1508 (+14) !!黄色!!

250 UndoHistory

問題文 -> コチラ

問題概要 :

複雑な仕様のエディタがある.

タイプ+クリック数の最小値を求めよ.

解法 :

問題文で記述しているとおりに実装するだけ. 最初にbuffer に"" を詰めておけば怖いことはない.

"複雑な仕様" を微妙に読み違えていて亀コーディングしましたが, Systest は通ったしよかったよかった...

#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 UndoHistory {
  public:
    int minPresses(vector <string> l)
    {
      int res = l.size();
      vector<string> buffers;
      
      buffers.push_back("");
      
      string prevstr = "";
      for (int i = 0; i < l.size(); i++){
          int idx = -1;
          for (int j = l[i].size(); (int)l[i].size() - j >= 0; j--){
            for (int k = 0; k < buffers.size(); k++){
              if (l[i].substr(0, j) == buffers[k]){
                idx = j;
              }
              if (~idx) break;
            }
            if (~idx) break;
          }
          
          int cost1 = (l[i].size() >= prevstr.size() && l[i].substr(0, prevstr.size()) == prevstr) ? l[i].size() - prevstr.size() : 9999999;
          int cost2 = l[i].size() - idx + 2;
          
          if (cost1 < cost2){
            res += cost1;
            for (int j = prevstr.size(); j < l[i].size(); j++)
              buffers.push_back(l[i].substr(0, j + 1));
          }
          else {
            res += cost2;
            for (int j = idx; j < l[i].size(); j++){
              buffers.push_back(l[i].substr(0, j + 1));
            }
          }
          
          prevstr = l[i];
      }
      
      return (res);
    }
  
    

}; 

450 TravellingPurchasingMan

問題文 -> コチラ

問題概要 :

N 個のお店があって, 0 から N - 1 までの番号がついている. あなたは0 から M - 1 番目までのお店に興味がある.

また, いくつかの店間には重み付きの無向辺がはられている.

0 ≦ x ≦ M - 1 を満たすx について, 時刻A[x] から B[x] の間にC[x] 時間滞在すればあなたはその店で満足できる.

店 N - 1 から出発するとき, 満足できる店の最大値を求めよ.

1 ≦ N ≦ 50, 1 ≦ M ≦ min(N, 16)

解法 :

M 頂点だけのグラフに縮約して, Warshall-Floyd + bitDP で十分.

しかし, 癖で店番号をデクリメントしていてサンプルが通らなかった... ザンネン

#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 st[64], en[64], stay[64];

struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};

int mask;
vector<Edge> G[64];
int dp[64][1 << 16];

class TravellingPurchasingMan {
	public:
		int maxStores(int N, vector <string> iStores, vector <string> rds)
		{
			int res = 0;
			
			for (int i = 0; i < iStores.size(); i++){
				sscanf(iStores[i].c_str(), "%d %d %d", st + i, en + i, stay + i);
			}
			
			int cst[64][64];
			
			for (int i = 0; i < 64; i++){
				for (int j = 0; j < 64; j++)
					cst[i][j] = 1000000000;
				cst[i][i] = 0;
			}
			
			for (int i = 0; i < rds.size(); i++){
				int a, b, c;
				sscanf(rds[i].c_str(), "%d %d %d", &a, &b, &c);
				cst[a][b] = c;
				cst[b][a] = c;
			}
			
			for (int k = 0; k < N; k++)
				for (int i = 0; i < N; i++)
					for (int j = 0; j < N; j++)
						cst[i][j] = min(cst[i][j], cst[i][k] + cst[k][j]);
			
			for (int i = 0; i < 64; i++)
				G[i].clear();
			
			for (int i = 0; i < iStores.size(); i++){
				for (int j = 0; j < iStores.size(); j++){
					if (cst[i][j] != 1000000000)
						G[i].push_back(Edge(j, cst[i][j]));
				}
			}
			
			mask = (1 << iStores.size()) - 1;
			
			for (int i = 0; i < 64; i++)
				for (int j = 0; j < 1 << 16; j++)
					dp[i][j] = 1000000000;
			
			for (int i = 0; i < iStores.size(); i++){
				if (cst[N - 1][i] <= en[i]){
					dp[i][1 << i] = max(st[i], cst[N - 1][i]) + stay[i];
				}
			}
			
			
			for (int j = 0; j < 1 << (iStores.size()); j++){
				for (int i = 0; i < iStores.size(); i++){
					if (dp[i][j] != 1000000000){
						res = max(res, __builtin_popcount(j));
						for (int k = 0; k < G[i].size(); k++){
							if (dp[i][j] + G[i][k].cost <= en[G[i][k].to]){
								dp[G[i][k].to][j | ((1ll << G[i][k].to) & mask)] = min(dp[G[i][k].to][j | ((1ll << G[i][k].to) & mask)],
																			       max(dp[i][j] + G[i][k].cost, st[G[i][k].to]) + stay[G[i][k].to]);
							}
						}
					}
				}
			}
			
			
			return (res);
		}
};

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);
		}
};