Codeforces Round #693 (Div. 3) A~E

또 떡락했다. 아직 실력이 너무나도 부족하다. 뭔가 마음만 급해지는 듯한 느낌이...꾸준하게 하다 보면 언젠가는 실력이 오를 거라고 생각하지만 이제 나이가 너무 들어 버려서 시간이...

A. Cards for Friends

Problem - A - Codeforces
Codeforces. Programming competitions and contests, programming community

종이를 반으로 자를 수 있을 때(즉 w나 h중 하나가 짝수일 때)까지 계속 잘라주고 거기에 따라 잘려진 조각 수에 2를 곱해준다. 그게 n 이상이면 문제의 조건을 만족시킬 수 있다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int w, h, n;
		int ans = 1;
		cin >> w >> h >> n;
		while (w % 2 == 0) {
			ans *= 2; w /= 2;
		}
		while (h % 2 == 0) {
			ans *= 2; h /= 2;
		}
		if (ans >= n) { cout << "YES\n"; }
		else {
			cout << "NO\n";
		}
	}
	return 0;
 
}

B. Fair Division

Problem - B - Codeforces
Codeforces. Programming competitions and contests, programming community

1그램과 2그램짜리로 이루어진 사탕들이 주어질 때, 사탕을 분배하여 무게가 같은 2개의 사탕 무더기를 만들 수 있는지를 묻는 문제다.

먼저 사탕의 전체 무게 합이 홀수라면 절대로 무게가 같은 2개의 무더기로 나눌 수 없다. 그럼 사탕의 전체 무게 합이 짝수라면? 경우를 나누어서 생각할 수 있다.

1그램짜리가 2개 이상 있다고 생각해 보자. 이때 사탕의 전체 무게 합이 짝수라는 전제가 있으므로 1그램짜리는 짝수 개만큼 있어야 한다. 이때는 2그램짜리 사탕을 어떻게 나누건 간에 1그램짜리 2개를 이용해서 무게를 맞춰 줄 수 있다. 그리고 남은 1그램짜리 사탕도 짝수 개이므로 2개의 무더기에 똑같이 분배하면 된다. 따라서 이때는 언제나 '가능'하다.

1그램짜리가 1개 있다면 사탕의 전체 무게 합이 홀수가 될 것이므로 전제에 위반되어 이런 경우는 존재할 수 없다.

1그램짜리가 0개 있다면, 2그램짜리가 짝수 개만큼 있어야 무게가 같은 2개의 무더기를 만들 수 있음이 당연하다.

이것들을 그대로 코드로 옮기면 된다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, arr[105];
		cin >> n;
		int sum = 0, g1 = 0, g2 = 0;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			sum += arr[i];
			if (arr[i] == 1) { g1++; }
			else { g2++; }
		}
		if (sum % 2 == 1) { cout << "NO\n"; } //그냥 합홀수
		else if (g1 == 0) {//1g 없음
			if (g2 % 2 == 1) { cout << "NO\n"; }
			else { cout << "YES\n"; }
		}
		else { cout << "YES\n"; }
	}
	return 0;
 
}

C. Long Jumps

이 문제에서 너무 많은 시간을 쓰고 뇌절해서 D를 못 풀지 않았을까 하는 생각을 해본다. 그래도 D는 처음 아이디어는 쉬워도 구체적으로 떠올리기 그렇게 쉽지 않던데 연습이 필요한 것 같다.

Problem - C - Codeforces
Codeforces. Programming competitions and contests, programming community

dp라고 할 수 있을까? 아무튼 나는 dp라고 생각한다...

