Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2009-10-26

IEEEXtreme 3.0 12:32 IEEEXtreme 3.0 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - IEEEXtreme 3.0 - nodchipのTopCoder日記 IEEEXtreme 3.0 - nodchipのTopCoder日記 のブックマークコメント

IEEEXtreme 3.0の参加記録です。

Problem 1A : Himalayas

東の無限遠から西にある山脈を見る。各山の傾斜は200%である。各山の頂点の(x,y,z)座標が与えられる。Skylineをなす山頂を列挙せよ。

実装するだけなのですが、緯度と標高が同じ山の処理を間違えてWAをもらいまくってしまいました。

struct M
{
	ll x, y, z;
	string name;
	bool operator<(const M& rh) const
	{
		if (x != rh.x) {
			return x < rh.x;
		}
		if (y != rh.y) {
			return y < rh.y;
		}
		if (z != rh.z) {
			return z < rh.z;
		}
		return name < rh.name;
	}
};

ll myabs(ll a)
{
	if (a < 0) {
		a *= -1;
	}
	return a;
}

int main()
{
	int N;
	cin >> N;
	vector<M> ms;
	for (int i = 0; i < N; ++i) {
		M m;
		cin >> m.name >> m.x >> m.y >> m.z;
		ms.push_back(m);
	}

	sort(ms.begin(), ms.end());

	for (int i = 0; i < N; ++i) {
		const M& from = ms[i];
		bool hidden = false;
		for (int j = 0; j < N && !hidden; ++j) {
			if (i == j) {
				continue;
			}
			const M& to = ms[j];
			if (from.x == to.x && from.z == to.z) {
				if (from.y > to.y) {
					hidden = true;
				}
			} else if (from.z <= to.z - myabs(from.x - to.x) * 2) {
				hidden = true;
			}
		}

		if (!hidden) {
			cout << from.name << endl;
		}
	}
}

Problem 1B : Vangelis

1 <= X <= 10 ^ 9, 1 <= A <= B <= 10 ^ 9 と、使用可能な数字の集合が与えられる。A <= x <= B かつ x mod X == 0 かつ x の各桁が使用可能な数字の集合に含まれるような x の個数を求めよ。

全探索だとX = 1, A = 1, B = 10 ^ 9, D = 1234567890 の場合に計算量が100億となって危ないと思っていたのですが、下位チームが続々解いているのを見てテストケースが甘いのではないかと思い、ためしに送ったら通ってしまいました。

int main()
{
	int X, A, B;
	cin >> X >> A >> B;
	char c;
	bool flag[10];
	memset(flag, 0, sizeof(flag));
	while (cin >> c) {
		flag[c - '0'] = true;
	}

	int answer = 0;
	for (int i = (A + X - 1) / X * X; i <= B; i += X) {
		int ii = i;
		bool ok = true;
		do {
			if (!flag[ii % 10]) {
				ok = false;
			}
			ii /= 10;
		} while (ii && ok);
		if (ok) {
			++answer;
		}
	}
	cout << answer << endl;
}

Problem 1C : Cube

単位立方体を敷き詰めた空間がある。1ステップ毎に隣接する隣の立方体に移動することが出来る。Kステップ後に行くことの出来る立方体の個数を求めよ。

実際の例で考えて見ます。K = 4 の場合は 1 + 4 + 9 + 16 + 25 + 16 + 9 + 4 + 1 です。これをそのまま書けば終わりです。

int main()
{
	ll K;
	cin >> K;

	ll answer = 0;

	for (ll n = 0; n < K; ++n) {
		answer += 2 * (n + 1) * (n + 1);
	}
	answer += (K + 1) * (K + 1);

	cout << answer << endl;
}

Problem 1D : Maze Keys

二次元迷路上に鍵(<=5個)と扉(<=5個)が置かれている。鍵は一度扉を開くと使えなくなる。ゴールまでの最短歩数を求めよ。

使用した鍵と開いた扉とオブジェクトの位置を持たせたダイクストラです。他のチームメンバーが通しました。

Problem 1E : Mobile Primes

数字Nの部分文字列からなる数の集合を考える。各桁数の素数がそれぞれ何個あるか求めよ。Leading zeroは含めない。

書くだけの問題だと思っていたのですが、Leading Zeroの条件を見落としていて自力で通せませんでした。他のチームメンバーが通しました。

Problem 1F : Olympic City

オリンピック開催地を決める選挙シミュレーションせよ。

タイムリーですね。選挙系実装問題です。他のチームメンバーが通しました。

Problem 1G : Police

