Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-12-27

SRM414 DIV2 Level One(250pt.)

| 18:10

http://www.topcoder.com/stat?c=problem_statement&pm=8786&rd=13505

『レストランの来客をある法則のもとに席へ誘導するとき、席につけず帰ってしまう顧客の総数を求めよ。』

英文4行で書かれた法則を理解することに時間がかかりました。特にdeparturesを「何分レストランに滞在するか」だと勘違いしてしまい、5分ほどロス。慣れないC++プログラムということもあり、ノーミスで150ptとなりました。

// 150.36 pt.
#include <vector>
#include <algorithm>
using namespace std;
class RestaurantManager {

	public:
	int allocateTables(vector <int> tableSizes, vector <int> groupSizes, vector <int> arrivals, vector <int> departures) {
		vector<int> tableDepartures;
		tableDepartures.resize(tableSizes.size());
		sort(tableSizes.begin(), tableSizes.end());
		int result = 0;

		for (int i = 0; i < groupSizes.size(); ++i) {
			for (int j = 0; j < tableDepartures.size(); ++j) {
				if (tableDepartures[j] <= arrivals[i]) {
					tableDepartures[j] = 0;
				}
			}

			int found = 0;
			for (int j = 0; j < tableDepartures.size(); ++j) {
				if (tableDepartures[j] == 0 && groupSizes[i] <= tableSizes[j]) {
					tableDepartures[j] = departures[i];
					found = 1;
					break;
				}
			}
			if (not found) {
				result += groupSizes[i];
			}
		}
		return result;
	}
};

2009-12-20

Member SRM455 Level One(250pt.)

| 19:16

http://www.topcoder.com/stat?c=problem_statement&pm=10714&rd=14179

『グリッドの各セルにクモが配置されている。指定された方向にクモが移動したとき、クモがいないセルはいくつ存在するか。』

初めて検索を使わずに書けた気がします。vectorstringを使う上でより効率良くCPUやメモリを使う書き方も存在するとは思いますが、ひとまずSRMを解く上で必要な知識はついてきたと考えてよさそうです。

// 228.20 pt.

#include <string>
#include <vector>
using namespace std;

class SpidersOnTheGrid {
	public:
	int find(vector <string> A) {
		int x, y, count = 0;
		for (y = 0; y < A.size(); ++y) {
			for (x = 0; x < A[y].size(); ++x) {
				if ((y > 0 && A[y - 1][x] == 'S') ||
					(x > 0 && A[y][x - 1] == 'E') ||
					(y < A.size() - 1 && A[y + 1][x] == 'N') ||
					(x < A[y].size() - 1 && A[y][x + 1] == 'W')) {
					//このマスに到達するクモが存在
				} else {
					++count;
				}
			}
		}
		return count;
	}
};

2009-12-13SRM415 DIV2

SRM415 DIV2 Level One(250pt.)

| 20:28

http://www.topcoder.com/stat?c=problem_statement&pm=9978&rd=13506

『N種類の消印(postmarks)が用意されており、あなたはそのうちの数種類を持っているものとする。これらを自由に売買できるとき、最大何種類を揃えることができるか。所持金はゼロとする。』

まずすべての消印を売り払い、安いものから順に買い占めることで解答できます。今回は目立ったひっかけはありませんでした。

// 231.90 pt.

#include <vector>
#include <algorithm>
using namespace std;

class CollectingUsualPostmarks {
	public:
	int numberOfPostmarks(vector <int> prices, vector <int> have) {
		int money = sumOf(prices, have);
		int total = 0;
		sort(prices.begin(), prices.end());

		for (int i = 0; i < prices.size() && prices[i] <= money; ++i) {
			money -= prices[i];
			++total;
		}
		return total;
	}

	private:
	int sumOf(vector <int> prices, vector <int> have) {
		int sum = 0;
		for (int i = 0; i < have.size(); ++i) {
			sum += prices[have[i]];
		}
		return sum;
	}
};

2009-11-22SRM416 DIV2

SRM416 DIV2 Level One(250pt.)

| 10:14

http://www.topcoder.com/stat?c=problem_statement&pm=9905&rd=13507

『与えられた英文の中で最も出現頻度の高い文字を求めよ。複数存在する場合は辞書順に連結して返せ。』

確率について論じられていますが、出現回数を数えるだけで確率まで求める必要はありません。与えられるテキストの長さも短いため、オーバーフローも気にせず解くことができます。

解答にかなり時間を必要としましたが、原因はint配列を初期化せずに使っていたことに気づけなかったこと。暗黙の初期化が行われるJavaとの違いにつまずく形となりました。

なおstringの+演算子による連結がどう実装されているか調べたところ、append関数を呼び出すようオーバーライドされていることを知ることができました。

// 127.94 pt.

#include <string>
#include <vector>
// #include <iostream>
using namespace std;

class MostCommonLetters {
public:
	string listMostCommon(vector<string> text) {
		int counter[26] = {0};	// すべての要素をゼロで初期化
		vector<string>::iterator t_iter;
		for (t_iter = text.begin(); t_iter != text.end(); ++t_iter) {
			string t = *t_iter;
			string::iterator c_iter;
			for (c_iter = t.begin(); c_iter != t.end(); ++c_iter) {
				char c = *c_iter;
				if (c != ' ') {
					++counter[c - 'a'];
				}
			}
		}

		int i, max_count = 0;
		string result;
		for (i = 0; i < 26; ++i) {
			// cerr << counter[i] << endl;
			if (max_count < counter[i]) {
				result = "";
				max_count = counter[i];
			}
			if (max_count == counter[i]) {
				// cout << i << "th string(" << (char)('a' + i) << ") added. max_count is " << max_count << endl;
				result += (char)('a' + i);
			}
		}
		return result;
	}
};

2009-11-15SRM417 DIV2

SRM417 DIV2 Level One(250 pt.)

| 11:40

http://www.topcoder.com/stat?c=problem_statement&pm=9925&rd=13508

『10進数の桁を逆転させる関数Rev(x)を定義し、与えられた2数(x, y)に対しRev(Rev(x)+Rev(y))を求めよ。』

この手の演算では精度の問題がつきまといますが、今回は与えられる数が1〜1000に限られているため気にする必要はありません。問題にかかれている通り、Rev(x)を定義して呼び出すだけです。

// 246.58 pt.

class ReversedSum {
public:
	int getReversedSum(int x, int y) {
		return rev(rev(x) + rev(y));
	}

private:
	int rev(int source) {
		int result = 0;
		while (source != 0) {
			int tail = source % 10;
			result = result * 10 + tail;
			source /= 10;
		}
		return result;
	}
};