Hatena::Grouptopcoder

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

 | 

2012-02-18

Codeforces Round #107 (Div. 1) 11:03 Codeforces Round #107 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Round #107 (Div. 1) - nodchipのTopCoder日記 Codeforces Round #107 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

A - Win or Freeze

  • ゲーム木探索・・・?
  • Aでいきなりゲーム木探索っておかしい気がするけど・・・
  • とりあえず書いてみる
  • 次が全部勝ちなら負けで、一つでも負けがあれば勝ち
  • 書けた
  • 最大ケースっぽいのもの一応通った
  • 出してみる
  • Time limit exceeded on test 29
  • orz
  • 他の人は約数の数でやってる・・・
  • 約数の数が2以外なら勝てるのか
  • 以下はPracticeで通したコードです。
int main() {
	std::ios::sync_with_stdio(false);

	ll q;
	cin >> q;
	vector<ll> divisors;
	for (ll divisor = 2; divisor * divisor <= q; ++divisor) {
		while (q % divisor == 0) {
			divisors.push_back(divisor);
			q /= divisor;
		}
	}
	if (q > 1) {
		divisors.push_back(q);
	}

	if (divisors.size() == 2) {
		cout << 2 << endl;
	} else if (divisors.size() <= 1) {
		cout << 1 << endl << 0 << endl;
	} else {
		cout << 1 << endl << divisors[0] * divisors[1] << endl;
	}
}

B - Quantity of Strings

  • これはDPか何かをしなければならないのだろうか
  • 少し考えてみる
  • なんか回文になるケースって殆ど無い気がする
  • kが奇数の場合はababa...というケース以外は部分文字列が回文にならない気がする
  • kが偶数の場合はaaaaa...だけ?
  • あとkが1の時はどんな文字列でもおk
  • kがnの場合は文字列全体が回文になっていれば良いのか
  • k>nの場合はどうだろう・・・
  • 問題で定義されていないから0かな? (<-間違い)
  • 出してみる
  • Wrong answer on pretest 3
  • ううむ
  • 分からない
  • TLによると"Any its substring with length equal to k is a palindrome."の解釈を間違っていたっぽい
  • k>nの場合は回分かどうかを判定する対象が無いと考えれば良いっぽい
  • 以下はPracticeで通したコードです。
int main() {
	std::ios::sync_with_stdio(false);

	ll n, m, k;
	cin >> n >> m >> k;

	if (k == 1 || n < k) {
		ll answer = 1;
		REP(i, n) {
			answer *= m;
			answer %= 1000000007;
		}
		cout << answer << endl;

	} else if (n == k) {
		ll answer = 1;
		REP(i, (n + 1) / 2) {
			answer *= m;
			answer %= 1000000007;
		}
		cout << answer << endl;

	} else if (k % 2 == 0) {
		cout << m << endl;

	} else {
		cout << m * m % 1000000007 << endl;

	}
}

C - Smart Cheater

  • 期待値の計算のところは多分大丈夫だと思う
  • 問題は[a,b)の中で最小の区間を求める部分をlog(n)で求める方法
  • さっぱりわからないorz

D - Mission Impassable

  • 考えていません

E - Freezing with Style

  • 考えていません

Hack

  • Aしか出していないのでAを眺めてみる
  • intでやっている人がいるので撃墜
  • 殆どの人が約数の個数でやってる・・・orz

System Test

x---- +100 1916->1838 紫に降格となってしまいました。みんな頭いいなぁ・・・orz

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20120218
 |