内容は知りませんがBFSをするだけだそうです。他のチームメンバーが通しました。

Problem 1H : Dice

D個のサイコロを同時に振り、出た目の合計がN以上となる確率を分数で求めよ。

典型的なDP問題です。他のチームメンバーが通しました。

Problem 1I : Proctoring

内容は知りませんがBFSをするだけだそうです。他のチームメンバーが通しました。

Problem 1J : Xtrebble

"a"から"z"までの文字パネルと"J"というジョーカーパネルがある。N人のプレイヤーがそれぞれ1枚以上の文字パネルを持っている。"a"から"z"までの文字にはそれぞれ価値が与えられている。書くプレイヤーがおのおのの持っている文字パネル全てを使って与えられた辞書の中の単語の一つを作るとき、文字の価値の和が最大になる単語を求めよ。ジョーカーパネルはどの文字にもマッチする。

単純な実装問題だと思っていたのですがWAで自力では通せませんでした。他のチームメンバーが通しました。

Problem 1K : The Return of the Focus List

昨年度出題された問題の続編。ワイルドカード形式のフィルタリング文字列csv形式のデータが与えられる。Nameの項目をフィルタリングしつつ、指定された形式でデータを出力せよ。

20個くらいWAを出したのですが自動JudgeにはAcceptedがもらえませんでした。その後Clarで浮動小数の出力の仕方が間違っているのではないかと小一時間くらい問い詰めたところ、Judge側がSample Outputの誤りを認め、提出したソースをおまけでACしてくれました。

Problem 1L : Quality

Mineral Waterというプログラミング問題のスコアリングを行う。この問題はN個のテストケースからなる。各テストケースにおける各サブミットのスコアリングは以下のように行う。初めに各サブミットを得点の良い順に並べる。サブミットの数が10以上の場合は、一番良いサブミットに10点を与える。続く (t-1) div 9 個毎に9点、8点、7点、と与えていく。最後の (t-1) div 9 + (t-1) mod 9 個のサブミットには1点を与える。サブミットの数が10未満の場合は得点の高い順に10点、9点、8点・・・と与えていく。ただし、いずれの場合も、スコアが変化する部分で得点が同じ場合には、低い方のスコアを高い方のスコアに合わせるようにする。最終的なスコアの高い順に出力せよ。

実装問題です。素直に書けばよいと思います。ちなみに Problem 2A への伏線です。

struct TEST
{
	int score;
	string name;
	int lastScore;
	bool operator<(const TEST& rh) const
	{
		return score > rh.score;
	}
};

int main()
{
	int N;
	cin >> N;
	vector<vector<TEST> > testss(N);
	string name;
	int testCase, score;
	while (cin >> name >> testCase >> score) {
		--testCase;
		TEST test;
		test.name = name;
		test.score = score;
		testss[testCase].push_back(test);
	}

	for (vector<vector<TEST> >::iterator it = testss.begin(); it != testss.end(); ++it) {
		sort(it->begin(), it->end());

		vector<TEST>& tests = *it;

		if (tests.size() > 10) {
			for (int i = 0; i < (int)tests.size(); ++i) {
				tests[i].lastScore = 1;
			}

			tests[0].lastScore = 10;
			const int k = (tests.size() - 1) / 9;
			int index = 1;
			for (int lastScore = 9; lastScore >= 1; --lastScore) {
				for (int i = 0; i < k; ++i) {
					tests[index++].lastScore = lastScore;
				}
			}
		} else {
			for (int i = 0; i < (int)tests.size(); ++i) {
				tests[i].lastScore = 10 - i;
			}
		}

		for (int i = 1; i < (int)tests.size(); ++i) {
			if (tests[i].score == tests[i - 1].score) {
				tests[i].lastScore = tests[i - 1].lastScore;
			}
		}
	}

	map<string, int> result;
	for (vector<vector<TEST> >::iterator it = testss.begin(); it != testss.end(); ++it) {
		for (vector<TEST>::iterator jt = it->begin(); jt != it->end(); ++jt) {
			result[jt->name] -= jt->lastScore;
		}
	}

	multiset<pair<int, string> > sorted;
	for (map<string, int>::iterator it = result.begin(); it != result.end(); ++it) {
		sorted.insert(make_pair(it->second, it->first));
	}

	for (multiset<pair<int, string> >::iterator it = sorted.begin(); it != sorted.end(); ++it) {
		cout << it->second << " " << -it->first << endl;
	}
}

Problem 2A : Mineral Water

