두번째 라운드는 Div1/Div2 공통 라운드였고, 코드포스 스타일로 문제별 배점이 있고 같은 문제도 패널티에 따라 점수가 달라졌다.
전 참가자 대상이라 문제가 전체적으로 어려웠던 것 같고, 25분동안 2문제를 풀고 남은 2시간 35분동안은 문제만 구경하다 끝났다. B는 충분히 풀 수 있을만한 문제였지만, 문제를 풀 당시에는 소수에 꽃혀서 2의 거듭제곱으로 나눠볼 생각을 하지 못했고, D도 시간을 충분히 들였으면 풀만한 문제였지만 B와 D중 고민하면서 결국 둘다 제대로 풀지 못한 것 같다.
E는 보고 SCC로 풀릴 것 같다는 생각은 했지만 그래프 공부를 열심히 안해서 시도해보지도 못했다.
전체적으로 코드포스 스타일에 대한 경험도 부족했고, 전략적으로 한 문제만 붙잡고 끝까지 풀었어야 했지만 그런 판단이 늦어서 아쉬웠다. 그래도 A와 C를 빨리 풀어서 순위는 3630등으로 생각보단 높게 나왔다.
Carrot이라는 구글 확장 프로그램을 사용해봤는데, 이 대회에서 내 수준이 어느정도였는지 나와서 객관적인 결과를 확인할 수 있다.
레이팅은 320점이 올랐지만, 두번째 라운드에서는 350점을 기본으로 주기 때문에 실질적으로는 -30점이다.
A. Distinct Buttons
https://codeforces.com/contest/1909/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
bool U = false, R = false, D = false, L = false;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
if (x > 0) {
R = true;
}
if (x < 0) {
L = true;
}
if (y > 0) {
U = true;
}
if (y < 0) {
D = true;
}
}
if (U && D && L && R) {
cout << "NO" << '\n';
}
else {
cout << "YES" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 위, 아래, 오른쪽, 왼쪽의 4가지 방향 버튼 중에 3가지만 눌러서 주어진 점을 모두 방문할 수 있는지를 묻는 문제이다.
x가 0보다 작은 좌표가 하나라도 있다면, 왼쪽 버튼이 필요한 것이고, 나머지 방향 버튼도 마찬가지로 사용해야 하는지 판정할 수 있다. 그러므로 각 버튼을 사용해야 하는지 4개의 bool변수를 만들고, 입력을 받으면서 스위핑을 하고 마지막에 모두 다 true라면 4개 버튼을 눌러야 하는 것이다.
C. Heavy Intervals
https://codeforces.com/contest/1909/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int ltable[100000];
int rtable[100000];
int ctable[100000];
int length[100000]; // all available lengths
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> ltable[i];
}
sort(<able[0], <able[n]);
for (int i = 0; i < n; i++) {
cin >> rtable[i];
}
sort(&rtable[0], &rtable[n]);
// generate lengths
stack<int> lefts;
// i : point l, j : point r
int i = 0, j = 0;
while (j < n) {
if (i < n && ltable[i] < rtable[j]) {
lefts.push(ltable[i]);
i++;
}
else {
length[j] = rtable[j] - lefts.top(); lefts.pop();
j++;
}
}
sort(&length[0], &length[n]);
for (int i = 0; i < n; i++) {
cin >> ctable[i];
}
sort(&ctable[0], &ctable[n]);
long long int res = 0;
for (int i = 0; i < n; i++) {
res += (long long int)length[i] * ctable[n - 1 - i];
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C번은 구간과 가중치가 주어질 때, 구간의 조건을 만족하게 하면서 (시작이 끝보다 작음) 총 가중치의 합이 최소가 되도록 구간을 조정하는 문제이다.
구간을 변경해도 총 길이는 동일하기 때문에, 작은 가중치부터 최대한 긴 구간을 만들며 할당해주는 식으로 그리디하게 풀 수 있다.
업솔빙
B. Make Almost Equal With Mod
https://codeforces.com/contest/1909/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
long long int numbers[100];
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> numbers[i];
}
long long int k = 1;
bool diff = false;
while (!diff) {
k *= 2;
long long int val = numbers[0] % k;
for (int i = 1; i < n; i++) {
long long int r = numbers[i] % k;
if (val != r) {
diff = true;
break;
}
}
}
cout << k << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B번은 배열의 모듈러 값이 정확히 2가지가 되도록 하는 K를 찾는 문제였다.
처음에 홀짝으로 나눠볼 생각까지는 했다가, 소수에 꽃혀서 2의 거듭제곱은 생각하지 못했던 것 같다.
풀이는 그냥 k=2부터 시작해서 나머지가 2가지가 될 때까지 k에 2를 곱해주면 된다.
이게 되는 이유는, 2^p로 나눈 나머지는 하위 p비트가 되고, k까지 나눴을 때 나머지가 모두 같다면 k*2에서 발생할 수 있는 차이는 최대 1비트라서 반드시 2가지 나머지만 존재하는 순간이 생기기 때문이다.
k가 2^58이 되면 모든 a보다 커지기 때문에 무조건 종료되고, 시간복잡도는 O(t*n*58)이고 t*n이 50000이기 때문에 무난하게 통과한다.
D. Split Plus K
https://codeforces.com/contest/1909/problem/D
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철
*/
#include <iostream>
#include <algorithm>
using namespace std;
long long int table[200000];
long long int GCD(long long int a, long long int b) {
if (b == 0) {
return a;
}
return GCD(b, a % b);
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
long long int k;
cin >> n >> k;
bool upper = false;
bool lower = false;
bool equal = false;
for (int i = 0; i < n; i++) {
cin >> table[i];
if (table[i] > k) {
upper = true;
}
else if (table[i] == k) {
equal = true;
}
else {
lower = true;
}
}
if (equal) {
if (!lower && !upper) {
cout << 0 << '\n';
}
else {
cout << -1 << '\n';
}
}
else if (upper) {
if (lower) {
cout << -1 << '\n';
continue;
}
long long int rem = table[0] - k;
long long int curr = table[0] - k;
for (int i = 1; i < n; i++) {
rem += table[i] - k;
curr = GCD(curr, table[i] - k);
}
cout << rem / curr - n << '\n';
}
else {
long long int rem = k - table[0];
long long int curr = k - table[0];
for (int i = 1; i < n; i++) {
rem += k - table[i];
curr = GCD(curr, k - table[i]);
}
cout << rem / curr - n << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/D번은 주어진 수열을 정해진 연산으로 나누었을 때 수열의 값을 모두 같게 만들 수 있는지와, 방법이 있다면 최소 몇번 연산을 해야 하는지를 묻는 문제.
차라지 B를 빨리 포기하고 D를 풀었으면 시간 안에 풀렸을 수도 있을 것 같다.
이 문제에서 캐치해야 하는 것은
1. 나누는 연산만 있고 합치는 연산이 없기 때문에 수열의 각 수에 대해 독립적으로 연산을 시행한다.
2. 연산을 어떤 식으로 시행하든, 한 수 a에 n번 연산을 하면 그 나눠진 수의 개수는 (n + 1)개이고, 수들의 합은 n*k + a이다.
이렇게 두가지이다.
이 두가지를 통해 문제를 잘 변형하면, 수열을 모두 k+d 로 만드는 것인데, 연산을 a에서 a-d와 k+d로 나누는 것으로 생각해도 된다. 이렇게 생각할 때 a=k+p*d라고 한다면 a에 (p-1)번 연산을 실행하면 a를 p개의 k+d로 나눌 수 있다.
그러므로 주어진 수열이 모두 k보다 크다면 각 수에서 k를 뺀 값의 GCD를 d라고 두고 계산하면 풀린다.
주어진 수열에 k와 같은 값이나 k보다 작은 값이 있을 때도 처리해야 하는데,
모든 값이 k와 같을 때는 주어진 수열이 이미 같으므로 0을 출력하면 되고
모든 값이 k보다 작으면 d를 음수라 생각했을 때 k에서 각 수열의 값을 빼고 GCD를 구하면 위의 풀이와 비슷하게 풀 수 있다.
k보다 큰 값, k와 같은 값, k보다 작은 값이 두 종류 이상 섞여있다면 문제를 풀 수 없기 때문에 -1을 출력하면 된다.
'알고리즘 > 코드포스' 카테고리의 다른 글
| 배치 다섯째 판 (0) | 2024.01.19 |
|---|---|
| 배치 넷째 판 (1) | 2024.01.06 |
| 배치 셋째 판 - 민트 달성 (1) | 2023.12.30 |
| 배치 첫판 (1) | 2023.12.27 |
| 코드포스 배치부터 레드까지 (1) | 2023.12.23 |