[대회] 2020 Kick Start Round G

(2020년 10월 21일에 작성한 글입니다.)

Kick Start - Google’s Coding Competitions

 

Kick Start!!!
전체 421등, 한국에서 14등 했다
거의 마지막 라운드기 때문에 잘 하는 분들이 많이 참여 안 하신 영향도 있지만
그래도 매우 만족 중이다ㅠㅠ
더더더 잘 하자.

1. Kick_Start
KICK이 몇 번 있는지 세고,
START가 나타날 때마다
그때까지 있던 KICK의 개수를 ans에 대해주면 됐다.
근데 우여곡절 끝에 맞출 수 있었는데
우선 KICKICK 처럼 KICK이 두 번 나올 수 있다는 걸 체크해야 하고
정말 중요한 건...
for (i = 0; i < len;)가 string을 훑는 부분이고
for (j = 0; j < 4 && s[i + j]; j++)가
s[i]부터 시작하는 string이 KICK이나 START인지 확인하는 부분이었는데
flag를 true에서 false로 바꾸는 부분이 for문 안에 있어서
만약에 검사하다가 s[i+j]==0이라서 끝나는 경우에는 flag가 안 바뀌었다.
그래서 예를 들어 만약 string이 STAR로 끝나도
flag는 계속 true이기 때문에 cnt가 한 번 더 더해졌다.
그래서... 이걸 따로 체크해줬다.

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	string s;
	int len;
	ll cnt, ans;
	string kick = "KICK", start = "START";
	bool flag;
	int i, j, k;
	cin >> T;
	for (k = 1; k <= T; k++) { 
		cin >> s; 
		len = s.length(); 
		cnt = 0; 
		ans = 0; 
		for (i = 0; i + 4 < len;) { 
			flag = true; 
			for (j = 0; j < 4; j++) { 
				if (s[i + j] != kick[j]) { 
					flag = false; break; 
				} 
			} 
			if (flag) { 
				cnt++; 
				i += 3; 
				continue; 
			} 
			flag = true; 
			for (j = 0; j < 5; j++) { 
				if (s[i + j] != start[j]) { 
					flag = false; break; 
				} 
			} 
			if (flag) { 
				ans += cnt; 
				i += 5; 
				continue; 
			} 
			i++; 
		} 
		cout << "Case #" << k << ": " << ans << '\n'; 
	} 
	return 0;
}

2. Maximum Coins
대각선 방향으로 가면서 더하고
그 합들 중 최대를 구하는거기 때문에
그냥 구현 문제였고...
10분만에 풀었다

int main() { 
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
	int T; 
	int N; 
	ll ans, cnt; 
	int i, j, s, k; 
	cin >> T; 
	for (k = 1; k <= T; k++) { 
		cin >> N; 
		vector<vector<ll>> arr(N, vector<ll>(N)); 
		for (i = 0; i < N; i++) { 
			for (j = 0; j < N; j++) { 
				cin >> arr[i][j]; 
			} 
		} 
		ans = 0; 
		for (s = 0; s < N; s++) { 
			cnt = 0; 
			for (i = 0, j = s; j < N; i++, j++) { 
				cnt += arr[i][j]; 
			} 
			ans = max(ans, cnt); 
		} 
		for (s = 1; s < N; s++) { 
			cnt = 0; 
			for (i = s, j = 0; i < N; i++, j++) { 
				cnt += arr[i][j]; 
			} 
			ans = max(ans, cnt); 
		} 
		cout << "Case #" << k << ": " << ans << '\n'; 
	} 
	return 0; 
}

3. Combination Lock
Brute Force로 하면 TLE이기 때문에
그렇지만 시간 패널티를 적게 받으려고 일단 그렇게 제출해서
첫 테스트 케이스에 대해서는 합격을 받고
어떻게 할지 고민하다가

모든 인풋에 대해서 그 값이랑, 그 값에 N을 더한 값을 배열에 저장한다.
그리고 그걸 정렬한다.
그리고 1~W번째에 대해서만 확인하면 되는데
자물쇠들이 모두 k로 동일해지기 위한 변화량들의 합의 최소를 구하는건데
이 k를 구할 때 W개의 자물쇠의 초기값들만 살펴보면 한다.
만약 k가 그 사이사이에 존재하는 값이라고 해도
차의 절댓값들의 합은 어차피 동일할거기 때문에.

근데 매번 Xi -> k로 가는 경로 중 짧은 건 min(abs(Xi-k), N-abs(Xi-k))이다.
그리고 저 두 값은 abs(Xi-k)가 N/2일때 같고.
그렇기 때문에 저 절댓값이 N/2보다 작거나 같으면 abs(Xi-k), 아니면 N-abs(Xi-k)가 선택되는건데
이건 N이 홀수일때도 성립한다.

이걸 이용해서
어떻게 어떻게 잘 하면 된다....
세그트리 문제 중에서 나무 심기 문제가 떠올랐다.
각각의 절댓값을 구하지 않고,
합을 구해서, 그걸 N * (개수)에서 빼는 방식이라는 게 비슷하다.

