Codeforces Round #693 (Div. 3) A~E
또 떡락했다. 아직 실력이 너무나도 부족하다. 뭔가 마음만 급해지는 듯한 느낌이...꾸준하게 하다 보면 언젠가는 실력이 오를 거라고 생각하지만 이제 나이가 너무 들어 버려서 시간이...
A. Cards for Friends
종이를 반으로 자를 수 있을 때(즉 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
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는 처음 아이디어는 쉬워도 구체적으로 떠올리기 그렇게 쉽지 않던데 연습이 필요한 것 같다.
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이 이런 애드혹 문제의 천국이라는데 연습이 좀 필요함을 느낀다. 아니 뭐 애드혹 문제 아니라도 연습이 안 필요한 게 어디 있겠어...
길이 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
간단히 요약한다. 직사각형들의 너비와 높이가 주어진다. 이때 각 직사각형마다 그 직사각형 내부에 쏙 들어가게 넣을 수 있는(즉 너비와 높이 모두 그 직사각형보다 작은)직사각형을 찾아야 하는 문제다.
먼저 세그먼트 트리와 좌표압축, 스위핑을 사용했다는 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님의 언급으로부터)