Hatena::Grouptopcoder

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

 | 

2014-04-19

AtCoder Beginner Contest #007 23:05 AtCoder Beginner Contest #007 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Beginner Contest #007 - nodchipのTopCoder日記 AtCoder Beginner Contest #007 - nodchipのTopCoder日記 のブックマークコメント

A - 植木算

  • 1引く
int main() {
	std::ios::sync_with_stdio(false);

	int n;
	cin >> n;
	cout << n - 1 << endl;
}

B - 辞書式順序

  • "a"なら-1、そうでないなら"a"
int main() {
	std::ios::sync_with_stdio(false);

	string s;
	cin >> s;
	if (s == "a") {
		cout << -1 << endl;
	}
	else {
		cout << "a" << endl;
	}
}

C - 幅優先探索

  • 幅優先探索する
int DX[] = { 0, 0, 1, -1 };
int DY[] = { 1, -1, 0, 0 };
int main() {
	std::ios::sync_with_stdio(false);

	int R, C, sy, sx, gy, gx;
	cin >> R >> C >> sy >> sx >> gy >> gx;

	vector<string> maze;
	REP(y, R) {
		string row;
		cin >> row;
		maze.push_back(row);
	}

	int memo[64][64];
	fill_n((int*)memo, sizeof(memo) / sizeof(memo[0][0]), INT_MAX);
	memo[sx - 1][sy - 1] = 0;
	queue<int> q;
	q.push(sx - 1);
	q.push(sy - 1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		int y = q.front();
		q.pop();

		REP(dir, 4) {
			int xx = x + DX[dir];
			int yy = y + DY[dir];
			if (maze[yy][xx] == '#') {
				continue;
			}
			if (memo[xx][yy] != INT_MAX) {
				continue;
			}

			memo[xx][yy] = memo[x][y] + 1;
			q.push(xx);
			q.push(yy);
		}
	}

	cout << memo[gx - 1][gy - 1] << endl;
}

D - 禁止された数字

  • DP
  • f(x)を0~xまでに含まれる禁止された数字の数を関数として、f(B)-f(A-1)をすればよいはず
  • f(x)の中身は再帰的に上の桁から数を数えていく感じ
  • 再帰の途中でメモれるところをメモっていけばメモ探になるはず(?)
  • とりあえずかけた
  • Submit
  • WA
  • うむむ・・・
  • naiveなものを書いて比較してみる
  • ・・・
  • だいぶ違う・・・
  • いろいろ直してみる
  • 直った
  • naiveなものと結果が一致したっぽい
  • Submit
  • AC
  • 算数DPホント苦手・・・orz
ll dp[32];
ll tens[32];
ll dfs(const string& number, int digit, bool matched) {
	if (number.size() == digit) {
		return 0;
	}

	if (matched) {
		ll result = 0;
		for (int i = 0; i <= number[digit] - '0'; ++i) {
			if (i == 4 || i == 9) {
				if (i == number[digit] - '0') {
					if (digit + 1 < number.size()) {
						istringstream iss(number.substr(digit + 1));
						ll n;
						iss >> n;
						result += n + 1;
					} else {
						++result;
					}
				}
				else {
					result += tens[digit];
				}
			}
			else {
				result += dfs(number, digit + 1, i == number[digit] - '0');
			}
		}
		return result;
	}
	else {
		if (dp[digit] != -1) {
			return dp[digit];
		}

		ll result = 0;
		for (int i = 0; i < 10; ++i) {
			if (i == 4 || i == 9) {
				result += tens[digit];
			}
			else {
				result += dfs(number, digit + 1, false);
			}
		}

		return dp[digit] = result;
	}
}


int main() {
	std::ios::sync_with_stdio(false);
	
	//for (int fileIndex = 4; fileIndex < 30; ++fileIndex) {
	//	int A = rand() % 100 + 1;
	//	int B = rand() % 100 + 1;
	//	if (A > B) {
	//		swap(A, B);
	//	}
	//	char filename[64];
	//	sprintf(filename, "abc007_4.%d.in.txt", fileIndex);
	//	ofstream ofs(filename);
	//	ofs << A << " " << B << endl;

	//	int answer = 0;
	//	for (int i = A; i <= B; ++i) {
	//		ostringstream oss;
	//		oss << i;
	//		string s = oss.str();
	//		if (s.find('4') != string::npos || s.find('9') != string::npos) {
	//			++answer;
	//		}
	//	}

	//	sprintf(filename, "abc007_4.%d.out.txt", fileIndex);
	//	ofstream ofs2(filename);
	//	ofs2 << answer << endl;
	//}

	//return 0;

	//int A, B;
	//cin >> A >> B;
	//int answer = 0;
	//for (int i = A; i <= B; ++i) {
	//	ostringstream oss;
	//	oss << i;
	//	string s = oss.str();
	//	if (s.find('4') != string::npos || s.find('9') != string::npos) {
	//		++answer;
	//	}
	//}

	//cout << answer << endl;

	tens[18] = 1;
	for (int i = 17; i >= 0; --i) {
		tens[i] = tens[i + 1] * 10;
	}

	fill_n(dp, sizeof(dp) / sizeof(dp[0]), -1);

	ll a;
	string A, B;
	cin >> a >> B;
	--a;
	ostringstream oss;
	oss << a;
	A = oss.str();
	while (A.size() < 19) {
		A = "0" + A;
	}
	while (B.size() < 19) {
		B = "0" + B;
	}
	ll bb = dfs(B, 0, true);
	ll aa = dfs(A, 0, true);
	cout << bb - aa << endl;
}

結果

順位ユーザ名植木算辞書式順序幅優先探索禁止された数字得点 / Total
23nodchip 100 00:32100 01:30100 06:41100 (2) 57:43400 (2) 67:43
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140419
 |