셋째 판은 Div2 라운드였다.
A, B를 풀고, F를 휴리스틱으로 풀었는데 통과가 돼서 레이팅이 굉장히 높게 나왔다. 저격에 성공해서 순위가 4000위에서 400위 정도까지 올랐다.
레이팅도 +437점이 되면서 초록을 건너뛰고 바로 민트색이 됐다.
평소와 같이 A, B를 15분도 안 걸려서 풀고, C를 보자마자 말렸음을 직감했다. 20분 정도 생각한 결과 나이브하게 풀다가 어느 순간 끊으면 된다는 것 까지는 찾아냈지만, 그 어느 순간을 구하는 방법을 못 찾아서 결국 대회 시간동안 못 풀었다.
그래서 일단 D, E, F를 보는데, F가 냅색 DP로 풀릴 것 같아서 붙잡고 풀기 시작했다.
일단 냅색으로 지름을 만들 수 있는지 구하고, 그 구한 지름이 실제로 다른 간선들을 가릴 수 있는지를 검증하는 코드를 만들었다. 아닌 경우는 확실히 잡아낼 수 있었지만, 가능한 경우도 간선의 정렬 순서에 따라서 아니라고 나올 때가 있었다. 오름차순으로도 정렬해보고, 내림차순으로도 정렬해보고, 덱으로 앞뒤에서 번갈아가면서 꺼내보기도 했지만 Pretest20에서 계속 잡혔다.
그러다가 시간이 거의 끝나가서, 다시 C를 붙잡고 풀어도 점수는 안 나올 것 같아서 F를 계속 시도하는데, 정석 풀이는 도저히 못 떠올랐다. 그러다가 기가 막힌 풀이가 생각났다.
for (int p = 0; p < 200; p++) {
random_shuffle(shorts.begin(), shorts.end());
...이 코드로 간선을 랜덤으로 섞어서 확인하는 과정을, 200번을 돌렸다. 결국 간선 순서만 맞으면 코드는 제대로 작동 되고, 200번쯤 랜덤으로 돌려봤는데도 No가 나오면 그건 No라고 생각하고 답을 출력했다.
처음에는 p를 100으로 잡고 제출했다. 두근두근 하는 마음으로 체점 현황을 계속 새로고침했고, 계속 걸리던 Pretest20도 통과하고, 기어이 Pretest Accepted가 떴다. 그 순간에 "와 됐다"라는 생각과 "왜 이게 되지"라는 생각이 동시에 들면서도, 실행시간이 여유롭길래 확실한 Systest통과를 위해서 p를 300으로 늘렸다. 그러자 TLE에 가까워지는 것 같아서 p를 200으로 잡고, 제출하고 마무리를 했다. 점수는 100점이 깎였지만, 통과했을 때의 이득이 훨씬 크기에 확실하게 하고 싶었다.
그리고 아침에 일어나자마자 확인해보니, 시스템 테스트까지도 통과해 있었다.
대회가 다 끝나고 나서, 업해킹을 당했다는 알림이 왔다. 그래도 레이팅이나 대회 결과에는 반영되지 않아서 크게 상관은 없지만, 어쨌든 휴리스틱의 한계는 명확하기 때문에 좀더 수련해서 정석대로 풀 수 있게 해야겠다는 생각을 했다.
A. Least Product
https://codeforces.com/contest/1917/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;
int mcount = 0;
bool haszero = false;
for (int i = 0; i < n; i++) {
int input;
cin >> input;
if (input < 0) {
mcount++;
}
else if (input == 0) {
haszero = true;
}
}
if (haszero || mcount % 2 == 1) {
cout << 0 << '\n';
}
else {
cout << 1 << '\n';
cout << 1 << " " << 0 << '\n';
}
}
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 예제에서 다 알려주는 문제였다. 결국 처음 주어지는 A의 곱이 양수라면 0으로 만들어야 하고, 0이나 음수이면 그대로 두면 된다. A의 곱이 양수일 때는 아무거나 0으로 바꾸면 되므로 그냥 무조건 첫번째를 0으로 바꾸도록 코드를 짰다.
B. Erase First or Second Letter
https://codeforces.com/contest/1917/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool used[256];
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;
string s;
cin >> s;
int res = 0; // complete string
int use = 0;
fill(&used[0], &used[256], false);
for (int i = 0; i < n; i++) {
if (!used[s[i]]) {
used[s[i]] = true;
use++;
}
res += use;
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 경우의 수를 세는 문제인데, i번 연산 후에는 스트링의 [0, i]부분 중 한 글자와 [i + 1, ~) 부분을 합친 스트링이 남는다. 그러므로 i번 연산 후에 스트링의 경우의 수는, 뒤에 부분은 i에 따라 1가지이고, 앞부분은 그냥 char테이블을 만들고 몇가지 알파벳이 있는지를 세면 된다.
F. Construct Tree
https://codeforces.com/contest/1917/problem/F
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
int ltable[2000];
int status[2001]; // 0: impossible, 1: not d including, 2: d including
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, d;
cin >> n >> d;
for (int i = 0; i < n; i++) {
cin >> ltable[i];
}
sort(<able[0], <able[n]);
if (ltable[n - 1] + ltable[n - 2] > d) {
cout << "No" << '\n';
continue;
}
int b = ltable[n - 1];
fill(&status[0], &status[d + 1], 0);
status[0] = 1;
vector<int> shorts;
for (int i = 0; i < n - 1; i++) {
shorts.push_back(ltable[i]);
}
for (int k : shorts) {
for (int j = d; j >= k; j--) {
if (status[j - k] != 0) {
status[j] = max(status[j], status[j - k]);
if (j >= b && d - j >= b) {
status[j] = 2;
}
}
}
}
// case1: contains biggest
if (status[d - b] != 0) {
cout << "Yes" << '\n';
continue;
}
// case2: both path must be bigger then big
if (status[d] == 2) {
cout << "Yes" << '\n';
continue;
}
bool found = false;
for (int p = 0; p < 200; p++) {
fill(&status[0], &status[d + 1], 0);
status[0] = 1;
random_shuffle(shorts.begin(), shorts.end());
for (int k : shorts) {
for (int j = d; j >= k; j--) {
if (status[j - k] != 0) {
status[j] = max(status[j], status[j - k]);
if (j >= b && d - j >= b) {
status[j] = 2;
}
}
}
}
if (status[d] == 2) {
found = true;
break;
}
}
if (found) {
cout << "Yes" << '\n';
}
else {
cout << "No" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/F는 간선의 길이들을 주고 이 간선들로 지름이 주어진 d인 트리를 만들 수 있는지를 판별하는 문제이다.
이 문제는 두개의 작은 문제로 쪼개볼 수 있다.
1) 주어진 간선들 중 일부를 활용하여 길이 d의 경로를 만들 수 있는가?
2) 이 경로에 포함되지 않는 간선들을 경로에 적절히 붙였을 때, 이 경로는 여전히 지름인가?
1번 문제는 냅색DP로 간단히 풀린다.
문제는 2번인데, 일단 가장 큰 간선과 두번째로 큰 간선의 길이 합보다 d가 작다면 d는 절대로 지름이 될 수 없다.
그리고 이 조건을 통과한다면, 간선을 최대한 균형있게 나누는 어떤 점을 잡고, 그 점 양쪽 길이가 가장 큰 간선 길이보다 크거나 같은지를 판별하면 된다.
좀더 엄밀히는, 가장 큰 간선 길이를 g라고 하면, 지름을 만드는 간선의 집합 E의 어떤 부분집합 F의 길이 합을 f라고 하면,
g <= f && g <= (d - f)를 만족시키는 F가 존재하면 된다.
처음에는 냅색을 하면서 기본적으로 DP값을 1로 두고 [f, d -f]구간에서 DP값을 2로 해서 d의 DP값이 2가 된다면 Yes를 출력하도록 했다. 그러나 이 풀이는 F가 정렬된 E의 앞에 연속된 원소들밖에 되 수 없기 때문에, Yes인 경우에도 No를 출력할 때가 있었다.
그래서 E를 여러번(200번)섞으면서, 확인했다. 당연히 정답은 아니고, Systest까지는 살아남았지만 결국 업핵을 당했다.
업솔빙
C. Watering an Array
https://codeforces.com/contest/1917/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int atable[2000];
int vtable[100000];
int GetScore(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
if (atable[i] == i + 1) {
res++;
}
}
return res;
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int n, k, d;
cin >> n >> k >> d;
for (int i = 0; i < n; i++) {
cin >> atable[i];
}
for (int i = 0; i < k; i++) {
cin >> vtable[i];
}
int curr = GetScore(n);
bool towait = true;
int b = vtable[0];
for (int j = 0; j < b; j++) {
atable[j]++;
}
for (int i = 1; i < min(d, 4008); i++) {
towait = !towait;
if (towait) {
curr++;
}
int next = GetScore(n);
if (next > curr) {
curr = next;
towait = true;
}
int b = vtable[i % k];
for (int j = 0; j < b; j++) {
atable[j]++;
}
}
if (d > 4008) {
int rem = d - 4008;
if (!towait) {
curr++;
rem--;
}
curr += rem / 2;
}
cout << curr << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C는 주어진 두가지 연산으로 얻을 수 있는 최대의 이득을 찾는 문제이다.
이 문제를 풀기 위해서는 두가지 관찰이 필요하다.
1. 한번 점수를 더하고 배열이 초기화 된 이후부터는 2번의 연산에 1씩 이득 보는게 최선이다.
연산이 한번 시행되고 나서는 배열이 모두 0이다. 그리고 배열에 값을 더하는 연산에서 주목해야 할 것이 있는데, 앞에서부터 더해지기 때문에 연산을 어떻게 하더라도 배열에 증가하는 부분이 생기지 않는다. 즉, i < j 이면 a[i] >= a[j]이다.
그리고 배열에 몇번의 연산을 하고 나서 이득을 취한다고 하자.
어떤 k에 대해 k = a[k]라고 하면, j < k에 대해서는 j < k = a[k] <= a[j], j < a[j]이다. 그러므로 k보다 작은 값에서는 이득이 없다.
마찬가지로 j > k에 대해서도 j > k = a[k] >= a[j], j > a[j]이므로 이득이 없다.
그러므로 연산을 몇번을 어떻게 하던지 얻을 수 있는 이득은 최대 1이다.
그러므로 물을 한번 줘서 a[1] = 1로 만들고 바로 다음에 1의 이득을 취하는 것이 최선이다.
2. 처음 배열에서, 몇번의 연산을 거친 후 얻을 수 있는 최대의 이득은 2000 이하이다.
실제 대회 중에는 이것을 못 떠올려서 풀이를 못 짰다. 당연히도, a[i] = i 일때 1씩 점수를 얻으므로, 크기가 2000인 배열에서 얻는 이득은 2000을 넘을 수 없다.
그러므로, 배열에서 첫번째로 이득을 얻는 시점은 연산 4000번 이하에 이루어져야 한다. 왜냐하면 위의 1번에 의해서 4000번동안 1, 2번 연산을 반복했을 때 얻는 이득이 2000이기 때문이다.
이 두가지 사실을 바탕으로, 연산 4000번까지는 나이브하게 해보면서 4000번 동안 얻을 수 있는 최대의 이득을 계산하고, 이후에 남은 횟수는 2로 나누어서 더해주면 최대 이득을 계산할 수 있다.
나이브한 계산에서 한 연산당 이득 계산은 n번 연산이 필요하다. (배열 전체를 확인해야 하므로)
그리고 4000번 연산을 해봐야 하고, n의 총합이 2000이 넘지 않으므로, 대충 8,000,000번의 연산으로 여유롭게 시간제한도 통과한다.