모든 칸에 대해 게임을 다 진행시켜 보고 최대의 점수를 찾을 수도 있겠지만 그러면 당연히 시간초과가 날 것임을 문제의 제한을 보면 알 수 있다. 이때 주목할 점은, 특정 칸까지 도달할 수 있는 모든 경로들 중 최대의 점수를 주는 경로를 이미 찾았다면, 그 다음 칸으로 진행하는 경로와 그전까지의 점수는 아무 상관이 없다는 것이다. 따라서 i번째 칸까지의 최대 점수를 찾아주는 dp 배열을 만들어서 풀 수 있다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, arr[200005] = { 0 }, dp[200005] = { 0 };
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			dp[i] = arr[i];
		}
 
		for (int i = 0; i < n; i++) {
			int cur = i + arr[i];
			if (cur >= n) { continue; }
			dp[cur] = max(dp[cur], dp[i] + arr[cur]);
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			ans = max(ans, dp[i]);
		}
		cout << ans << "\n";
 
	}
 
 
 
 
	return 0;
 
}

D. Even-Odd Game

딥3이 이런 애드혹 문제의 천국이라는데 연습이 좀 필요함을 느낀다. 아니 뭐 애드혹 문제 아니라도 연습이 안 필요한 게 어디 있겠어...

Problem - D - Codeforces
Codeforces. Programming competitions and contests, programming community

길이 n인 수열이 주어지고 이 수열을 두고 앨리스와 밥이 게임을 한다. 앨리스부터 시작해서 둘이 번갈아가면서 숫자를 하나씩 고르는 것이다(중복 선택 불가). 앨리스는 짝수를 골랐을 때 그 수만큼 점수를 얻고, 홀수를 고르면 아무 변화도 없다. 밥은 반대로 홀수를 골랐을 때 그 수만큼 점수를 얻고, 짝수를 고르면 아무 변화도 없다. 이때 서로 최적의 선택을 한다면 앨리스와 밥 중 누가 이길 것인지를 찾으면 되는 문제다.

기본적으로 따지면, 수열에 홀수와 짝수 모두 넉넉할 경우 각자가 점수를 얻을 수 있는 것 중 가장 큰 것을 골라야 한다는 것은 당연하게 알 수 있다. 따라서 홀수와 짝수를 구분하고 정렬해 준다.

그 다음 따져 줄 것은 이때 앨리스와 밥은 최적으로 경기를 진행한다고 했는데 이게 문제다. 앨리스가 어떤 숫자를 고르는 것은 밥이 그 숫자를 고르는 것을 막는 역할도 한다. 밥이 숫자를 고를 때도 앨리스에게 마찬가지다. 따라서 앨리스가 짝수 숫자를 고르는 것보다 밥이 어떤 홀수 숫자를 고르는 것을 막는 것이 더 이득이라면 그렇게 해야 한다. 가령 앨리스의 턴에 2와 999 중 하나를 선택해야 한다면, 밥이 999를 고르는 것을 막는 게 이득일 것이다. 2는 나중에도 고를 수 있기도 하고.

그래서 그때그때 최적인 것을 계산해 주면 된다. 그리고 숫자들 중 짝수나 홀수만 남았을 시에는 앨리스, 밥 둘 중 하나는 점수를 전혀 주지 않는 숫자를 골라야 하지만, 그래도 상대방이 얻을 수 있는 점수를 최소화해야 하므로 큰 숫자부터 고른다.

위의 발상을 그대로 코드로 전환하면 다음과 같은데 나는 그걸 대회에서 못했다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n;
		vector<int> even, odd;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int t;
			cin >> t;
			if (t % 2 == 1) { odd.push_back(t); }
			else { even.push_back(t); }
		}
 
		sort(even.begin(), even.end(), greater<int>());
		sort(odd.begin(), odd.end(), greater<int>());
 
		ll alice = 0, bob = 0;
		int evencnt = 0, oddcnt = 0;
		int alice_move = 1;
 
		while (evencnt < even.size() && oddcnt < odd.size()) {
			if (even[evencnt] >= odd[oddcnt]) { //앨리스 입장에서, 자기가 먹는게 더 이득
				if (alice_move) { alice += even[evencnt]; }
				evencnt++;
			}
			else {
				if (!alice_move) { bob += odd[oddcnt]; }
				oddcnt++; //앨리스는 상대방을 저지하는 게 더 이득
			}
			alice_move = (alice_move ? 0 : 1);
		}
 
		while (evencnt < even.size()) {
			if (alice_move) { alice += even[evencnt]; }
			evencnt++;
			alice_move = (alice_move ? 0 : 1);
		}
 
		while (oddcnt < odd.size()) {
			if (!alice_move) { bob += odd[oddcnt]; }
			oddcnt++;
			alice_move = (alice_move ? 0 : 1);
		}
 
		if (alice > bob) { cout << "Alice\n"; }
		else if (alice == bob) { cout << "Tie\n"; }
		else { cout << "Bob\n"; }
 
	}
 
 
 
	return 0;
 
}

