[대회] Google Kick Start 2021 Round A

 

Kick Start - Google’s Coding Competitions

 

결과가 많이 아쉽다.

 

A.

코포 A와 유사

비교 대상인 쌍들 중 문자가 같은 것의 개수를 cnt라고 하면 abs(k - cnt)가 답이다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc; cin >> tc;

	for (int forTC = 1; forTC <= tc; forTC++) {
		int n, k; cin >> n >> k;
		string s; cin >> s;
		int cnt = 0;
		for (int i = 0; i < n / 2; i++) {
			if (s[i] != s[n - 1 - i]) cnt++;
		}

		cout << "Case #" << forTC << ": " << abs(k - cnt) << ENDL;
	}

	return 0;
}

 

B.

문제를 보자마자 엄청난 코드를 구현했다.

평소에도 문제 풀 때 일단 구현하고 보는 습관이 있다.. 바꿔야 한다.

역시나 두 번째 케이스에서 TLE가 떴고

그리고 나서 이게 prefix sum 사용하는 문제라는 게 떠올라서 고쳤다.

또 TLE가 떴다.

시간복잡도를 보니 O(N^3)이었다. 최대 n은 1000이었다.

그래서 일단 보류하고 C로 넘어갔다.

 

끝나고 풀이를 보고 다시 짰다.

int cal(int a, int b) {
	if (a < 4 && b < 4) return 0;
	
	int cnt = 0;
	if (a >= 4) {
		cnt += min((a - 2) / 2, b - 1);
	}
	if (b >= 4) {
		cnt += min((b - 2) / 2, a - 1);
	}

	return cnt;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc; cin >> tc;

	for (int tcn = 1; tcn <= tc; tcn++) {
		int r, c; cin >> r >> c;
		vector<vector<int>> arr(r + 5, vector<int>(c + 5));
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				cin >> arr[i][j];
			}
		}

		vector<vector<int>> lr, rl, ud, du;
        //각각 left->right, right->left, up->down, down->up 방향의 prefix sum을 저장
		lr = rl = ud = du = arr;

		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if (arr[i][j]) lr[i][j] = lr[i][j - 1] + 1;
			}
		}

		for (int i = 1; i <= r; i++) {
			for (int j = c; j >= 1; j--) {
				if (arr[i][j]) rl[i][j] = rl[i][j + 1] + 1;
			}
		}

		for (int j = 1; j <= c; j++) {
			for (int i = 1; i <= r; i++) {
				if (arr[i][j]) ud[i][j] = ud[i - 1][j] + 1;
			}
		}

		for (int j = 1; j <= c; j++) {
			for (int i = r; i >= 1; i--) {
				if (arr[i][j]) du[i][j] = du[i + 1][j] + 1;
			}
		}

		
		int ans = 0;
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				ans += cal(lr[i][j], du[i][j]);
				ans += cal(lr[i][j], ud[i][j]);
				ans += cal(rl[i][j], du[i][j]);
				ans += cal(rl[i][j], ud[i][j]);
			}
		}
		
		cout << "Case #" << tcn << ": " << ans << ENDL;
	}

	return 0;
}

cal 함수는 두 방향의 블록 개수가 a, b로 주어질 때 가능한 조합의 개수를 세는 부분이다.

만약 두 쪽이 모두 4보다 작으면 둘 다 긴 쪽이 될 수 없으므로 가능한 경우가 없다.

그리고 a, b가 긴 쪽이 될 수 있는 경우를 각각 계산해서 더한다.

 

C.

이건 코포 B번 같은 느낌이었다.

모든 높이를 priority queue에 넣고 가장 큰 값부터 뽑아서 인접한 것과 확인했다.

인접한 것이 (확인중인 높이 - 1) 보다 작다면 답 업데이트 하고 이 값으로 바꿔준다.

거의 10분만에 풀었다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc; cin >> tc;
	const int diry[4] = { -1, 1,0, 0 }, dirx[4] = { 0, 0, -1, 1 };

	for (int forTC = 1; forTC <= tc; forTC++) {
		int r, c; cin >> r >> c;
		vector<vector<ll>> arr(r + 5, vector<ll>(c + 5, INF));
		priority_queue<pair<ll, pair<int, int>>> pq;
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				cin >> arr[i][j];
				pq.push({ arr[i][j], {i, j} });
			}
		}

		ll ans = 0;
		while (!pq.empty()) {
			ll h = pq.top().first;
			int y = pq.top().second.first;
			int x = pq.top().second.second;
			pq.pop();

			if (arr[y][x] != h) continue;

			for (int k = 0; k < 4; k++) {
				int yy = y + diry[k];
				int xx = x + dirx[k];
				if (arr[yy][xx] == INF) continue;

				if (arr[yy][xx] < arr[y][x] - 1) {
					ans += arr[y][x] - 1 - arr[yy][xx];
					arr[yy][xx] = arr[y][x] - 1;
					pq.push({ arr[yy][xx], {yy, xx} });
				}
			}
		}
		cout << "Case #" << forTC << ": " << ans << ENDL;
	}

	return 0;
}

 

그리고 D를 읽어보다가 첫 번째 테스트케이스는 어떻게 잘 구현할 수 있지 않을까 싶어서 열심히 짰는데

구현하기엔 훨씬 복잡한 문제라는 걸 깨달았다.

그래서 B로 돌아갔는데... 뭔가 계속 놓치고 있었다

결국 종료 전에 못 풀었고.

 

여러모로 정말 많이 아쉽다.