Hatena::Grouptopcoder

hotpepsiの練習帳

2011-05-09

SRM 504 Div2

02:40

Easy (250) ComparerInator 比較専用言語

問題

  • 特定の比較演算結果と一致しているなら、1または7を返す
  • 1と7の両方を満たす場合は1を返す
  • 1も7も満たさない場合は-1を返す

はまりポイント

  • 解く速さ優先なら、まとめるよりもコピペして1つずつ確実に判定したほうがよさげ。

実装した内容

  • 演算子毎にカウントする
  • a < bの判断自体は共通なのでまとめる
  • カウントの長さが配列の長さと一致したら、その演算子を満たしたとみなす

https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/ComparerInator.cpp

Medium (500) MathContest 白黒ボール

問題

  • シーケンシャルなキューに白または黒のボールが入っている
  • キューから1つずつボールを取り出す
  • 取り出したボールが白だったらキューの残りのボールの並びを反転する
  • 取り出したボールが黒だったらキューの残りのボールの色を反転する

実装した内容

  • 配列の先頭と最後にポインタを設定しておく
  • 並びが反転したら、読むポインタを変更する
  • 色が反転したら、判定する色を変更する

https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/MathContest.cpp

Hard (1000) Algrid 色塗り

問題

  • 白または黒のセルで構成されたグリッドがある
  • 上の行から下の行に、左から右に向かって処理する
  • ある位置の処理において、上の位置の内容に応じて下の位置を塗る、または交換する

はまりポイント

  • 塗られた部分については、元データがどちらでもよいので、Bとみなす
  • 塗られていない部分については、交換操作を考慮して、元データのどの場所から来ているのかという情報を保持する必要がある

実装した内容

  • 塗るべきところを塗る
  • 交換するところは、ポインタを交換する
  • 塗った部分について、出力データと比較して、不一致なら失敗とする
  • 塗った部分はどちらでもよいので、元データをBとする
  • 塗っていない部分は、出力データからもってくる

https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/Algrid.cpp

結果

今回は問題文が比較的わかりやすかった。

システムのエラーにより残念ながらnon-rated。

時間中にはEasyとMediumを回答し、のちほどチェックしたところEasyはミスっていてMediumはOKだった。

コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20110509

2011-04-17

SRM 503 Div2

03:23

Easy (250) ToastXRaspberry 奇抜なトースト

文章がわかりづらい。

  1. 一度に最大upper_limit層まで塗れる
  2. layer_count層を塗るための最小の塗りの回数

ってこれだけ?

class ToastXRaspberry {
	public:
	int apply(int upper_limit, int layer_count) {
		return (layer_count + upper_limit - 1) / upper_limit;
	}
};

Medium (500) ToastXToast ナイスなトースト

境界条件の理解に時間がかかった。場合わけすると-1と1と2しかない。

焼いた種類のパンについて、必ずovertoastedとundertoastedが存在する、という文章を制約条件だと読んでいなかったため、システムテストに落ちた。汚かったので整理して書き直した。

#include <algorithm>
#include <vector>
using namespace std;
class ToastXToast {
	public:
	int bake(vector <int> undertoasted, vector <int> overtoasted) {
		sort(undertoasted.begin(), undertoasted.end());
		sort(overtoasted.begin(), overtoasted.end());
		if (undertoasted.size() < 1 || overtoasted.size() < 1) {
			return -1;
		}
		if (*undertoasted.rbegin() >= *overtoasted.rbegin() ) {
			return -1;
		}
		if (*undertoasted.begin() >= *overtoasted.begin() ) {
			return -1;
		}
		if (*undertoasted.rbegin() < *overtoasted.begin()) {
			return 1;
		}
		return 2;
	}
};

Hard (900) KingdomXCitiesandVillagesAnother 村を町につなぐ

孤立している村をなくせ。町または、町につながっている村とつなぐための道路を建設せよ。建設すべき道路の最小の合計値を求めよ。

残り15分くらいしかなく、テストのみ書いて終了。終了後、解いた人のソースを見て理解。

  1. 村のうち、最小の長さで町に接続できる村を見つける。
  2. 村と町を接続して、距離の合計値に加算する。
  3. その村を村のリストから削除して、町のリストに追加する。
#include <math.h>
#include <list>
#include <vector>

using namespace std;

struct XY {
	int x;
	int y;
};

typedef vector<int> VI;
typedef list<XY> LXY;

class KingdomXCitiesandVillagesAnother {
	public:
	double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
		LXY cities, villages;
		VI::const_iterator x, y;
		for (x = cityX.begin(), y = cityY.begin(); x != cityX.end(); ++x, ++y) {
			XY city = {*x, *y};
			cities.push_back(city);
		}
		for (x = villageX.begin(), y = villageY.begin(); x != villageX.end(); ++x, ++y) {
			XY village = {*x, *y};
			villages.push_back(village);
		}
		double total = 0.0;
		while (villages.size() > 0) {
			double distance = 0.0;
			LXY::iterator it = findNearestVillage(cities, villages, distance);
			cities.push_back(*it);
			villages.erase(it);
			total += distance;
		}
		return total;
	}
	static LXY::iterator findNearestVillage(const LXY &cities, LXY &villages, double &distance) {
		LXY::iterator nearest = villages.end();
		LXY::iterator village;
		for (village = villages.begin(); village != villages.end(); ++village) {
			LXY::const_iterator city;
			for (city = cities.begin(); city != cities.end(); ++city) {
				double d = getDistance(*city, *village);
				if (nearest == villages.end() || d < distance) {
					nearest = village;
					distance = d;
				}
			}
		}
		return nearest;
	}
	static double getDistance(const XY &a, const XY &b) {
		double x = a.x - b.x;
		double y = a.y - b.y;
		return sqrt(x * x + y * y);
	}
};

