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 のべき


解法 :

まず, A を降順にソートする. そして

dp[i][j][k] := 上から i 桁目を, A_j 以降の数字で 2 進表現で k にする総数, としてメモ化再帰すればいい.

メモ化再帰を行うときは, 上の桁から確定させていくと実装が楽である.

計算量は, 桁数をD, 配列の大きさをN とすると, O(DN) となる. 今, 2^50 * 50 が表現できる数の上限であるから, 二進表現での最大の桁数は 56 桁以下であるから D ≦ 56 で, 十分高速であることが分かる.

コード :

#include <bits/stdc++.h>

using namespace std;
typedef long long lint;

class PowersOfTwo {
public:
	long long count(vector<lint>);
};

int n;
lint memo[64][64][2];
vector<lint> v;

lint countIt(int pos, int rem, int bit)
{
	if (pos < 0) return (!bit);
	if (rem < 0) rem = 63;
	
	lint &res = memo[pos][rem][bit];
	if (res >= 0) return (res);
	
	res = 0;
	lint target = bit ? (1ll << pos) : 0;
	int next = rem;
	while (target && next >= 0 && next != 63){
		if (v[next] <= target) target -= v[next];
		next--;
	}
	if (target) return (res = 0);
	res = countIt(pos - 1, next, 0) + countIt(pos - 1, next, 1);
	return (res);
}

long long PowersOfTwo::count(vector<lint> v) {
	sort(v.begin(), v.end());
	::v = v;
	
	n = v.size();
	memset(memo, -1, sizeof(memo));
	
	return (countIt(63, n - 1, 0));
}

03.05.2014 (Wed)

SRM 610 div2

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

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


250 Divided By Zero

できる数は0 から100 までの範囲なので, 適当にiteration すればよし. (ゼロ除算には気をつけましょう)

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

typedef long long lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
const lint INFLL = 1001001001001001001ll;

#define zclear(a) memset((a), 0 ,sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


using namespace std;

class DivideByZero {
public:
	int CountNumbers(vector <int>);
};

int DivideByZero::CountNumbers(vector <int> numbers) {
	
	vector<int> next;
	int fill[128] = {0};
	
	for (int i = 0; i < numbers.size(); i++) fill[numbers[i]] = true;
	for (int i = 0; i < numbers.size(); i++){
		for (int j = i + 1; j < numbers.size(); j++){
			int a = numbers[i], b = numbers[j];
			if (a < b) swap(a, b);
			if (b != 0 && fill[a / b] == 0){
				fill[a / b] = 1;
				numbers.push_back(a / b);
				i = -1;
				break;
			}
		}
	}
	return (numbers.size());
}

550 TheMatrix

市松模様は, (i, j) マスのうちi + j が偶数となるものをひっくり返すと白 or 黒の塊になるのでそうしておくとして, あとは4 次元累積和です. 制約がやや大きいのでO(N^4) は心配ですが間に合います.

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

typedef long long lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
const lint INFLL = 1001001001001001001ll;

#define zclear(a) memset((a), 0 ,sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


using namespace std;

class TheMatrix {
public:
	int MaxArea(vector <string>);
};

int search(int key, vector<string> board)
{
	int cum[128][128] = {0};
	
	for (int i = 0; i < board.size(); i++){
		for (int j = 0; j < board[i].size(); j++){
			if (i) cum[i][j] += cum[i - 1][j];
			if (j) cum[i][j] += cum[i][j - 1];
			if (i && j) cum[i][j] -= cum[i - 1][j - 1];
			cum[i][j] += (board[i][j] == key);
		}
	}
	
	int ret = 0;
	
	for (int i = 0; i < board.size(); i++){
		for (int j = i; j < board.size(); j++){
			for (int k = 0; k < board[i].size(); k++){
				for (int l = k; l < board[i].size(); l++){
					if ((j - i + 1) * (l - k + 1) == cum[j][l] - (i ? cum[i - 1][l] : 0) - (k ? cum[j][k - 1] : 0) + ((i && k) ? cum[i - 1][k - 1] : 0)) ret = max(ret, (j - i + 1) * (l - k + 1));
				}
			}
		}
	}
	return (ret);
}

int TheMatrix::MaxArea(vector <string> board) {
	for (int i = 0; i < board.size(); i++){
		for (int j = 0; j < board[i].size(); j++){
			board[i][j] -= '0';
			if ((i + j) & 1) board[i][j] ^= 1;
		}
	}
	
	return (max(search(1, board), search(0, board)));
}

1000 MiningGoldEasy

dp[何日目][今日のx位置][今日のy位置]でDPをすればいいが, 位置はイベントリストに出てくるものだけを参照すれば十分である.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

class MiningGoldEasy {
public:
	int GetMaximumGold(int, int, vector <int>, vector <int>);
};

vector<int> xs, ys;
vector<int> ex, ey;
int N, M;
int memo[51][52][52];

int calcMax(int day, int px, int py)
{
	if (day == ex.size()) return (0);
	if (memo[day][px][py] >= 0) return (memo[day][px][py]);
	
	int ret = 0;
	
	for (int i = 0; i < xs.size(); i++) ret = max(ret, calcMax(day + 1, i, py));
	for (int i = 0; i < ys.size(); i++) ret = max(ret, calcMax(day + 1, px, i));
	
	return (memo[day][px][py] = ret + N + M - abs(ex[day] - xs[px]) - abs(ey[day] - ys[py]));
}

int MiningGoldEasy::GetMaximumGold(int N, int M, vector <int> event_i, vector <int> event_j) {
	xs.push_back(0); xs.push_back(N);
	ys.push_back(0); ys.push_back(M);
	for (int i = 0; i < event_i.size(); i++) xs.push_back(event_i[i]);
	for (int i = 0; i < event_j.size(); i++) ys.push_back(event_j[i]);
	
	sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
	sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
	
	ex = event_i; ey = event_j;
	
	::N = N, ::M = M;
	
	memset(memo, -1, sizeof(memo));
	
	int ret = 0;
	
	for (int i = 0; i < xs.size(); i++)
		for (int j = 0; j < ys.size(); j++)
			ret = max(ret, calcMax(0, i, j));
	
	return (ret);
}