SRM 380 Div.2

250 : 쉬운 구현 문제

class LuckyTicketSubstring {
public:
	int maxLength(string s) {
		int res = 0;
		int n = s.size();
		for (int i = 0; i < n; i++) {
			int L = 1;
			for (int j = i + 1; j < n; j += 2) {
				int s1 = 0, s2 = 0;
				int i2 = i + L;
				for (int k = 0; k < L; k++) {
					s1 += s[i + k] - '0';
					s2 += s[i2 + k] - '0';
				}
				if (s1 == s2) res = max(res, L * 2);
				L++;
			}
		}
		return res;
	}
};

500 : 오른쪽으로만 이동할 수 있는 연산의 특성을 고려해 케이스를 잘 나누어 Greedy하게 해결하면 됨.

class LameKnight {
public:
	int maxCells(int height, int width) {
		if (height == 1 || width == 1) return 1;
		if (width >= 7) {
			if (height == 2) return 4;
			return width - 2;
		}
		if (width >= 5) {
			if (height == 2) return 3;
			return 4;
		}
		if (width >= 3) {
			if (height == 2) return 2;
			return width;
		}
		if (height == 2) return 1;
		return 2;
	}
};

1000 : tuple의 개수에 대해 parametric search. 처음에 잘못된 그리디로 접근을 해서 고생을 좀 했다. 시간이 지나가면 다시 풀어보아야 할 문제이다.

class CompilingDecksWithJokers {
public:
	int n;
	int f(vector <int> c, int jokers, int X) {
		long long ret = 0;
		for (int i = 0; i < n; i++) {
			if (X >= c[i]) ret += X - c[i];
		}
		return (ret <= jokers && ret <= X);
	}
	int maxCompleteDecks(vector <int> c, int jokers) {
		int res = 0;
		n = c.size();
		if (n == 1) return c[0] + jokers;
		int mn = 1e9;
		for (int i = 0; i < n; i++) mn = min(mn, c[i]);
		int L = 0, R = mn + jokers, M;
		while (L <= R) {
			M = (L + R) / 2;
			if (f(c, jokers, M)) res = max(res, M), L = M + 1;
			else R = M - 1;
		}
		return res;
	}
};