이번 라운드에는 D에 doubly linked list가 출제되었는데, 물론 나도 못 풀었고, E는 1700명이 풀었지만 D는 1300명밖에 못 푸는 기현상이 벌어졌다.
에디토리얼을 보니 구현도 그렇게 복잡하지 않았던 것 같은데, PS를 하는 사람들은 대부분 머리에서 링크드 리스트를 지우고 있기 때문에 킬러 문제로 나올 수 있는 것 같다. 자주 만날 일은 없겠지만 그래도 연습을 좀 해야겠다는 생각을 했다.
이번에도 교회 기도회가 끝나고 라운드를 시작해서 1시간정도 자체 패널티를 가지고 시작했지만, 그래도 풀 수 있는 문제는 다 푼 것 같다. E가 굉장히 코포스러운 해 구성하기 애드 혹 문제였는데, 종료 6분 전에 아슬아슬하게 AC를 받았다. 코포를 열심히 하다 보니 이런 류의 문제에도 어느정도 적응이 된 것 같다.
A. Tricky Template
https://codeforces.com/contest/1922/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#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 a, b, c;
cin >> a >> b >> c;
bool flag = true;
for (int i = 0; i < n; i++) {
if (a[i] != c[i] && b[i] != c[i]) {
flag = false;
break;
}
}
if (flag) {
cout << "No" << '\n';
}
else {
cout << "Yes" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 그냥 A였다.
세개의 문자열 a, b, c가 주어지고, 템플릿의 적용 방식이 주어진다. 그리고 a, b는 t를 만족시키고 c는 t를 만족시키지 않는 어떤 템플릿 t가 존재하는지를 판별하면 된다.
일단 a, b를 만족시키도록 템플릿을 만드는 것은 그냥 템플릿을 모두 대문자로 하고, i번째 글자가 a[i]와도 다르고 b[i]와도 다르게 만들면 된다. 이때 c가 t를 만족하지 않으려면 lower_case(t[i]) == c[i]인 i가 하나라도 있으면 된다. 이 조건을 만족시키지 못한다면, 모든 i에 대해 c[i] == a[i] or c[i] == b[i]인 것이므로, 답은 No가 된다. 구현은 for문 한번 돌리면서 확인하면 된다.
B. Forming Triangles
https://codeforces.com/contest/1922/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int inputs[300000];
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 >> inputs[i];
}
sort(&inputs[0], &inputs[n]);
int past = inputs[0];
long long int tot = 0;
long long int count = 1;
long long int res = 0;
for (int i = 1; i < n; i++) {
if (past == inputs[i]) {
count++;
}
else {
if (count >= 3) {
res += count * (count - 1) * (count - 2) / 6;
}
if (count >= 2) {
res += count * (count - 1) / 2 * tot;
}
tot += count;
past = inputs[i];
count = 1;
}
}
if (count >= 3) {
res += count * (count - 1) * (count - 2) / 6;
}
if (count >= 2) {
res += count * (count - 1) / 2 * tot;
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 경우의 수 세기 문제였다.
n개의 변 중 3개를 골랐을 때 삼각형이 되는 쌍의 수를 세면 되는데, 이때 순서는 고려하지 않으므로 중복을 잘 처리해줘야 한다. 삼각형인지 확인하는 것은 가장 긴 변이 나머지 두변의 합보다 작으면 되고(문제에서 넓이가 0보다 큰 삼각형이라 명시했으므로 (2, 1, 1)같은 것은 삼각형이 아니다.), 나이브하게 구현하면 O(n ^ 3)인데, n = 3 * 10^5이므로 시간초과가 난다.
문제의 조건 중 크기가 2^(a) 꼴임을 주목하자. 가장 긴 변의 길이를 2^k라고 할 때, 남은 두 변 중 최소 한 변은 2^k여야 한다. (m, n < k라면 2^m + 2^n <= 2^max(m, n) + 2^max(m, n) <= 2 * 2^(k-1) = 2^k 이기 때문에 2^k < 2^m + 2^n 을 만족시키는 m, n을 절대 고를 수 없다)
그러므로 가능한 삼각형은 정삼각형과, 가장 긴 변이 2개인 이등변삼각형 밖에 없다.
변을 길이별로 묶었을 때 2^k의 개수를 n(k)라 하자. 정삼각형의 개수는 n(k) * (n(k) - 1) * (n(k) - 2) / 6 (중복 제거) 이고, 이등변삼각형의 개수는 (i < k)Σn(i) * n(k) * (n(k) - 1) / 2이다.
(i < k)Σn(i)를 나이브하게 처리하면 k하나당 O(n)시간이 걸리지만, k=0부터 시작해서 차례대로 계산하면 이전 값에 n(k)를 더하며 계산하면 k하나당 O(1)시간만 걸린다. 계산의 시간복잡도는 O(n)이고, bucket sort로도 할 수 있겠지만 나는 그냥 정렬하고 스위핑을 하면서 O(n log n)으로 해결했다.
C. Closest Cities
https://codeforces.com/contest/1922/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int cities[100000];
int rcost[100000];
int lcost[100000];
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 >> cities[i];
}
rcost[0] = 0;
rcost[1] = 1;
for (int i = 2; i < n; i++) {
int curr = cities[i] - cities[i - 1];
if (curr < cities[i - 1] - cities[i - 2]) {
curr = 1;
}
rcost[i] = rcost[i - 1] + curr;
}
lcost[n - 1] = 0;
lcost[n - 2] = 1;
for (int i = n - 3; i >= 0; i--) {
int curr = cities[i + 1] - cities[i];
if (curr < cities[i + 2] - cities[i + 1]) {
curr = 1;
}
lcost[i] = lcost[i + 1] + curr;
}
int m;
cin >> m;
for (int q = 0; q < m; q++) {
int x, y;
cin >> x >> y;
x--; y--;
if (x < y) {
cout << rcost[y] - rcost[x] << '\n';
}
else {
cout << lcost[y] - lcost[x] << '\n';
}
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C는 이동하는데 드는 최소 비용을 처리하는 쿼리가 여러번 들어오는 문제였다.
먼저 쿼리 하나를 보자. x -> y로 이동이 있을 때 x < y라면 계속 오른쪽으로만 이동하는 것이 최소 비용이다. (거슬러가는 것은 무조건 손해이다.) y < x일 때도 마찬가지로 왼쪽으로만 이동하는 것이 최소 비용이다. 가장 가까운 도시는 미리 구해놓을 수 있고, 나이브하게 쿼리를 처리하면 O(n) 시간이 걸린다.
쿼리가 m개 들어오므로 나이브한 풀이로는 O(nm)시간이 걸리고, TLE가 난다. 한가지 생각을 해보자. 가장 가까운 도시는 쿼리가 들어오는 중에 바뀌지 않는다. 그러므로 이동 비용을 처음에 누적합으로 구해놓고, 쿼리가 들어올때는 그 누적합으로 계산해주면 O(1)시간에 처리할 수 있다.
E. Increasing Subsequences
https://codeforces.com/contest/1922/problem/E
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int list[200];
long long int table[200];
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 X;
cin >> X;
long long int count = 2;
if (X == 2) {
cout << 1 << '\n';
cout << 0 << '\n';
continue;
}
table[0] = 1;
list[0] = 0;
int found = -1;
for (int i = 1; i < 200; i++) {
for (int k = i; k >= 0; k--) {
long long int curr = 1;
for (int j = 0; j < i; j++) {
if (list[j] < k) {
curr += table[j];
}
}
if (curr + count <= X) {
list[i] = k;
table[i] = curr;
count += curr;
break;
}
}
if (X == count) {
found = i;
break;
}
}
if (found == -1) {
cout << -1 << '\n';
}
else {
cout << found + 1 << '\n';
for (int i = 0; i <= found; i++) {
cout << list[i] << " ";
}
cout << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/E는 해 구성하기 애드혹 문제였다.
사실 이 문제의 조건에서는 2^100까지의 모든 정수를 만들수 있게 된다.
내가 대회 당시에 푼 아이디어는 이렇다. 먼저 계속해서 증가하는 수열을 만드는데, 이 수열의 부분수열의 개수가 X이하인 최대 길이까지 만든다. 그리고 그 이후부터는 다음에 추가할 수를 조절해가며 X에 점점 가깝게 만든다.
증명 안된 풀이였고, 그냥 제출했더니 한번에 맞았다.
아마 제대로된 풀이는 1, 3, 5, 7 ... 이런식으로 증가하는 수열을 앞에 둔 뒤, 감소하는 짝수 수열을 그 뒤에 붙여서 이진수를 만들듯이 만들면 될 것 같다.
'알고리즘 > 코드포스' 카테고리의 다른 글
| Codeforces Round 924 (Div. 2) (1) | 2024.04.12 |
|---|---|
| Codeforces Round 923 (Div. 3) - 블루 달성 (0) | 2024.04.08 |
| Codeforces Round 920 (Div. 3) (0) | 2024.03.19 |
| 배치 여섯째 판 (3) | 2024.02.13 |
| 배치 다섯째 판 (0) | 2024.01.19 |