Think-cell라운드는 레이팅 제한이 없는 Div1+Div2라운드 같은 라운드였다. Div1도 참가 대상이기 때문에 문제가 굉장히 어렵게 느껴졌고, 퍼포먼스는 잘 나왔지만 약간 벽을 느낀 것 같다.
전체적으로 (내가 푼 ABCD는) 관찰이 어렵고 구현이 간단했던 것 같다. 특히 C번은 대회가 끝나기 20분 전에 풀었는데, 생각할 거리가 좀 많았던 것 같다.
후기를 적으려고 문제를 다시 보니 어떻게 풀었는지가 잘 생각이 안났다. 그래서 거의 문제를 다시 풀면서 후기를 적었다. 역시 기록은 제때 하는 것이 최고인 것 같다.
그래도 후기를 적으며 엄밀한 증명을 계속 생각하는 것이 사고력에 많은 도움이 되는 것 같다.
A. Maximise The Score
https://codeforces.com/contest/1930/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int inputs[100];
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 * 2; i++) {
cin >> inputs[i];
}
sort(&inputs[0], &inputs[n * 2]);
long long int res = 0;
for (int i = 0; i < n * 2; i += 2) {
res += inputs[i];
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 간단한 그리디 문제였다. 큰 수부터 정렬해서 (가장 큰수, 두번째로 큰수) ... (두번째로 작은 수, 가장 작은 수)이렇게 묶어주는 것이 최적이다.
B. Permutation Printing
https://codeforces.com/contest/1930/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#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 n;
cin >> n;
int small = 1;
int big = n;
bool down = true;
for (int i = 0; i < n; i++) {
if (down) {
cout << small << " ";
small++;
}
else {
cout << big << " ";
big--;
}
down = !down;
}
cout << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 간단한 관찰 후에 그리디하게 풀 수 있는 해 구성하기 문제였다. n을 입력받고 길이 n짜리 조건에 만족하는 Permuation을 아무거나 하나 출력하면 된다.
조건은 다음과 같다: i =! j이고 p[i]가 p[j]의 약수이고 p[i + 1]이 p[j + 1]의 약수인 (i, j)쌍이 존재하지 않는다.
n이 홀수라고 해보자. n = 2k + 1이라고 하자. p[i] > k라면 p[i]의 배수인 p[j]는 존재할 수 없다.
(p[i]의 배수) = p[i] * d >= (k + 1) * d > 2k + 2 > 2k + 1이고, permutation의 가장 큰 원소가 2k + 1이기 때문이다.
그러므로 모든 짝수 i에 대해 p[i] > k가 되도록 p를 구성할 수 있고, 어떤 i를 잡더라도 i혹은 i + 1의 배수가 배열 내에 존재하지 않게 된다.
짝수일 경우에도 n = 2k일때 p[i] > k여서 p내에 다른 수의 약수가 아닌 k개의 수가 있으므로, 그 수들을 짝수번째에 배치하면 된다.
구현은 큰 수와 작은 수에 대해 각각 현재 몇까지 쓰였는지를 변수에 저장해놓고, for문을 돌리며 i의 홀짝성에 때라서 큰 수 혹은 작은 수를 출력하면 된다.
대회 당시에는 이렇게 엄밀하게 풀지는 못했고, 큰수와 작은수가 번갈아가며 나오면 조건에 나오는 (i, j)쌍을 만들 수 없다는 것만 발견하여 그냥 큰수 작은수 번갈아가며 출력했고, Proof by AC를 했다.
C. Lexicographically Largest
https://codeforces.com/contest/1930/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <queue>
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;
priority_queue<int> values;
for (int i = 1; i <= n; i++) {
int input;
cin >> input;
values.push(input + i);
}
int curr = 1987654321;
while (!values.empty()) {
int next = values.top(); values.pop();
next = min(next, curr);
cout << next << " ";
curr = next - 1;
}
cout << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/내가 대회 당시에 느끼기에는 가장 까다로웠던 C번 문제. 결론은 우선순위 큐로 그리디하게 풀 수 있지만, 그 해의 정당성을 보이는 것이 굉장히 어려웠다.
길이 n짜리 한개의 배열 a가 주어진다. 이 배열에 어떤 연산을 n번 반복하면서 연산의 결과들을 S라는 세트에 넣고, S의 최종 결과를 내림차순으로(S내에 중복되는 원소가 없다)정렬한 배열 b가 사전 순으로 가장 뒤가 되도록 했을 때의 b를 출력하면 된다.
여기서 어떤 연산이란, a[i] + i를 세트에 집어넣고, a[i]를 삭제하는 것이다. (이때 a[i]뒤의 원소들은 인덱스가 1씩 감소하게 된다.)
처음으로 관찰했던 것은, 사전 순으로 맨 뒤이려면 먼저는 최대값을 최대화해야 한다는 것이다. 그리고 연산이 진행될 수록 나올 수 있는 값들은 작아지기 때문에 (a배열의 크기가 감소하면 i의 최대값도 감소한다.)첫번째 연산으로는 a[i] + i의 최대값을 뽑는 것이 이득이다.
이것을 보고나서, 레이지세그를 이용해서 a[i] + i값들을 저장해놓고 최대값을 뽑은 후 i이후의 값들은 모두 1씩 감소시키는 풀이가 떠올랐다. S가 중복을 허용했다면 이 풀이가 맞았을 것이다. 그러나 S가 중복되는 원소를 받지 않으므로, 이것은 최적이 아니다.
중복을 허용하지 않으므로 a[i] + i = x인 최대값 후보가 c개 있다면, 연산 순서를 잘 맞춰서 S에 x, x-1, x-2, ... x-c+1이 모두 들어가도록 만드는 것이 최적이다. 그리고 종이와 1시간정도 씨름한 결과, 결론적으로 이러한 S를 무조건 만들 수 있음을 알게 되었다.
이제 실제 풀이만 짜면 되는데, 고려해야 하는 것이 몇가지 있다.
a = [100, 99, 98, 96]이라 해보자. a[i] + i값은 [101, 101, 101, 100]이 된다. 101이 3개가 있으므로 S에 101, 100, 99를 차례대로 넣게 될 것이고, 남은 100은 98로 들어가게 된다. 그러므로 결과는 101 100 99 98이 된다.
a = [100, 99, 98, 1]이라 해보자. a[i] + i값은 [101, 101, 101, 5]이 된다. 101이 3개가 있으므로 S에 101, 100, 99를 차례대로 넣게 될 것이고, 98을 넣을 차례이지만 남은 최대값이 5이기 때문에 5를 집어넣어야 한다. 그러므로 결과는 101 100 99 5이다.
구현은 priority_queue를 이용하면 간단하다. a[i] + i의 값을 모두 우선순위 큐에 넣고, (현재 S에 들어간 최대값-1)을 curr라는 변수에 저장한 후에 pop을 하고 curr과 비교해서 curr이상이면 curr, curr미만이면 pop한 값을 출력한다. 그리고 curr를 (직전 출력값) - 1로 갱신해주면 된다. priority_queue의 시간복잡도에 의해 총 시간복잡도는 O(N log N)이 된다.
아마 실제 연산 적용 방법까지 출력하도록 문제가 나왔다면 훨씬 어려워졌을 것 같다.
D1. Sum over all Substrings (Easy Version)
https://codeforces.com/contest/1930/problem/D1
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#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;
string s;
cin >> n >> s;
int res = 0;
for (int l = 0; l < s.size(); l++) {
for (int r = l; r < s.size(); r++) {
int count = 0;
int last = l - 2;
for (int i = l; i <= r; i++) {
if (s[i] == '1') {
if (last < i - 1) {
count++;
last = i + 1;
}
}
}
res += count;
}
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/D는 문제가 이해하기 어려웠지만, 이해하고 나면 그냥 쉬운 그리디였다.
f(p)라는 함수에 대해 생각해보자. 1의 개수가 최소라는 조건을 제외하고 q를 생각해보면, 그냥 p와 똑같은 q도 조건을 만족시킨다. 그러므로 p가 0으로만 구성되어있다면 f(p)는 그냥 0이다.
이제 p에 1들이 생긴다고 생각해보자. q에 1을 최소로 추가하면서 조건을 만족시키도록 한다고 생각하면 편하다.
p=111이라면 q=010인 것이 최적이다. (i = 1이면 l=1, r=2: 01, i=2이면 l=2, r=2: 1, i=3이면 l=2, r=3: 10을 잡을 수 있다.)
이제 이것을 일반화시켜서, q[i]가 1이라면, p[i-1]~p[i+1]이 1일 수 있다는 것으로 생각할 수 있다.
q에서 최대한 적은 1을 만들어서 p의 모든 1을 커버한다고 생각하면, p를 스위핑하면서 p[i]가 아직 커버되지 않았다면 q[i+1] = 1로 만들어주고 (이 과정에서 p[i+2]까지 커버된다.) 현재 어디까지 커버했는지를 변수로 관리해주면 p를 한번 스위핑해서 f(p)를 구할 수 있다.
n이 매우 작으므로 s의 모든 서브스트링에 대해 브루트포스를 해주면 O(N^3)짜리 솔루션을 짤 수 있다.
여기서 시작점을 고정하고 끝점만 바꿔가며 스위핑을 하면 O(N^2)솔루션도 구현 가능한데, Hard Version은 n이 10^6까지 가능해서 더 빠른 풀이가 필요하다.
'알고리즘 > 코드포스' 카테고리의 다른 글
| CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) (0) | 2024.05.03 |
|---|---|
| Codeforces Round 934 (Div. 2) (2) | 2024.05.02 |
| Codeforces Round 924 (Div. 2) (1) | 2024.04.12 |
| Codeforces Round 923 (Div. 3) - 블루 달성 (0) | 2024.04.08 |
| Educational Codeforces Round 161 (Rated for Div. 2) (1) | 2024.04.04 |