SRM 330 Div.1

250(Easy) : 문제 링크

System> hongjun7 has submitted the 250-point problem for 242.56 points

class Arrows {
	public:
	int longestArrow(string s) {
		int res = -1;
		int n = s.size();
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (s[i] == '<') {
					int ok = 1;
					for (int k = i + 1; k <= j; k++) if (s[k] != s[i + 1]) ok = 0;
					if (ok) {
						if (i + 1 > j || s[i + 1] == '-' || s[i + 1] == '=') res = max(res, j - i + 1);
					}
				}
				if (s[j] == '>') {
					int ok = 1;
					for (int k = i; k < j; k++) if (s[k] != s[j - 1]) ok = 0;
					if (ok) {
						if (i > j - 1 || s[j - 1] == '-' || s[j - 1] == '=') res = max(res, j - i + 1);
					}
				}
			}
		}
		return res;
	}
};

500(Medium) : 문제 링크

문제를 요약하면 다음과 같다. prefix-free set을 집합의 모든 두 원소 쌍 중 어느 하나가 다른 하나의 prefix가 되지 않는 것으로 정의한다. 이 때, string set이 주어지면 그 set에서 prefix-free set을 찾는 것이 문제의 요구사항이다. string set의 크기는 50개 이하이며, 각 string의 길이도 50이하이다.

문제를 보고 트라이(trie)를 떠올리는데 5분 정도가 소요되었다.

트라이를 떠올리고도 counting하는 방법에 대해서 15분 정도 고민했었다. 결론부터 얘기하면, 트라이의 어떤 노드 x에 대해서 자식도드들 y_i들이 있을 때에 y_i들의 부트리에 대한 답들을 +1한 걸 다 곱한 후 -1하면 공집합을 제외한 걔네들끼리의 모든 prefix-free set의 개수가 된다. 왜냐하면 최초의 공통 조상이 x인데, x를 제외하면 prefix가 성립되지 않으니까. 여기다가 x_i가 finishing node(string의 끝)이면 +1해주면 된다. 주의할 점으로 문제에서 공집합도 prefix-free set으로 간주한다고 했으니까 트라이의 슈퍼노드도 finishing node라고 해주면 된다.

System> hongjun7 has submitted the 500-point problem for 248.81 points

int n, m;
int d[2555][26], fin[2555];
class PrefixFreeSubsets {
public:
	long long go(int x) {
		int cnt = 0;
		long long a = 1;
		for (int i = 0; i < 26; i++) {
			if (d[x][i] != -1) {
				++cnt;
				long long y = go(d[x][i]);
				a *= (y + 1);
			}
		}
		return (fin[x] == 1) + a - 1;
	}
	long long cantPrefFreeSubsets(vector <string> words) {
		n = words.size();
		memset(d, -1, sizeof(d));
		long long res = 0;
		for (int i = 0; i < n; i++) {
			string s = words[i]; int sn = s.size(); int p = 0;
			for (int j = 0; j < sn; j++) {
				int x = s[j] - 'a';
				if (d[p][x] == -1) {
					++m;
					d[p][x] = m;
				}
				p = d[p][x];
			}
			fin[p] = 1; //no duplicate
		}
		fin[0] = 1;
		res = go(0);
		return res;
	}
};

1000(Hard) : 문제 링크

System> hongjun7 has submitted the 1000-point problem for 664.67 points

int N, x[22], res, K;
bool d[4000005];
class LongLongNim {
public:
	int solve(int M, vector <int> x) {
		memset(d, 0, sizeof(d));
		res = 0;
		N = M; K = x.size();
		if (N > 1e6) {
			N = 1e6;
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j < K; j++) {
					if (i >= x[j]) {
						if (d[i - x[j]] == 0) d[i] = 1;
					}
				}
			}
			int p = 1e6;
			for (int i = 1; i <= p; i++) {
				if ((p - i + 1) & 1) continue;
				int r = (p - i + 1) / 2;
				bool ok = 1;
				for (int k = i; k < i + r; k++) if (d[k] != d[k + r]) { ok = 0; break; }
				if (ok) {
					int c = 0;
					for (int k = p + 1; k <= N; k++) {
						if (d[k] != d[i + c]) { ok = 0; break; }
						c++;
						if (c == r) c = 0;
					}
					if (ok) {
						for (int k = 1; k < i; k++) res += (d[k] == 0);
						for (int k = 0; k < r; k++) res += (d[i + k] == 0)*((M - i - k) / r + 1);
						return res;
					}
				}
			}
		}
		else {
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j < K; j++) {
					if (i >= x[j]) {
						if (d[i - x[j]] == 0)
							d[i] = 1;
					}
				}
				if (!d[i]) ++res;
			}
			return res;
		}
	}
	int numberOfWins(int maxN, vector <int> moves) {
		int res = solve(maxN, moves);
		return res;
	}
};