TopCoder SRM 523 DIV2

Rating: 1143(緑)→1156(緑)

いろいろとしくじった。Challenge大荒れの回だった。

229.78 Point

250: AlphabetPath

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class AlphabetPath {
private:
	bool isValid(int x, int y, vector<string>& maze) {
		return 0 <= x && x < maze.size() && 0 <= y && y < maze[0].size();
	}

public:
	string doesItExist(vector <string> letterMaze) {
		int sx = -1, sy;

		for (int i = 0; i < letterMaze.size(); ++i) {
			for (int j = 0; j < letterMaze[i].size(); ++j) {
				if (letterMaze[i][j] == 'A') {
					sx = i, sy = j;
					break;
				}
			}
			if (sx != -1)
				break;
		}

		const int dx[] = {1, 0, -1, 0},
		      	  dy[] = {0, 1, 0, -1};

		int cx = sx, cy = sy;

		bool f = true;

		for (int i = 'B'; i <= 'Z'; ++i) {
			bool g = false;

			for (int j = 0; j < 4; ++j) {
				const int nx = cx + dx[j], ny = cy + dy[j];
				if (!isValid(nx, ny, letterMaze))
					continue;
				if (letterMaze[nx][ny] == i) {
					g = true;
					cx = nx, cy = ny;
					break;
				}
			}
			if (!g) {
				f = false;
				break;
			}
		}

		return string(f ? "YES" : "NO");
	}
};

229.78 Point

2次元平面上に並ぶABCD....ZをAからはじめて隣接するマスを辿って順にZまでいけるかどうかを判定しろという問題。
問題をざっと聞いただけで分かると思うが、どう聞いても実装が重い。250の実装量では絶対ない。450ぐらいが妥当ではないだろうか。

500: CountingSeries

(あとでACした人のソースをチラチラ見ながら書いたソース)

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class CountingSeries {
	public:
	long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
		long long res = 0;

		if (a <= upperBound)
			res += (upperBound - a) / b + 1;

		for (long long y = c; y <= upperBound; y *= d, y = (d == 1 ? upperBound + 1 : y)) {
			if ((y - a) % b || y < a)
				res++;
		}
		return res;
	}
};

結論から言えばチャレンジされた。

全般的に今回の一大反省を要する問題。問題文の条件をそもそも大誤読した上に、グラフを描かない悪癖がたたって、脳内で謬論に基く実装が出来上がってしまい、しかもそれが非常に重かった。実装が終わりかけた頃にこれでは解けないというのに気付いて、ついでに問題文を再び誤読して、絶対にTLEする解法を送った。正直ねぼけていたという事にしたい。

1000:

時間なかった