TopCoder Memo@kagamiz

SRM 610 div2

Practice | 21:45 |

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

ツイートする