E. Correct Placement

Problem - E - Codeforces
Codeforces. Programming competitions and contests, programming community

간단히 요약한다. 직사각형들의 너비와 높이가 주어진다. 이때 각 직사각형마다 그 직사각형 내부에 쏙 들어가게 넣을 수 있는(즉 너비와 높이 모두 그 직사각형보다 작은)직사각형을 찾아야 하는 문제다.

먼저 세그먼트 트리와 좌표압축, 스위핑을 사용했다는 YunGoon님의 코드다. 고인물같은 아이디어에 비해 구현량이 그리 많지는 않은 것 같지만 윤군님의 코드 압축 능력을 생각해 볼 때 꼭 쉬워서 짧다고 말할 수는 없을 것 같다.

그렇게까지 고급 알고리즘이 많이 사용되지 않는다는 코드포스 Div.2,3에서도 고급 알고리즘을 알고 있으면 좋다는 것을 여실히 보여주는 아이디어의 문제인 것 같다. 윤군님뿐만이 아니라 주변의 많은 사람들이 E를 푼 아이디어에 대해 '세그먼트 트리' 라고 답변한 것을 기반으로 한다. 일단 풀면 좋지 않겠는가?

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.tie(nullptr)->sync_with_stdio(false)
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int MOD = 1e9 + 7;
constexpr int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
constexpr int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
 
int SZ;
vector<int> tree;
 
void update(int idx, int val) {
	for (tree[idx += SZ] = val; idx >>= 1; )
		tree[idx] = max(tree[idx << 1], tree[idx << 1 | 1]);
}
int query(int L, int R) {
	int ret = 0;
	for (L += SZ, R += SZ; L <= R; L >>= 1, R >>= 1) {
		if (L & 1) ret = max(ret, tree[L++]);
		if (~R & 1) ret = max(ret, tree[R--]);
	}
	return ret;
}
 
int main() {
	fastio;
	int T;
	cin >> T;
 
	for (int n; T--; ) {
		cin >> n;
 
		SZ = 1;
		while (SZ < n * 2) SZ <<= 1;
 
		tree.clear();
		tree.resize(SZ << 1);
 
		vector<pair<pii, int>> pos;
		vector<int> C;
		for (int a, b, i = 0; i < n; ++i) {
			cin >> a >> b;
			if (a > b) swap(a, b);
			pos.emplace_back(pii(a, b), i + 1);
			C.push_back(a);
			C.push_back(b);
		}
 
		sort(all(C));
		C.resize(distance(C.begin(), unique(all(C))));
 
		for (int i = 0; i < n; ++i) {
			pos[i].X.X = lower_bound(all(C), pos[i].X.X) - C.begin();
			pos[i].X.Y = lower_bound(all(C), pos[i].X.Y) - C.begin();
		}
 
		sort(all(pos));
 
		int ans[200000];
		for (int i = 0, j; i < n; ) {
			for (j = i; j < n && pos[i].X.X == pos[j].X.X; ++j) {
				int t = query(0, pos[j].X.Y - 1);
				if (t) ans[pos[j].Y - 1] = t;
				else ans[pos[j].Y - 1] = -1;
			}
 
			for (; i < j; ++i) {
				update(pos[i].X.Y, pos[i].Y);
			}
		}
 
		for (int i = 0; i < n; ++i) cout << ans[i] << ' ';
		cout << endl;
	}
 
	return 0;
}