二次元格子上の各点にスコアが割り当てられている。半径が与えられる円N個 (3 <= N <= 50) を配置していく。円の内部のスコアの話が全体のスコアとなる。なるべく高いスコアを出力せよ。サブミットの相対評価は Problem 1L に基づいて行われる。

はやくも伏線回収です。この手の問題は焼きなまし法が鉄板となっていると思いますので、素直に実装してみます。まず円をランダムに配置します。続いてランダムに円を1つ選び、別のランダムに選んだ場所に配置し直すという手順を繰り返します。この時、再配置前と後でスコアが高くなるかちょっとだけ悪くなった場合は再配置を受理し、それ以外の場合は棄却します。これを5分くらい続けてよい配置になることを願います。

ype

Problem 2B : Cookies recipe

"a"から"j"までの文字を使って文字列を作る。以下の関数の評価がなるべく大きくなるような文字列を作れ。

数学的な解法がありそうな気がするのですが、全く思いつかず、焼きなましで作ってしまいました。こちらの焼きなましでは長めのランダムな文字列を作った後、スコアが取れるように変化させ、スコアが取れたら1文字削り、以下繰り返しという形になっています。最終的には170点くらいの文字列が作れました。

int hash(char vec[6]) {
	int sorted[6];
	int i,j,k,s;

	for (i=0; i<6; sorted[k] = vec[i++]-'a')
		for (k=j=0; j<6; ++j)
			if (i!=j && vec[i]==vec[j]) return 0;
			else	k += vec[i]<vec[j];
	for (s=i=0; i<5; ++i) s = 10*s+sorted[i];

	return s;
}

main() {
	char	c;
	char	last5[6]={'@','@','@','@','@','@'};
	int	num_appear=0, hash_appear[100000];
	int	i,i5=0;

	for (i=0; i<100000; ++i) hash_appear[i]=!i;
	for (i=0; i<500 && (c=getchar()) <= 'j' && c>='a'; ++i) {
		last5[i5] = c;
		i5 = (i5+1)%5;
		num_appear += !hash_appear[hash(last5)]++;

	}

	return (num_appear<252) ? 0 : 500-i;

}
rgy == -

Problem 2C : Math Exercise

与えられた7桁の数字に自由に演算子を挿入する。100という数が作れ。

第一回天下一プログラマー予選第2回の問題にそっくりです。他のチームメンバーが解きました。

Problem 2D : Problem 2D : VHDL

10個の要素からなる数列の部分数列の和の最大値を求める論理回路VHDLを用いて合成せよ。

言語限定問題です。VHDLとか来ないといいなぁと思っていたら来てしまいました。チームメンバーがたまたま持っていたCのソースコードを、同期代入とステートマシンを使って書き直して解きました。実は数値演算ライブラリは使ってはいけなかったようで、以下のコードはレギュレーション違反となります。加算演算器と比較演算器を作れば通ると思います。

library ieee;
	use ieee.numeric_std.all;
	use ieee.std_logic_1164.all;
	--use std.textio.all;

entity MaxSeqSum is
port (
	clock : in STD_LOGIC;
	sreset : in STD_LOGIC;
	input_valid : in STD_LOGIC;
	value_1 : in STD_LOGIC_VECTOR (31 downto 0);
	value_2 : in STD_LOGIC_VECTOR (31 downto 0);
	value_3 : in STD_LOGIC_VECTOR (31 downto 0);
	value_4 : in STD_LOGIC_VECTOR (31 downto 0);
	value_5 : in STD_LOGIC_VECTOR (31 downto 0);
	value_6 : in STD_LOGIC_VECTOR (31 downto 0);
	value_7 : in STD_LOGIC_VECTOR (31 downto 0);
	value_8 : in STD_LOGIC_VECTOR (31 downto 0);
	value_9 : in STD_LOGIC_VECTOR (31 downto 0);
	value_10 : in STD_LOGIC_VECTOR (31 downto 0);
	idle : out STD_LOGIC;
	output_valid : out STD_LOGIC;
max_sum : out STD_LOGIC_VECTOR (31 downto 0)
);
end MaxSeqSum;

architecture MaxSeqSumBody of MaxSeqSum is