근데 진짜 웃긴 건
나무 심기 문제가 떠오른 것 때문에 세그먼트 트리에 꽂혀서 그걸로 합을 구했는데
학교 선배님 코드 보니까 그냥 prefix sum으로 구하면 된다..
나무 심기 문제에서는 새로운 나무를 심을 때 값을 업데이트 해야 하기 때문에 세그먼트 트리가 필요하지만
이 문제에서는 아니다.... 그냥 특정 구간에서의 수들의 합만 있으면 된다.

class Tree { public: Tree() { base = 0; cout << "INITIALIZE THE TREE" << '\n'; } Tree(int size) { for (base = 1; base < size; base *= 2); tree.resize(base * 2, 0); } void init(int size, vector<ll>* arr) { int i; for (i = 0; i < size; i++) { tree[i + base] = (*arr)[i]; } for (i = base - 1; i > 0; i--) { tree[i] = tree[i * 2] + tree[i * 2 + 1]; } return; } void update(int at, type val) { at += base; tree[at] = val; for (at /= 2; at > 0; at /= 2) { tree[at] = tree[at * 2] + tree[at * 2 + 1]; } return; } type get(int from, int to) { from += base; to += base; type ret = 0; while (from <= to) { if (from % 2 == 1) { ret += tree[from++]; } if (to % 2 == 0) { ret += tree[to--]; } from /= 2; to /= 2; } return ret; } private: vector<type> tree; int base; }; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; int W, N; ll ans, cnt; int idx, leftover; int i, j, s, k; cin >> T; for(k = 1; k <= T; k++) { cin >> W >> N; vector<ll> arr(2 * W); for (i = 0; i < W; i++) { cin >> arr[i]; arr[i + W] = arr[i] + N; } sort(arr.begin(), arr.end()); Tree tree(2 * W); tree.init(2 * W, &arr); ans = ll_inf; for (i = 0; i < W; i++) { cnt = 0; idx = lower_bound(arr.begin(), arr.end(), arr[i] - N / 2) - arr.begin(); cnt += arr[i] * (ll)(i - idx) - tree.get(idx, i - 1); leftover = W - (i - idx) - 1; if (leftover > 0) { idx = upper_bound(arr.begin(), arr.end(), arr[i] + N / 2) - arr.begin(); idx--; idx = min(idx, i + leftover); cnt += tree.get(i + 1, idx) - arr[i] * (ll)(idx - i); leftover -= (idx - i); } if (leftover > 0) { idx++; cnt += (ll)((N + arr[i]) * leftover) - tree.get(idx, idx + leftover - 1); } ans = min(ans, cnt); } cout << "Case #" << k << ": " << ans << '\n'; } return 0; }

이 문제 맞추고 나서 정말 엄청 좋았다ㅎㅎ
설마 이게 맞을까...? 하는 심정이었는데
초록색 체크 세 개가 딱 떴을 때 진짜 좋았다

4.
첫 번째 test set은 Brute Force로 할 수 있을 거 같아서 일단 코드 짰는데
생각보다 작성하는 데 시간이 많이 걸려서 그때 시작하길 잘 했다고 생각했다.

void cal(double, vector<ll>); int N; double ans; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; int i, k; cin >> T; for (k = 1; k <= T; k++) { cin >> N; vector<ll> arr(N); for (i = 0; i < N; i++) { cin >> arr[i]; } ans = 0; cal(0, arr); cout << "Case #" << k << ": " << fixed << setprecision(10) << ans << '\n'; } return 0; } void cal(double sum, vector<ll> cur) { int i, j; if (cur.size() == 1) { for (i = 2; i <= N - 1; i++) { sum /= (double)i; } ans += sum; return; } for (i = 0; i < cur.size() - 1; i++) { vector<ll> next(cur.size() - 1); for (j = 0; j != i; j++) { next[j] = cur[j]; } next[i] = cur[i] + cur[i + 1]; for (j = i + 1; j < cur.size() - 1; j++) { next[j] = cur[j + 1]; } cal(sum + next[i], next); } return; }

구글 대회는 ICPC나 Codeforces, 그 외 다수의 대회와 다르게
가장 최근에 ac받은 코드의 제출 시간 + 맞기까지의 시도 * 4로 패널티가 측정되고
test set마다 부분점수가 있다.
그렇기 때문에 큰 data set에도 적용할 수 있는 풀이가 떠올리는 게 막막하면
우선 Brute Force로 풀어서 data set이 작은 것부터 점수를 얻어 놓는 게 더 유리하다.
혹시라도 더 좋은 풀이를 떠올리지 못할 대비해서.
근데 이것도 완전 탐색 풀이를 빨리 구현하는 게 관건이지만
나는 구현에 더 자신있어서 앞으로도 이렇게 하는 게 좋을거 같다.