Hatena::Grouptopcoder

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

 | 

2012-01-22

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

A. Lucky Conversion

  • ええっと・・・
  • 10^5以下の数字しか来ないから全探索でいいよね <- 間違い
  • 賢い方法がとっさに思いつかないのでとりあえず幅優先
  • Submit -> Time limit exceeded on pretest 6
  • なぬー!
  • 問題をよく見なおしてみる
  • 10^5「桁」以下の数字・・・
  • orz
  • 賢い方法を考えてみる
  • 変更する数字の個数だけ見れば良いのかな
  • 4->7 7->4に変更する場合はスワップして、それ以外は書き換えればいいのね
  • orz
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);
	string a, b;
	cin >> a >> b;

	int fourToSeven = 0;
	int sevenToFour = 0;
	REP(i, a.size()) {
		if (a[i] == '4' && b[i] == '7') {
			++fourToSeven;
		} else if (a[i] == '7' && b[i] == '4') {
			++sevenToFour;
		}
	}

	int swap = min(fourToSeven, sevenToFour);
	cout << fourToSeven + sevenToFour - swap << endl;
}

B. Lucky Number 2

  • これめんどくね・・・?
  • CodeForcesお得意の場合分け失敗で即死ゲー
  • 多分賢くやると残りの数字の個数で場合分けしてすんなり書けたりするんだろうなぁ
  • とりあえず紙に書き出してみる
  • 474747...47と繰り返す場合と747474...74と繰り返す場合があるらしい
  • どちらを選べばよいか入力で場合分けする感じかな
  • 最後に4444...44か7777...77を挿入してあげれば良さそう
  • とりあえず書いてみる
  • 場合分けに自信が無いのでテストケースを十数個くらい追加
  • テストしてみる
  • ・・・
  • 全く通らないorz
  • 修正しても通らないorz
  • ・・・
  • 通った
  • Submit -> Accepted
void solve(int a4, int a7, int a47, int a74, char first) {
	vector<char> s;
	s.push_back(first);
	int count47 = 0;
	int count74 = 0;
	while (true) {
		if (s.back() == '4') {
			if (count47 == a47) {
				break;
			}
			s.push_back('7');
			++count47;
		} else {
			if (count74 == a74) {
				break;
			}
			s.push_back('4');
			++count74;
		}
	}

	if (count47 != a47 || count74 != a74) {
		return;
	}

	a4 -= count(ALL(s), '4');
	a7 -= count(ALL(s), '7');

	if (a4 < 0 || a7 < 0) {
		return;
	}

	vector<char>::iterator it4 = find(ALL(s), '4');
	s.insert(it4, a4, '4');
	vector<char>::iterator it7 = find(s.rbegin(), s.rend(), '7').base();
	s.insert(it7, a7, '7');
	cout << string(ALL(s)) << endl;
	exit(0);
}

int main() {
	std::ios::sync_with_stdio(false);

	int a4, a7, a47, a74;
	cin >> a4 >> a7 >> a47 >> a74;

	if (!a47 && !a74) {
		if (a4 && !a7) {
			cout << string(a4, 'a4') << endl;
			return 0;
		} else if (!a4 && a7) {
			cout << string(a7, 'a7') << endl;
			return 0;
		}
	}

	solve(a4, a7, a47, a74, '4');
	solve(a4, a7, a47, a74, '7');
	cout << -1 << endl;
}

C. Lucky Subsequence

  • ラッキーナンバー以外は全て独立に扱って良いのは分かる
  • これは{}_{n}C_{k}で計算できそう
  • 同じラッキーナンバーはまとめて処理するっぽい
  • こっちがよく分からない・・・
  • O(N^2)なら解けるけどTLEするし・・・
  • パス

D. Lucky Pair

  • 読んでいません

E. Lucky Queries

  • 読んでいません

Hack

  • Bのコーナーケースを狙ってみる
  • ・・・
  • この人0の場合の処理書いてない
  • Hack -> Invalid input
  • あ・・・0はInvalidっぽいorz
  • ・・・
  • この人 "1 2 1 1" -> "747" の時の場合分けできてない
  • Hack -> Successful hacking attempt
  • この人は "2 3 2 1" -> "47477" の時、7を手前につけちゃってる
  • Hack -> Successful hacking attempt
  • この人は何かよく分からないけど場合分けが抜けてる気がする <- 落ち着け
  • Hack -> Unsuccessful hacking attempt
  • +2 -1 で終了

System Test

#Who=ABCDE
109nodchip1356+2 : -1422 00:14784 00:54

1846->1912 Candidate master(紫)からMaster(黄色)に昇格しました。当面の目標は黄色の維持です。

ゲスト



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