라운드가 끝난지 약 2달 만에 후기를 올린다.
사실 배치 6판이 끝나고, 제목을 정하지 못해서 글을 안 쓰다가, 이러다 평생 글을 못 쓸까봐 그냥 대회 이름을 제목에 쓰고 후기를 적기 시작했다.
교회에서 기도회가 있어서 1시간 정도 자체 패널티를 가지고 시작했는데, 그래도 무난하게 한 것 같다. F는 제곱근 분할법 까지 떠올리고 세그멘트 트리로 해야하는 줄 알고 넘겼는데, 누적합으로 풀리는 문제였다. 고급 알고리즘들을 공부할수록 쉬운 알고리즘을 두고 어려운 알고리즘으로 짜는 경우가 생기는 것 같다. 조금 더 생각하면서 이런 경우를 줄이는 연습이 필요하다.
A. Square
https://codeforces.com/contest/1921/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int mx = 987654321, Mx = -987654321, my = 987654321, My = -987654321;
for (int i = 0; i < 4; i++) {
int x, y;
cin >> x >> y;
mx = min(mx, x);
Mx = max(Mx, x);
my = min(my, y);
My = max(My, y);
}
cout << (Mx - mx) * (My - my) << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 그냥 문제에서 시키는대로 풀면 되는 문제였다. 단지 사각형의 꼭지점들의 순서가 섞이는 것이 문제였다.
꼭짓점들의 순서를 찾으려면 4!=24가지 경우가 생기고, 풀 수는 있지만 구현이 어려워진다.
여기서 한가지 관찰이 필요한데, 모든 꼭짓점의 X좌표와 Y좌표는 각각 2가지씩만 존재한다. 그러므로 점의 순서를 맞출 필요 없이, 들어오는 값들중 X값 2개, Y값 2개만 찾으면 되고, 이것은 min과 max로 찾을 수 있다. 그리고 (찾은 X좌표 간의 차) * (찾은 Y좌표 간의 차)를 계산하면 정답이 된다.
B. Arranging Cats
https://codeforces.com/contest/1921/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int n;
cin >> n;
string s, f;
cin >> s >> f;
int sc = 0, fc = 0;
for (int i = 0; i < n; i++) {
if (s[i] == f[i]) {
continue;
}
if (s[i] == '1') {
sc++;
}
else {
fc++;
}
}
cout << max(sc, fc) << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 연산들을 최소로 활용해서 배열을 원하는대로 바꾸는 문제이다. 고양이를 추가하는 연산을 1, 고양이를 빼는 연산을 2, 고양이를 옮기는 연산을 3이라 하자.
1을 a번, 2를 b번, 3을 c번 해서 배열을 바꿀 수 있다고 하자.
a > 0 이고 b > 0이라면 a와 b에서 1씩 빼고 c에 1을 추가할 수 있다. (상자 하나에서 빼고 상자 하나에 넣는 것은 옮기는 것과 동치이다.)
그러므로 a나 b중 하나가 0이 될 때까지 c연산으로 바꿔주면 그것이 최적이다. 처음에 c=0이라 가정하고 a와 b횟수를 센 다음, 둘중 하나를 0으로 만들어주면 a, b중 최대값이 최종 결과가 된다. (a > b일 경우 c = b, a = a - c, b = 0, 반대의 경우도 마찬가지)
C. Sending Messages
https://codeforces.com/contest/1921/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
long long int n, f, a, b;
cin >> n >> f >> a >> b;
long long int last = 0;
for (int i = 0; i < n; i++) {
long long int m;
cin >> m;
long long int cost = (m - last) * a;
cost = min(cost, b);
f -= cost;
last = m;
}
if (f > 0) {
cout << "YES" << '\n';
}
else {
cout << "NO" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C는 모든 메시지를 보내야 한다는 조건이 있기 때문에 그리디로 간단하게 풀린다.
결국 메시지를 하나도 놓쳐서는 안되기 때문에, 휴대폰을 종료한 상태에서 하나의 메시지를 지나치는 선택을 할 수 없다. 그러므로 휴대폰을 종료해놓을 수 있는 기간은 각 메시지 사이이고, 그 사이 기간에 휴대폰을 켜놓는 것과 껐다 키는 것 중 더 작은것을 선택하면 된다.
그리고 모든 메시지에 대해서 이렇게 계산한 후에, 그것이 주어진 배터리 양 이하가 되는지만 체크하면 된다.
D. Very Different Array
https://codeforces.com/contest/1921/problem/D
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int a[200000];
int b[200000];
int up[200000];
int down[200000];
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(&a[0], &a[n]);
for (int i = 0; i < m; i++) {
cin >> b[i];
b[i] *= -1;
}
sort(&b[0], &b[m]);
long long int res;
long long int curr = 0;
for (int i = 0; i < n; i++) {
down[i] = abs(b[i] + a[i]);
up[i] = abs(b[i + (m - n)] + a[i]);
curr += up[i];
}
res = curr;
for (int i = 0; i < n; i++) {
curr -= up[i];
curr += down[i];
res = max(res, curr);
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/D는 누적합과 그리디로 푸는 문제였다.
만약 n과 m이 같다면, 배열 a는 오름차순으로, 배열 b를 내림차순으로 정렬한 뒤 매칭시키는 것이 최적이다. 그러나 m이 n보다 크므로 어떻게 매칭시킬지를 정해야 한다.
마찬가지로 a와 b를 반대로 정렬시킨 후에, a를 b의 앞에서부터 연속적으로 매칭시킨 것과, a를 b의 뒤에서부터 연속적으로 매칭시킨 것을 생각해보자. 각각의 경우에서 매칭의 연속을 깨는 것은 무조건 손해이므로, 앞에서 k개, 뒤에서 n-k개를 매칭시키는 것이 최선임을 알 수 있다.
이것을 나이브하게 구현하면, 모든 k에 대해서 시도를 해봐야 하고, 각 k에 대해서 앞쪽과 뒤쪽을 합쳐서 n개의 데이터를 봐야 하므로 각 연산에서 O(n), 총 O(n ^ 2)시간이 걸린다. n이 2*10^5이므로 이것은 시간초과가 난다.
시간복잡도를 줄이기 위해, k개를 앞에서 매칭시킨 것과 k+1개를 앞에서 매칭시킨 것을 보자. 앞쪽 매칭은 하나가 늘었고, 뒤쪽 매칭은 하나가 줄었다. 그러므로 앞쪽 매칭 0~n개까지를 누적합으로 전처리 해놓고, 뒤쪽 매칭도 0~n개까지를 누적합으로 전처리 해놓으면 앞뒤 매칭의 이득을 O(1)시간 안에 구할 수 있고, 계산에는 총 O(n)시간이 걸린다. 누적합 계산 역시 O(n)시간이므로 전처리까지 합친 시간복잡도도 O(n)이 된다.
E. Eat the Chip
https://codeforces.com/contest/1921/problem/E
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int h, w, xa, ya, xb, yb;
cin >> h >> w >> xa >> ya >> xb >> yb;
if (xa >= xb) {
cout << "Draw" << '\n';
continue;
}
int hd = xb - xa;
if (hd % 2 == 1) {
// alice
if (abs(ya - yb) <= 1) {
cout << "Alice" << '\n';
continue;
}
int d;
if (ya < yb) {
d = w - ya;
}
else {
d = ya - 1;
}
if (hd >= d + d - 2) {
cout << "Alice" << '\n';
}
else {
cout << "Draw" << '\n';
}
}
else {
// bob
if (ya == yb) {
cout << "Bob" << '\n';
continue;
}
int d;
if (ya > yb) {
d = w - yb;
}
else {
d = yb - 1;
}
if (hd >= d + d) {
cout << "Bob" << '\n';
}
else {
cout << "Draw" << '\n';
}
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/E는 게임 이론 문제였다.
이 문제에서 먼저 관찰해야 하는 것은, 승자가 될 수 있는 플레이어는 최초 x좌표 차이에서 정해진다는 것이다. x좌표 차이가 홀수라면, alice가 움직일 때마다 차이는 짝수가 되고, bob이 움직일때마다 차이가 홀수가 된다. 그러므로 bob이 움직일 때는 높이 차이가 절대로 0이 될 수 없고, bob은 승자가 될 수 없다. x좌표 차이가 짝수일때는 반대로 alice는 절대로 승자가 될 수 없다. 그러므로 x좌표 차이가 홀짝일때로 경우를 나누면, 한 플레이어가 무조건 다른 플레이어를 피하는 식으로 게임을 단순화시킬 수 있다.
이렇게 게임을 단순화 시킨 후에 피하는 플레이어의 y좌표를 y1, 잡는 플레이어의 y좌표를 y2라 하자.
y1 == y2면 잡는 쪽이 피하는 쪽과 대칭으로 움직이면 무조건 이긴다.
y1 < y2라면 y1은 계속 감소하는 쪽으로 피해야 하고, 피할 공간이 없어질때 (y1 == 0) x좌표가 교차하지 않았다면 잡힌다. 그리고 y1이 충분히 크다면, y1과 y2의 차이는 계속해서 유지되므로 계속 피할 수 있다.
y1 > y2인 경우도 마찬가지로 구할 수가 있다.
alice가 잡는 쪽이라면 첫 턴에 |y1 - y2| == 1일 경우에도 무조건 잡을 수 있다는 것과, 애초에 x좌표가 교차한 상태라서 무조건 비기는 경우들 등까지 조건 분기를 잘 해주면 풀 수 있다.
'알고리즘 > 코드포스' 카테고리의 다른 글
| Codeforces Round 923 (Div. 3) - 블루 달성 (0) | 2024.04.08 |
|---|---|
| Educational Codeforces Round 161 (Rated for Div. 2) (1) | 2024.04.04 |
| 배치 여섯째 판 (3) | 2024.02.13 |
| 배치 다섯째 판 (0) | 2024.01.19 |
| 배치 넷째 판 (1) | 2024.01.06 |