Codeforces Global Round 25
이번 라운드도 모든 사람을 참가 대상으로 하는 대회였다.
여느 때와 같이 A를 빠르게 풀고, B를 빠르게 풀어야 했지만 문제 이해를 잘못해서 4번을 틀리고 40분이 지나서야 맞았다. 복구해야 한다는 생각으로 C와 D를 봤는데, 아무리 봐도 모르겠어서 E를 읽었다.
E는 팰린드롬에 관련된 문제였는데 케이스워크를 열심히 하고 나니 무조건 TLE가 나는 O(N ^ 2)풀이가 떠올랐다. 그런데 그 풀이가 O(N ^ 2)인 이유가 팰린드롬을 확인하는 과정이 한번에 O(N)시간이 걸리기 때문이었고, Manacher's를 사용하면 O(N)으로 최적화를 할 수 있길래 열심히 Manacher's를 짜고 맞았다. 그 와중에 continue를 안 써서 출력을 두번 하는 코드를 제출해서 한번 틀리고 맞았다.
나중에 E의 에디토리얼을 보니 모든 팰린드롬을 구하지 않아도 풀 수 있고, 모든 팰린드롬을 브루트포싱하는 "dumber"의 솔루션은 통과되지 못하도록 제한을 설정하려고 했다고 한다.
"Nevertheless, we tried our hardest to make sure dumber "solutions" won't pass."
하지만 출제진은 "Manacher + dumber"는 막지 못했다. 역시 어려운 알고리즘을 쓰면 머리를 안써도 돼서 좋은 것 같다.
그리고 다시 C로 돌아가보니, 너무 많이 풀려 있길래 증명도 없이 사람들이 이렇게 짰을 것 같은 그리디 풀이를 짜서 냈더니 맞았다. 사실 아직도 왜 되는지 정확히는 모르겠다.
A. Dual Trigger
https://codeforces.com/contest/1951/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
for (cin >> T; T; T--) {
int n;
cin >> n;
string s;
cin >> s;
int p1 = -1, p2 = -1;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
if (p1 == -1) {
p1 = i;
}
else {
p2 = i;
}
cnt++;
}
}
if ((cnt & 1) || p1 + 1 == p2) {
cout << "NO" << '\n';
}
else {
cout << "YES" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 쉬운 애드혹 문제였다.
1) 한번에 2개씩 램프가 켜지므로 홀수개를 켤 수는 없다
2) 램프가 4개 이상 켜져있다면, 켜진 램프 개수를 2k라 할 때, 1번째와 k+1번째, 2번째와 k+2번째... 이런식으로 모든 램프를 켠다면 절대로 인접한 램프를 한번에 킬 일이 없다.
3) 램프가 2개라면 그 2개가 인접하지 않아야 한다.
여기서 2, 3번을 한번에 처리할 수 있는데, 그냥 가장 왼쪽 램프와 가장 오른쪽 램프가 인접하지 않은지를 확인하면 된다.
B. Battle Cows
https://codeforces.com/contest/1951/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int table[100000];
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
for (cin >> T; T; T--) {
int n, k;
cin >> n >> k;
k--;
for (int i = 0; i < n; i++) {
cin >> table[i];
}
int i;
for (i = 0; i < n; i++) {
if (table[i] >= table[k]) break;
}
if (i == k) {
for (i++; i < n; i++) {
if (table[i] > table[k]) break;
}
cout << i - 1 << '\n';
}
else {
int res = i - 1;
int curr = (i > 0);
for (i++; i < n; i++) {
if (table[i] >= table[k]) break;
curr++;
}
cout << max(res, curr) << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 케이스워크 몇개만 하면 되는 쉬운 문제였지만 지문 이해를 잘못해서 4번 WA를 받고 40분이 되어서야 맞았다.
1. 만약, 내 소 보다 앞선 더 강한 소가 하나라도 있다면 내 소는 한번도 이기지 못한다.
그러므로 나보다 강한 소가 내 앞에 있다면 최소한 그 소보다 내 소가 앞으로 가도록 교환을 해야 한다.
이 상황에서 두가지 행동을 할 수 있는데, 내 소를 맨 앞으로 보내는 것과 내 소를 내 소보다 강한 첫번째 소와 교환하는 것이다.
첫번째 행동으로 얻을 수 있는 이득은 (내 소보다 강한 소 앞에 있는 소의 수) - 1이 된다. (-1은 내 소와 교환되는 소 때문에 생긴다.)
두번째 행동으로 얻을 수 있는 이득은 (새로운 내 소 위치 ~ 내 소 다음으로 처음 나오는 내 소보다 강한 소 사이의 소의 수) + (만약 내 소의 위치가 맨 앞이 아니라면 1)이 된다.
2. 만약, 내 소보다 앞선 더 강한 소가 없다면, 그냥 내 소를 맨 앞으로 보내면 내 소보다 앞에 있는 모든 소들을 다 이기고 내 소 뒤에 연속적으로 있는 내 소보다 약한 소도 모두 이길 수 있다.
1, 2와 경우를 그냥 그대로 구현하면 맞는다.
C. Ticket Hoarding
https://codeforces.com/contest/1951/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
// value, -idx
pair<int, int> table[300000];
int counts[300000];
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
for (cin >> T; T; T--) {
long long int n, m, k;
cin >> n >> m >> k;
long long int rk = k;
fill(&counts[0], &counts[n], 0);
for (int i = 0; i < n; i++) {
cin >> table[i].first;
table[i].second = -i;
}
sort(&table[0], &table[n]);
long long int res = 0;
for (int i = 0; i < n; i++) {
if (k < m) {
m = k;
}
res += table[i].first * m;
counts[-table[i].second] += m;
k -= m;
if (k == 0) {
break;
}
}
for (int i = 0; i < n; i++) {
rk -= counts[i];
res += (counts[i] * rk);
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C는 신기한 그리디 문제였고, 거의 직관으로 풀은 것 같다.
티켓을 살때마다 나머지 날의 가격이 오른다는 조건 때문에, 최대한 적은 날에 티켓을 사는 것이 이득이다.
그리고 가격이 가장 작은 날부터 차례대로 선택하고, 같은 가격의 날들 중에서는 가장 늦은 날 부터 선택하는 것이 이득이다. 이러한 순서로 k개를 m개씩 분배하다가 m개 미만이 되면 그만큼을 분배하고, 계산하면 답이 나온다.
구현은 가격들을 모두 입력받아 <가격, -인덱스>의 pair로 정렬하고, 정렬한 뒤에 앞에서부터 훑으면서 선택한다.
그리고 날짜를 선택하는 부분과 가격을 계산하는 부분을 분리하는 것이 이후 날짜에 가격이 오르는 것을 반영하기 쉽기 때문에, 위에서 선택된 인덱스에 몇장의 티켓을 사는지를 counts라는 배열에 따로 저장한 뒤에, 날짜 순서대로 한번 더 훑으며 가격을 계산하면 된다.
왜 되는지는 모르겠지만, 컨테스트 시작 후 2시간 정도 지났을 때 거의 6000명이 풀었길래, 다들 이렇게 풀었겠거니 하고 풀어서 제출했더니 맞았다.
E. No Palindromes
https://codeforces.com/contest/1951/problem/E
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int P[2000010];
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
for (cin >> T; T; T--) {
string s;
cin >> s;
int n = s.size();
if (n == 1) {
cout << "NO" << '\n';
continue;
}
char cc = s[0];
bool same = true;
for (int i = 1; i < n; i++) {
if (s[i] != cc) {
same = false;
break;
}
}
if (same) {
cout << "NO" << '\n';
continue;
}
bool ispal = true;
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
ispal = false;
break;
}
}
if (!ispal) {
cout << "YES" << '\n';
cout << 1 << '\n';
cout << s << '\n';
continue;
}
if (n <= 3) {
cout << "NO" << '\n';
continue;
}
if (n == 4) {
cout << "YES" << '\n';
cout << 2 << '\n';
cout << s[0] << s[1] << " " << s[2] << s[3] << '\n';
continue;
}
if (n % 2 == 0) {
cout << "YES" << '\n';
cout << 2 << '\n';
bool flag = true;
for (int i = 0, j = n / 2 - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
flag = false;
break;
}
}
if (flag) {
for (int i = 0; i < n / 2 - 1; i++) {
cout << s[i];
}
cout << " ";
for (int i = n / 2 - 1; i < n; i++) {
cout << s[i];
}
cout << '\n';
}
else {
for (int i = 0; i < n / 2; i++) {
cout << s[i];
}
cout << " ";
for (int i = n / 2; i < n; i++) {
cout << s[i];
}
cout << '\n';
}
continue;
}
// front odd pallind
// manachers
string t = "*";
for (auto c : s) {
t += c;
t += '*';
}
int r = 0, c = 0;
for (int i = 0; i < t.size(); i++) {
if (r < i) P[i] = 0;
else P[i] = min(P[2 * c - i], r - i);
while (i - P[i] - 1 >= 0 && i + P[i] + 1 < t.size() && t[i - P[i] - 1] == t[i + P[i] + 1]) P[i]++;
if (r < i + P[i]) {
r = i + P[i];
c = i;
}
}
bool found = false;
for (int i = 3; i < n; i += 2) {
if (P[i] < i) {
int rem = t.size() - i * 2;
rem /= 2;
if (P[rem] < rem) {
found = true;
cout << "YES" << '\n';
cout << 2 << '\n';
for (int j = 0; j < i; j++) {
cout << s[j];
}
cout << " ";
for (int j = i; j < n; j++) {
cout << s[j];
}
cout << '\n';
break;
}
}
}
if (!found) {
cout << "NO" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/E는 어떤 문자열을 s를 입력받아서 모든 조각이 회문이 되도록 연속된 부분 문자열로 쪼개고, 그렇게 하는 것이 불가능하다면 불가능하다고 출력하는 문제였다.
먼저 s가 회문이 아니라면, 그냥 입력받은 문자열을 그대로 출력하면 된다.
조각 수는 임의로 정할 수 있는데, s가 회문이 아닐 때 조건을 맞춰서 쪼개는 것이 가능하다면 2조각으로 쪼개는 방법도 있음을 직관적으로 알 수 있다.
s가 회문이 아닐 때를 생각해보자.
1. s 전체가 한가지 문자라면 어떻게 나눠도 회문이므로 No를 출력하면 된다.
2. s의 길이가 짝수이고, 한가지 문자로 이루어지지 않았을 때는 문제가 쉽게 풀린다.
s를 절반으로 쪼개서 왼쪽/오른쪽은 l, r이라 해보자.
s가 회문이므로 l과 r은 정확히 대칭이다. 여기서 두가지 경우를 생각해볼 수 있다.
2-1. l이 회문이 아닐 경우, r도 회문이 아니다. 그러므로 l과 r을 출력하면 된다.
2-2. l이 회문일 경우, r도 회문이다. 백준 15927번 회문은 회문 아니야!에서 얻을 수 있는 아이디어가 하나 있는데, (한가지의 문자로 이루어지지 않은)회문에 한 글자를 더하거나 한 글자를 뺀 것은 회문이 아니다.
그러므로 l과 r이 모두 회문이라면 l의 마지막 글자를 빼서 r로 옮기면 둘다 회문이 아니게 되고, 이것을 출력하면 된다.
3. s의 길이가 홀수일 경우 문제가 복잡해진다.
짝수일때는 반을 쪼개면 (회문, 회문)이거나 (비회문, 비회문)이었지만, 홀수일때는 반을 쪼갰을 때 (회문, 비회문)과 같은 쌍이 나올 수도 있으므로 위의 해결책을 적용할 수 없다.
회문에서 한 글자를 빼서 그것을 비회문으로 만들더라도, 비회문이 회문이 되어버릴 수도 있기 때문이다.
s의 길이가 최대 1,000,000이므로 s를 반으로 쪼개는 경우는 999,999개가 있다. 그리고 회문인지를 확인하는 것은 나이브하게 구현하면 문자열의 길이만큼 걸리므로, 모든 쪼개는 경우 중 (비회문, 비회문)이 있는지 확인하는 것은 O(len(s) ^ 2)시간이 걸려서 너무 비효율적이다.
만약 회문인지를 충분히 빨리 확인할 수 있다면 이 솔루션을 적용할 수 있을 것이다. 그리고 Manacher's 알고리즘을 사용하면 회문인지를 충분히 빨리 확인할 수 있다.
Manacher's는 모든 회문을 O(len(s))시간에 구해주는데, 미리 모든 회문을 구해놓고 나면 각 나눠지는 쌍에 대해 양쪽이 회문인지를 확인하는데 O(1)시간이 걸려서, 전처리까지 합쳐서 O(len(s))시간에 답을 구할 수 있다.
1, 2, 3번 경우를 각각 나눠서 잘 처리하면 문제가 풀린다.
정해를 보니 Manacher's없이 풀 수 있는 것 같던데, 아무튼 풀었다.