結果

ox- 200.98+231.06*0

Easyのみシステムテストに通ってratingが932。Mediumが時間内にきちんと解けるようになりたい。

Hardは30分くらいで解くのはまだきつい感じ。

コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20110417

2011-04-15

SRM 502 Div2

02:05

Easy (250) TheProgrammingContestDivTwo プログラミングコンテスト

N個のタスクが与えられる。それぞれ解くのにrequiredTime[i]の時間かかる。

解くとスコアが1増えてペナルティが経過時間tだけ増える。

T分の間に、スコアの最大値と、そのときのペナルティを返す。

requiredTimeを昇順にソートして加える。

#include <algorithm>
#include <string>
#include <vector>

using namespace std;
typedef vector <int> VI;

class TheProgrammingContestDivTwo {
	public:
	VI find(int T, VI requiredTime) {
		sort(requiredTime.begin(), requiredTime.end());
		int past = 0;
		int solved = 0;
		int penalty = 0;
		VI::const_iterator it;
		for (it = requiredTime.begin(); it != requiredTime.end(); ++it) {
			past += *it;
			if (past > T) {
				break;
			}
			++solved;
			penalty += past;
		}
		VI r;
		r.push_back(solved);
		r.push_back(penalty);
		return r;
	}
};

Medium (500) TheLotteryBothDivs 当たりくじ

9桁の数字のくじがあり、当たりくじのsuffixが与えられるとき、当たる確率を求める。

suffixをprefixと考えても同じなので、suffix文字列を逆順にすることで、suffixをprefixに変換した。

prefixの小さい桁から順番に確率を加えていく。

桁数の小さいprefixは桁数の大きいprefixを含むので、より大きいprefixの中に処理中のprefixを含むものがあれば、無効にする。

#include <algorithm>
#include <string>
#include <vector>
#include <set>

using namespace std;
typedef vector<string> StringVector;
typedef set<string> StringSet;

class TheLotteryBothDivs {
	public:
	double find(vector <string> goodSuffixes) {
		StringSet seq[10];	// use 1 to 9
		StringVector::const_iterator it;
		for (it = goodSuffixes.begin(); it != goodSuffixes.end(); ++it) {
			if (it->length() >= 1 && it->length() <= 9) {
				string s = *it;
				reverse(s.begin(), s.end());
				seq[it->length()].insert(s);
			}
		}

		double result = 0.0;
		double rate = 0.1;
		for (int i = 1; i <= 9; ++i) {
			StringSet::const_iterator it;
			for (it = seq[i].begin(); it != seq[i].end(); ++it) {
				result += rate;
				for (int j = i + 1; j <= 9; ++j) {
					StringSet::iterator temp;
					while (true) {
						temp = seq[j].lower_bound(*it);
						if (temp == seq[j].end() || strncmp(it->c_str(), temp->c_str(), it->length()) != 0) {
							break;
						}
						seq[j].erase(temp);
					}
				}
			}
			rate /= 10.0;
		}

		return result;
	}
};

Hard (1000) TheCowDivTwo 逃げた牛のカウント

0からN-1まで番号がついたN匹の牛のうち、K匹が逃げた。

逃げた牛の番号を合計するとNで割り切れるとき、可能な牛の組み合わせの場合の数を求めよ。

なんかもやもやしてわからなかったので、ぐぐって解法を調べた。

nまでの番号がついた牛が(1～47)匹逃げたときの場合の数を求めておき、(n+1)までの番号がついた牛が逃げたときの場合の数を、そこからの差分で求めていく。

面倒だったのでstaticの二次元配列。

#include <string>
#include <vector>
using namespace std;
class TheCowDivTwo {
	public:
	int find(int N, int K) {
		static int current[47][1024];
		memset(current, 0, sizeof(current));
		current[0][0] = 1;
		for (int n = 0; n < N; ++n) {
			static int prev[47][1024];
			memcpy(prev, current, sizeof(current));
			for (int p = 1; p <= K; ++p) {
				for (int m = 0; m < N; ++m) {
					int mod = (m + n) % N;
					current[p][mod] += prev[p - 1][m];
					current[p][mod] %= 1000000007;
				}
			}
		}
		int result = current[K][0];
		return result;
	}
};
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20110415

2011-04-14

参加

02:03

Google Code Jam勉強会に参加した記念に開始。

最近の話題についていくため、SRMのdiv2を新しい方から順番に解いていこうかと。

言語はほとんどCに近いC++で。

コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20110414
プロフィール

TopCoder参戦記など
TopCoder:hotpepsi
Codeforces:hotpepsi
twitter:@hotpepsi
はてな:firewood

最新タイトル
カテゴリー
リンク集
SRM Div2 Hard
SRM Div1 Medium