9번째 라운드에서 Div3을 졸업하고, 10번째 라운드로 코포 스타일의 Div2 라운드를 참가했다.
스코어보드만 봐도 무난해 보이지는 않는 결과인데, 아무튼 C, D번이 별로였다고(개인적으로)생각한다.
항상 그래왔듯이 A, B를 빠르게 풀고, C에서 약간의(?)삽질을 하고, D를 열심히 쳐다봐도 답이 안보여서 체념한 상태로 E를 보니까, 대충 냅색 DP로 풀릴 것 같아서 풀고 맞았다.
2300명이 푼 C와 959명이 푼 D는 둘다 놓쳤지만, 감사하게도 E에 DP가 있어서 아무튼 레이팅은 올랐다. 확실히 내가 DP에만 강하고 다른 분야들(특히 수학)에는 부족함을 느껴서 다른 분야도 열심히 공부해보려고 한다.
A. Rectangle Cutting
https://codeforces.com/contest/1928/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 a, b;
cin >> a >> b;
if (a % 2 == 0) {
if (a / 2 != b) {
cout << "Yes" << '\n';
continue;
}
}
if (b % 2 == 0) {
if (b / 2 != a) {
cout << "Yes" << '\n';
continue;
}
}
cout << "No" << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/간단한 수학문제. 똑같은 직사각형 두개를 붙이고 다시 반으로 나누는데, 나눈 두개가 다르려면 당연히 붙인 쪽으로 나누면 안된다.
그러므로 문제를 직사각형의 가로세로 길이 a, b에 대해 (a, b) -> (a / 2, b * 2)로 바꾸는 것으로 생각할 수 있다.
일단, 모든 변의 길이가 정수여야 하므로 a는 짝수여야 한다.
그리고 90도 회전시 같으면 같은 직사각형이므로 b * 2 != a여야 한다.
(b * 2 == a 라면 (a, b) == (b * 2, a / 2)이고, 90도 회전시 (a / 2, b * 2)가 된다.)
가로를 쪼개도 되고 세로를 쪼개도 되므로 가로세로 중 하나라도 조건을 만족하는지 확인하고, 정답을 출력하면 된다.
B. Equalize
https://codeforces.com/contest/1928/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int a[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;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(&a[0], &a[n]);
deque<int> currs;
int curr = 0;
int res = 0;
for (int i = 0; i < n; i++) {
if (!currs.empty() && currs.back() == a[i]) continue;
if (!currs.empty() && currs.front() + n <= a[i]) {
currs.pop_front();
curr--;
}
curr++;
currs.push_back(a[i]);
res = max(res, curr);
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/주어진 배열 a에 임의의 Permutation을 더했을때, 가장 많이 나타나는 값의 최대값을 구하는 문제.
임의의 Permutation을 설정할 수 있고, 최대값을 구하면 되므로 그리디하게 접근할 수 있다.
Permutation 순서를 원하는대로 설정할 수 있기 때문에, a에서 원하는 값을 원하는 만큼 증가시킨다고 생각할 수 있다. 이때, 증가시키는 값은 중복되지 않고, n-1이다. (최소 1을 더하고 최대 n을 더하기 때문이다.)
증가값이 중복될 수 없기 때문에, a 배열에서 같은 값은 무시해도 된다. (어떻게 증가시키던 서로 다른 값이 된다.)
이제 a에서 중복을 제거한 배열에서, 어떤 x에 대해 x <= a[i] < x + n인 모든 a[i]를 x + n - 1로 같게 만들 수 있다.
그러므로 x <= a[i] < x + n인 a[i]개수를 최대화하는 x를 잡았을 때, 범위 내의 a[i]의 개수가 정답이 된다.
구현은 정렬 후 투포인터로 할 수도 있지만, 나는 정렬 후 덱 스위핑으로 풀었다.
a를 정렬 후 순서대로 덱에 삽입하면서, 덱의 마지막과 a[i]값이 같으면 push하지 않고(중복은 허용하지 않는다),
덱의 front가 back과 n미만으로 차이 날때까지 pop을 해준 뒤, 크기를 체크하고 그중에서 최대값을 구하면 된다.
E. Modular Sequence
https://codeforces.com/contest/1928/problem/E
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int table[200001];
int froms[200001];
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
fill(&table[0], &table[200001], 987654321);
table[0] = 0;
long long int step = 1;
for (int i = 2; step <= 200000; i++) {
for (int j = 0; j <= 200000; j++) {
if (j + step > 200000) break;
if (table[j] != 987654321 && table[j + step] > table[j] + i) {
table[j + step] = table[j] + i;
froms[j + step] = j;
}
}
step += i;
}
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
long long int n, x, y, s;
cin >> n >> x >> y >> s;
long long int r = x % y;
x -= r;
s -= r * n;
if (s < 0 || s % y != 0) {
cout << "No" << '\n';
continue;
}
x /= y;
s /= y;
bool flag = false;
long long int curr = 0;
long long int step = x;
for (int i = 0; i < n; i++) {
curr += step;
step++;
if (s < curr) {
break;
}
int d = s - curr;
int rem = n - 1 - i;
if (table[d] <= rem) {
flag = true;
cout << "Yes" << '\n';
long long int out = x * y + r;
for (int j = 0; j <= i; j++) {
cout << out << " ";
out += y;
}
while (d > 0) {
long long int c = froms[d];
long long int accum = 0;
long long int curr = 0;
while (accum < d - c) {
cout << curr * y + r << " ";
accum += curr;
curr++;
rem--;
}
d = c;
}
for (int i = 0; i < rem; i++) {
cout << r << " ";
}
cout << '\n';
break;
}
}
if (!flag) {
cout << "No" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/주어진 조건을 만족하는 배열 a중 합이 S인 배열이 존재하는지 확인하고, 존재한다면 그 배열을 문제이다. 가능 유무를 판정하고 Yes일 경우 해를 출력해야 하기 때문에 구현량이 약간 많다. 몇가지 관찰을 하면 일종의 냅색 문제로 환원시킬 수 있다.
일단 냅색문제로 만들때까지 몇가지 정수론적인 관찰이 필요하다.
1) x % y == r 이라 할때, a의 모든 원소에 대해 a[i] % y == r이다.
이는 수학적 귀납법으로 증명할 수 있다.
-a[1] == x이므로 a[1] % y == r임은 자명하다.
-a[i] % y == r일 경우,
첫번째 조건을 적용하면 a[i + 1] % y == (a[i] + y) % y == (a[i] % y + y % y) % y == a[i] % y == r
두번째 조건을 적용하면 a[i + 1] % y == (a[i] % y) % y == r % y == r
그러므로 a[i + 1] % y == r역시 참이고, 모든 i에 대해 1)이 성립한다.
2) 조건의 만족하는 배열 a가 존재한다면, sum(b) = (S - r * n) / y인 배열 b가 존재한다.
a[i]를 b[i] * y + r이라고 나타내보자. (이것은 1)에 의해 항상 이렇게 나타낼 수 있음을 보일 수 있다.)
sum(a) == sum(b * y + r) == sum(b) * y + r * n이고, sum(a) == S이므로 sum(b) * y + r * n == S이고, 이항하면 위의 식과 같다.
3) b[1] == (x - r) / y이다.
x == a[1] == b[1] * y + r을 정리하면 위 식이 성립한다.
4) 배열 b의 모든 원소에 대해 b[i] == b[i - 1] + 1 or b[i] == 0이다.
첫번째 조건을 적용해 a[i] = a[i - 1] + y라면 y * b[i] + r == y * b[i - 1] + r + y이고, 식을 정리하면 b[i] == b[i - 1] + 1이다.
두번째 조건을 적용하면 a[i] = r이므로 y * b[i] + r == r이고, b[i] == 0이다.
이 네가지 관찰을 통해 문제를 합이 (S - r * n) / y(이하 D)인 b를 구하는 문제로 바꿀 수 있다.
b는 (x - r) / y부터 시작해서 1씩 증가하는 수열 하나와, 0부터 k까지 k + 1개의 1씩 증가하는 수열 여러개를 이어 붙인 수열로 생각할 수 있다.
이 상황에서 b를 구하는 것은 그리디하게 처리할 수 있다.
b[0]부터 시작해서 1씩 늘려가다가, D를 초과하게 되는 시점에 b[i]를 0으로 만들어주고(sum(b[0]~b[i - 1] <= D가 되도록), 남은 부분을 0부터 k까지의 수열 여러개로 채워서 D를 만들어주면 된다.
이것은 sum(0~k)의 동전들을 최소 개수로 사용해서 D를 만드는 것으로 생각할 수 있고, 냅색으로 풀 수 있다.
냅색의 시간복잡도는 O(N ^ 1.5)가 되고, 미리 DP테이블을 만들어 놓을 수 있기 때문에 전처리에 O(N ^ 1.5), 실제 쿼리 처리에 총 O(N)이 걸리므로 시간 안에 통과가 된다.
마지막으로, 사실은 훨씬 더 많이 틀렸지만, Test1에서 계속 틀려서 스코어보드상에서는 7번만 틀렸다고 기록된 C의 실제 삽질 흔적을 첨부한다.
'알고리즘 > 코드포스' 카테고리의 다른 글
| Codeforces Round 934 (Div. 2) (2) | 2024.05.02 |
|---|---|
| think-cell Round 1 (0) | 2024.04.23 |
| Codeforces Round 923 (Div. 3) - 블루 달성 (0) | 2024.04.08 |
| Educational Codeforces Round 161 (Rated for Div. 2) (1) | 2024.04.04 |
| Codeforces Round 920 (Div. 3) (0) | 2024.03.19 |