하지만 이렇게 고급 아이디어를 사용하는 문제를(세그먼트 트리 정도는 웰논 중에 웰논이라고 하는 무리들도 있지만 그런 말은 듣는 것이 아니다)딥3에서 1700명이나 풀 수 있었을 리 없다. 일단 내가 세그먼트 트리를 잘 못하기 때문에 절대 저렇게 풀 수 없다. 이것만 적는 풀이는 용납할 수 없다. 따라서 좀더 딥3에 가깝다고 할 수 있는 풀이를 해보자.

먼저, 주어진 직사각형들은 회전할 수 있다는 조건에 주목하자. 그러면 우리는 어떤 게 너비고 어떤 게 높이인지에 상관없이 주어진 높이,너비 쌍을 (큰 것, 작은 것)으로 취급할 수 있다.

그럼 입력받을 때부터 너비와 높이를 (큰 것, 작은 것) 식으로 입력받은 후 정렬을 한다. 앞으로는 큰 것을 너비, 작은 것을 높이라고 생각해서 설명한다. 그러면 정렬된 직사각형들은 너비가 작은 것부터 큰 것까지 나열될 것이고, 너비가 같으면 높이가 작은 것부터 나열되어 있을 것이다. 이때 너비가 같은 것끼리를 한 그룹으로 생각하고 그 그룹들이 너비순으로 나열되어 있다고 생각하자. 그러면 한 직사각형에 대해서, 그 직사각형에 완전히 들어가는 직사각형을 찾기 위해서는 그보다 너비가 작은 그룹들에 대해서만 생각하면 된다. 그런데 너비의 개수는 한정적이다.

그렇다면, '특정 너비보다 작은 너비를 가진 직사각형들 중 가장 작은 높이를 가진 직사각형의 크기와 위치' 를 모든 너비에 대해 미리 구해 놓는다면 모든 직사각형에 대해, 거기에 들어가는 직사각형이 있는지를 쉽게 판별할 수 있을 것이다. 너비순으로 정렬된 데이터가 있으므로 너비를 차차 늘려가면서, 너비가 바뀔 때마다 최소높이를 업데이트해주면 된다. 말로 설명하니까 쉽지 않은데, 코드 동작은 생각보다 간단하다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;

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

	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n;
		pair<pair<int, int>, int> person[200005];

		cin >> n;
		for (int i = 1; i <= n; i++) {
			int w, h;
			cin >> w >> h;
			if (w < h) { swap(w, h); } //무조건 w>=h
			person[i] = { {w,h},i}; //w,h,몇번째 사람인지
		}
		sort(person + 1, person + n + 1);


		int cur_width = 0; //지금 보고 있는 너비
		int cur_min_height = 2000000000, cur_id = 0; //그전까지 본 너비들 중 가장 높이 작은 것의 정보
		int tmp_min_height = 2000000000, tmp_id = 0; //너비 하나를 검토하면서 임시로 높이를 저장

		int ans[200005];
		fill(ans, ans + 200005, -1);

		for (int i = 1; i <= n; i++) {
			int width = person[i].first.first, height = person[i].first.second;
			int id = person[i].second;

			if (cur_width != width) { //만약 너비가 달라지면
				if (cur_min_height > tmp_min_height) { //그전까지의 최소높이 업데이트
					cur_min_height = tmp_min_height;
					cur_id = tmp_id;
				}

				cur_width = width;
				tmp_min_height = 2000000000;
				tmp_id = 0;
			}

			if (tmp_min_height > height) { //임시 최소높이 업데이트
				tmp_min_height = height;
				tmp_id = id;
			}

			if (height > cur_min_height) { 
				//너비가 더 작은 직사각형들 중 높이 또한 더 작은 직사각형이 있다면
				ans[id] = cur_id;
			}

		}

		for (int i = 1; i <= n; i++) {
			cout << ans[i] << " ";
		}
		cout << "\n";


	}


	return 0;

}

https://www.acmicpc.net/problem/1946 이 문제에서 한 발짝 더 나아간, 기본적으로는 비슷한 아이디어다. (한 카카오톡 오픈채팅방에서의 Green55님의 언급으로부터)