Hatena::Grouptopcoder

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

 | 

2010-07-10

Codeforces Beta Round #23 03:23 Codeforces Beta Round #23 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #23 - nodchipのTopCoder日記 Codeforces Beta Round #23 - nodchipのTopCoder日記 のブックマークコメント

A. You're Given a String...

  • ループ回すだけ・・・?
  • だよね
  • O(N^3)

結果: Accepted

bool check(const string& s, const string& sub) {
	const size_t index = s.find(sub);
	if (index == string::npos) {
		return false;
	}
	if (s.find(sub, index + 1) == string::npos) {
		return false;
	}
	return true;
}

int main() {
	string s;
	getline(cin, s);

	for (int length = s.size(); length >= 0; --length) {
		for (int index = 0; index <= s.size() - length; ++index) {
			const string sub = s.substr(index, length);
			if (check(s, sub)) {
				cout << length << endl;
				return 0;
			}
		}
	}

	cout << 0 << endl;
}

B. Party

  • 状況が全然つかめない
  • とりあえず図を書いてみる
  • たとえば ○-○-○ とつながっていたときはどうだろう
  • 友達0人の人はいなくて、友達1人の人が2人帰って、残った人が友達0人になって・・・
  • 一人残った
  • 多分こういう事らしい
  • さて、最適な組み合わせを考えないと・・・
  • こういう時は特徴的なグラフを考えると相場が決まっている(本当か?)
  • 完全グラフとか、完全グラフから1本抜くとか
  • 完全グラフから1本抜けばいいんじゃね?
  • そんな気がする
  • で、N=1のときは誰も残らないあから、max(0,N-2)とか
  • ・・・本当か?
  • とりあえず書くしか無い

結果: Accepted

int main() {
	int T;
	cin >> T;
	REP(t, T) {
		int N;
		cin >> N;
		cout << max(0, N - 2) << endl;
	}
}

C. Oranges and Apples

  • どうやるんだろう・・・
  • 全然検討がつかない・・・
  • ソートとかするのかなぁ・・・
  • orz

D. Tetragon

  • これ解けるかも
  • 最初の点を座標-10~20の範囲で0.5刻みで回して全探索すればいいんじゃね?
  • 書いてみた
  • TLE
  • 手元で回してみる
  • 全然間に合ってない
  • 計算量でかくね・・・?
  • orz

E. Tree

  • O(N^3)まで許されるらしい
  • メモつき探索かなにかかなぁ・・・
  • でも全然思いつかないorz

結果

#Who=PenaltyABCDE
51nodchip222+00:05+00:17 -2
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100710
 |