component MaxSeqSum
port (
	clock : in STD_LOGIC;
	sreset : in STD_LOGIC;
	input_valid : in STD_LOGIC;
	value_1 : in STD_LOGIC_VECTOR (31 downto 0);
	value_2 : in STD_LOGIC_VECTOR (31 downto 0);
	value_3 : in STD_LOGIC_VECTOR (31 downto 0);
	value_4 : in STD_LOGIC_VECTOR (31 downto 0);
	value_5 : in STD_LOGIC_VECTOR (31 downto 0);
	value_6 : in STD_LOGIC_VECTOR (31 downto 0);
	value_7 : in STD_LOGIC_VECTOR (31 downto 0);
	value_8 : in STD_LOGIC_VECTOR (31 downto 0);
	value_9 : in STD_LOGIC_VECTOR (31 downto 0);
	value_10 : in STD_LOGIC_VECTOR (31 downto 0);
	idle : out STD_LOGIC;
	output_valid : out STD_LOGIC;
max_sum : out STD_LOGIC_VECTOR (31 downto 0)
);
end component;

signal state : integer;
signal s0,s1,s2,s3,s4,s5,s6,s7,s8,s9 : integer;
signal t, s, min : integer;
signal result_ : integer;

begin
	process(clock, sreset)
		variable result : integer;
	begin
		if clock'event and clock = '1' then
			if sreset = '1' then
				state <= 0;
				idle <= '1';
				output_valid <= '0';
				max_sum <= "00000000000000000000000000000000";

			elsif input_valid = '1' then
				--report "input_valid=1";
				state <= 1;
				s0 <= to_integer(signed(value_1));
				s1 <= to_integer(signed(value_2));
				s2 <= to_integer(signed(value_3));
				s3 <= to_integer(signed(value_4));
				s4 <= to_integer(signed(value_5));
				s5 <= to_integer(signed(value_6));
				s6 <= to_integer(signed(value_7));
				s7 <= to_integer(signed(value_8));
				s8 <= to_integer(signed(value_9));
				s9 <= to_integer(signed(value_10));
				t <= 0;
				s <= 0;
				idle <= '0';
				min <= 0;
				output_valid <= '0';
				
			elsif state = 1 then
				state <= 2;
				if (t + s0 > 0) then t <= t + s0; else t <= 0; end if;
				if (s0 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 2 then
				state <= 3;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 3 then
				state <= 4;
				if (t + s1 > 0) then t <= t + s1; else t <= 0; end if;
				if (s1 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 4 then
				state <= 5;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 5 then
				state <= 6;
				if (t + s2 > 0) then t <= t + s2; else t <= 0; end if;
				if (s2 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 6 then
				state <= 7;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 7 then
				state <= 8;
				if (t + s3 > 0) then t <= t + s3; else t <= 0; end if;
				if (s3 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 8 then
				state <= 9;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 9 then
				state <= 10;
				if (t + s4 > 0) then t <= t + s4; else t <= 0; end if;
				if (s4 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 10 then
				state <= 11;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 11 then
				state <= 12;
				if (t + s5 > 0) then t <= t + s5; else t <= 0; end if;
				if (s5 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 12 then
				state <= 13;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 13 then
				state <= 14;
				if (t + s6 > 0) then t <= t + s6; else t <= 0; end if;
				if (s6 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 14 then
				state <= 15;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 15 then
				state <= 16;
				if (t + s7 > 0) then t <= t + s7; else t <= 0; end if;
				if (s7 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 16 then
				state <= 17;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 17 then
				state <= 18;
				if (t + s8 > 0) then t <= t + s8; else t <= 0; end if;
				if (s8 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 18 then
				state <= 19;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 19 then
				state <= 20;
				if (t + s9 > 0) then t <= t + s9; else t <= 0; end if;
				if (s9 < min) then min <= s0; else min <= min; end if;
				idle <= '0';
				output_valid <= '0';
			elsif state = 20 then
				state <= 21;
				if (s < t) then s <= t; else s <= s; end if;
				idle <= '0';
				output_valid <= '0';

			elsif state = 21 then
				state <= 22;
				if (s = 0) then
					result := min;
				else
					result := s;
				end if;
				result_ <= result;
				max_sum <= std_logic_vector(to_signed(result, 32));
				--report integer'image(result);
				idle <= '0';
				output_valid <= '0';
				
			elsif state = 22 then
				state <= 23;
				idle <= '0';
				output_valid <= '1';
				max_sum <= std_logic_vector(to_signed(result_, 32));

			elsif state = 23 then
				state <= 0;
				idle <= '1';
				output_valid <= '0';
				max_sum <= "00000000000000000000000000000000";

			end if;
		end if;
	end process;
end MaxSeqSumBody;

総評

  • 強いチームがあまりいなかった
  • 英語が読みにくかった
  • ランキングが二つのコンテストにまたがって表示されているため、見づらかった
  • Clarの返答が誤字脱字だらけで意味が取れない場合があった
  • 単純実装が多かった
  • Mooshakの使い勝手はまぁまぁ
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20091026
 |