https://codeforces.com/contest/1605
Dashboard - Codeforces Round #754 (Div. 2) - Codeforces
codeforces.com
정말 오랜만에 라이브 코포를 했다.
사실 코포 자체가 정말 오랜만이었다.
A.
d(a1, a2, a3) = |a1 + a3 - 2 * a2| 에서 1을 증가시키거나 감소시키는 두 수가 a1, a3가 되면 d값이 변하지 않는다.
따라서 a1과 a3 중 하나와 a2를 골라야 하는데, 이때 결과적으로 | | 안의 값은 3 증가하거나 감소한다.
만약 a1을 1 증가시키고 a2를 1 감소시키면 +3 되고, 반대로 하면 -3 되니까.
그러므로
d(a1, a2, a3)
= |a1 + a3 - 2 * a2|
= |a1 + a2 + a3 - 3 * a2| 인데
operation을 계속하다 보면 3의 배수에 해당하는 3 * a2 값은 어차피 상쇄되므로
a1 + a2 + a3를 3으로 나눈 나머지만 구하면 된다.
이때 주의할 점은, 만약 (a1 + a2 + a3) % 3 = 2 라면 |2 - 3| = 1로 더 줄어들 수 있다는 거다.
그래서 나는 그냥 min(sum % 3, 1)을 출력했다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int sum = 0;
for (int i = 0; i < 3; ++i) {
ll input; cin >> input;
sum += input % 3;
}
cout << min(sum % 3, 1) << kEndl;
}
}A번인데 11분이나 걸렸다.
B.
문제가 복잡해 보였지만 알고 보니 어렵지 않았다.
코포를 하면서 항상 염두에 두고 있는 것 중에 하나는 문제에서 제공하는 예제 풀이에 너무 몰입하여 생각하지 않아야 한다는 거다.
이 문제도 예제 풀이를 보면 되게 복잡해 보이는데, 그것보다 훨씬 간단하게 풀 수 있었다.
결국 원하는 것은 0과 1로 이루어진 수열을 0이 앞쪽, 1이 뒤쪽에 나오는 것으로 바꾸는 거다.
결과 수열에서 0과 1의 위치가 이미 정해져 있으므로, 해당 위치에 있지 않은 친구들만 옮기면 된다.
그래서 그냥 첫 번째부터 (전체 수열 길이) - (1의 개수) 번째 중에서 1이 있는 인덱스, 그 뒤에 수 중에서 0이 있는 인덱스를 모아서 출력하면 답이다.
예를 들어 예제의 10100을 보면
10100 -> 00011이 되어야 하므로 1~3번째 중에 있는 1의 인덱스, 4~5번째 중에 있는 0의 인덱스를 출력하면 된다.
그리고 처음부터 non-decreasing 상태이면 k는 0이고, 그렇지 않을 때는 한 번 만에 무조건 원하는 수열을 만들 수 있어서 k는 무조건 1이다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
string s; cin >> s;
int count_1 = 0;
for (const char& c : s) {
if (c == '1') {
++count_1;
}
}
vector<int> ans;
for (int i = 0; i < s.length() - count_1; ++i) {
if (s[i] == '1') {
ans.push_back(i);
}
}
for (int i = s.length() - count_1; i < s.length(); ++i) {
if (s[i] == '0') {
ans.push_back(i);
}
}
if (ans.size()) {
cout << 1 << kEndl;
cout << ans.size() << ' ';
for (const int& idx : ans) {
cout << idx + 1 << ' ';
}
cout << kEndl;
}
else {
cout << 0 << kEndl;
}
}
}
C.
많은 깨달음을 얻은 문제다.
첫 제출에서 런타임 에러가 났는데,
for (int i = 0; i < s.length() - 2; ++i) {
if (s[i] == 'a' && s[i + 2] == 'a') {
ans = 3;
break;
}
}s.length()가 반환하는 값 타입이 unsigned int라서 이런 코드가 있을 때 string s의 길이가 1이면 underflow가 발생한다.
그래서 i = 0일 때 i < s.length() - 2가 true로 처리되는데, 그러고 나서 s[i + 2]에 접근하니까 런타임 에러가 난 거였다.
이걸 라운드 중에 깨달아서 정말 다행이었다...
이걸 해결하는 방법엔 두 가지가 있는데
하나는 (int)s.length() - 2 이런 식으로 casting 하는 거고,
다른 하나는 처음부터 i + 2 < s.length() 이렇게 작성하는 건데,
후자가 훨씬 좋아 보인다.
애초에 이 조건이 'i + 2 인덱스가 bound 안에 있는가?'를 확인하는 용도니까.
그런 맥락에도 맞고, 이해하기도 훨씬 쉽다.
좋은 코딩 습관이 몸에 배도록 항상 신경 쓰면서 코드 작성해야겠다.
이 문제에서 가장 중요한 포인트는, 우리가 원하는 substring은 무조건 a로 시작하고 끝난다는 거다.
- 'a' occurs strictly more times in this substring than 'b'
- 'a' occurs strictly more times in this substring than 'c'
위 두 조건을 만족해야 하므로 a로 시작하는 string에서 a 이후에 b나 c가 등장하는 순간 'occurs strictly more times' 조건을 위반하게 되고, 이를 만회하려면 결국 또 a가 등장해야 한다. (ex. aba)
그 뒤에 b나 c가 또 등장하면 또 같은 이유로 a가 등장해야 하는데, 그 경우는 결국 이전에 고려한 케이스에 포함되기 때문에 더 이상 살펴볼 필요가 없다.
예를 들어 ababa는 어차피 aba를 포함하고 있으므로 위에서 확인한 케이스에 포함된다.
그래서 확인해야 하는 substring은
aa
aba 혹은 aca
abca 혹은 acba
이렇게 세 종류다.
라고 생각했으나 반례가 하나 더 있었다.
abbacca 혹은 accabba
이렇게 b나 c가 연속으로 나오는 경우도 생각했지만, 개수가 strict하게 크기 위해서는 abbaa 이런 식으로 a가 연속해서 나올 수밖에 없기 때문에 고려 대상이 아니라고 판단했다.
근데 이런 식으로 abba와 acca가 가운데 a를 공유하는 경우가 있었다....
라운드가 끝나기 전에 이걸 찾아서 뿌듯했다. ㅎㅎ
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
string s; cin >> s;
int ans = -1;
for (int i = 0; i < n - 1; ++i) {
if (s[i] == 'a' && s[i + 1] == 'a') {
ans = 2;
break;
}
}
if (ans == -1) {
for (int i = 0; i < n - 2; ++i) {
if (s[i] == 'a' && s[i + 2] == 'a') {
ans = 3;
break;
}
}
}
if (ans == -1) {
for (int i = 0; i < n - 3; ++i) {
if (s[i] == 'a' && s[i + 3] == 'a') {
if (s[i + 1] != s[i + 2]) {
ans = 4;
break;
}
}
}
}
if (ans == -1) {
for (int i = 0; i < n - 6; ++i) {
if (s[i] == 'a' && s[i + 3] == 'a' && s[i + 6] == 'a') {
if (s[i + 1] != s[i + 4]) {
ans = 7;
break;
}
}
}
}
cout << ans << kEndl;
}
}