on
Codeforces Round #754 (Div. 2)
Codeforces Round #754 (Div. 2)
A,B,C,D,E를 50분 내에 풀어서 2등을 하였다.
0:00~0:01
A번을 생각했다. 수 하나를 늘리고 다른 수를 줄이는 연산으로는, 합이 원래 a,b,c와 같은 모든 a,b,c의 쌍을 만들 수 있다. 만약 a+b+c가 3의 배수이면 a+c=2b, 아니면 a+c=2b±1의 꼴로 만들 수 있다. a+c=2b가 가능하면 답은 0, 아니면 답은 1이다. 구현은 1분만에 끝낼 수 있었다.
#include #include #include using namespace std; signed main() { int T; cin >> T; while (T--) { int a, b, c; cin >> a >> b >> c; if ((a + b + c) % 3 == 0) cout << 0 << '
'; else cout << 1 << '
'; } }
0:01~0:05
A번 AC를 확인한 후, B번으로 넘어갔다. 이 문제에서 중요한 관찰은, 정렬됐을 때 0이여야 하는데 현재 1인 위치와, 정렬됐을 때 1인데 현재 0인 위치의 개수가 같다는 것이다. 이 모든 위치들을 뒤집어주면 1과 0이 바뀌면서 정렬이 된다. 이를 통하면 최대 1번에 정렬이 가능하며, 이미 정렬되어 있는 경우 0을 출력하는 것을 잊으면 안 된다.
#include #include #include #include using namespace std; signed main() { int T; cin >> T; while (T--) { int N; cin >> N; string s; cin >> s; int i; vectora; int c = 0; for (i = 0; i < N; i++) { c += s[i] == '0'; } for (i = 0; i < N; i++) { if ((s[i] == '0') != (i < c)) { a.push_back(i); } } if (a.size()) { cout << 1 << '
'; cout << a.size() << ' '; for (i = 0; i < a.size(); i++) cout << a[i]+1 << ' '; cout << '
'; } else cout << 0 << '
'; } }
0:05~0:09
C번을 생각하기 시작했다. a들의 위치를 모두 저장한 뒤, 바로 전 a와 지금 탐색하는 a 사이에 b,c가 각각 2개 미만이면 최솟값에 저장하고, 아니면 넘기는 풀이를 생각했다. 구현했더니 wa를 받았다.
0:09~0:14
이 코드의 반례는 abbacca이다. 바로 전 a만 봐서는 답을 찾을 수 없지만, 길이 7의 답이 있다. 이를 해결하기 위해, 바로 전 a뿐만 아니라 두 번째 전 a까지 체크하도록 코드를 짰고, ac를 받을 수 있었다.
#include #include #include #include using namespace std; signed main() { int T; cin >> T; while (T--) { int N; cin >> N; string s; cin >> s; int i; int befa = -79797979;//I am 79brue fan int ans = 79797979; int b = 0; int c = 0; vectorap; for (i = 0; i < s.size(); i++) { if (s[i] == 'a') { ap.push_back(i); } } for (i = 1; i < ap.size(); i++) { int a = 1; int b = 0; int c = 0; int j; for (j = i-1; j >= max(0, i - 2); j--) { int k; for (k = ap[j + 1]-1; k >= ap[j]; k--) { if (s[k] == 'a') a++; else if (s[k] == 'b') b++; else c++; } if (a > b && a > c) { ans = min(ans, ap[i] - ap[j] + 1); } } } if (ans > N) cout << -1 << '
'; else cout << ans << '
'; } }
0:14~0:25
이제 D번 문제를 볼 수 있었다. 맨 처음에는 기본 O(N)이 필요한 tree dp를 모든 정점에 대해 해야 한다고 생각해서 어려워 보였다. 하지만 중요한 관찰을 두 개 하고 나니, 문제를 쉽게 풀 수 있었다. 관찰 1. 엣지를 타고 다른 노드로 이동할 필요충분조건은 시작 노드와 도착 노드의 2진법 자리수가 같다는 것이다. 증명: 자릿수가 다르면 더 큰 수의 최고 자릿수는 xor할 때 항상 1이고, 이러면 시작과 도착 중 더 작은 수보다 크다. 자릿수가 같으면 xor의 최고 자릿수는 0이 되고, 이러면 둘 중 더 작은 수보다 작다. 관찰 2: 어떤 간선도 사용하지 못하도록 정점을 배치할 수 있다. 트리에서 임의의 정점을 루트로 잡고 depth가 홀수인 것과 짝수인 것을 나누자. 그러면 depth가 홀수인 것에 몇몇 자릿수의 정점을 배정하고, depth가 짝수인 것에 나머지를 배정할 수 있다. 이는 자릿수가 큰 것(특정 자릿수의 가짓수가 많은 것이 아님에 주의하자)부터 그리디하게 배정할 수 있으면 배정하는 방식으로 해줄 수 있다. 그러면 어떤 정점에 돌을 놓아도 이동을 하지 못하고 선이 이기게 된다.
#include #include #include #include using namespace std; vectorlink[200100]; int arr[200100]; int c = 0; void dfs(int n, int p, int o) { c += o == 1; arr[n] = o; int i; for (i = 0; i < link[n].size(); i++) { if (link[n][i] != p) dfs(link[n][i], n, 3 - o); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; while (T--) { c = 0; int N; cin >> N; int i; for (i = 1; i <= N; i++) link[i].clear(); for (i = 1; i < N; i++) { int a, b; cin >> a >> b; link[a].push_back(b); link[b].push_back(a); } dfs(1, 0, 1); vector>r; vectorto; vectoroo; for (i = 1; i <= N; i*=2) { vectort; int j; for (j = i; j < min(2 * i, N + 1); j++) { t.push_back(j); } r.push_back(t); } for (i = r.size() - 1; i >= 0; i--) { if (c >= r[i].size()) { c -= r[i].size(); int j; for (j = 0; j < r[i].size(); j++) { oo.push_back(r[i][j]); } } else { int j; for (j = 0; j < r[i].size(); j++) { to.push_back(r[i][j]); } } } for (i = 1; i <= N; i++) { if (arr[i] == 1) { cout << oo.back()<<' '; oo.pop_back(); } else { cout << to.back() << ' '; to.pop_back(); } } cout << '
'; } }
0:25~0:50
E번을 생각했다. E번에서 중요한 값은 B-A이므로 이를 C라고 정의한다. 관찰 1. 만약 C1이 정해져 있다면 어떻게 할 수 있을까? 답: C를 순서대로 탐색하면서, Ci가 0이 되도록 연산을 해 주고, 이를 다른 노드들에게 전파해주는 것이다. 일단 B1이 0이라고 가정한 뒤 값을 구해보자. 관찰 2. C1이 1 올라갈 때, 나머지 원소들은 어떻게 변할까? 우선 1번에는 decrease 연산을 1번 더 해 줘야 하고, 나머지 모든 원소에는 increase 연산을 한 번 더 해줘야 한다. 그 다음 2번이 1 커졌으므로 2를 제외한 2의 배수는 decrease 연산을 한 번 더 해야 한다. 이런 식으로 하면 increase를 한 번 더 하는 수, decrease를 한 번 더 하는 수, 그대로인 수 3가지로 나눌 수 있다. 그대로인 수는 신경을 쓰지 말고, increase를 한 번 더하는 수는 현재 Ci이 음수면 정답이 1 감소하고, Ci가 0 이상이면 정답이 1 증가한다. decrase를 한 번 더 하는 수는 Ci가 양수여야 1 감소하고, 아니면 답이 1 증가한다. 이런 식으로 현재 C1이 i 올라갔을 때 답이 얼마나 변하는지 계산을 해주면 문제를 풀 수 있다.
#include #include #include #include using namespace std; #define int long long int a[200100]; int b[200100]; int rop[200100]; vectorop[3]; int valc[3][2][2000100]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; int i; rop[1] = 1; for (i = 1; i <= N; i++) { int j; for (j = i * 2; j <= N; j += i) { rop[j] -= rop[i]; } } for (i = 1; i <= N; i++) { cin >> a[i]; } for (i = 1; i <= N; i++) { cin >> b[i]; if (b[i] == -1) b[i] = 0; b[i] = b[i] - a[i]; } int ans = 0; for (i = 1; i <= N; i++) { ans += abs(b[i]); op[rop[i] + 1].push_back(b[i]); int j; for (j = i * 2; j <= N; j += i) { b[j] -= b[i]; } } sort(op[0].begin(), op[0].end()); sort(op[2].begin(), op[2].end()); int c = 0; int k; for (k = 1; k <= 1000000; k++) { int r = lower_bound(op[0].begin(), op[0].end(), k) - op[0].begin(); c -= ((int)op[0].size() - r) - r; valc[0][1][k] = c; } c = 0; for (k = 1; k <= 1000000; k++) { int r = lower_bound(op[2].begin(), op[2].end(), -k+1) - op[2].begin(); c -= r-((int)op[2].size() - r); valc[2][1][k] = c; } int Q; cin >> Q; while (Q--) { int a; cin >> a; int curans = ans; curans += valc[0][1][a]; curans += valc[2][1][a]; cout << curans << '
'; } }
그 뒤
순위를 확인해 봤는데 1등이여서 기분 좋게 F번을 생각했다. 20분 정도 F번을 생각했는데 아무 것도 생각이 안나서 순위를 다시 봤더니 2등이 되어 있었다. C번을 한번 틀린 것 때문이다 ㅠㅠ. 그 뒤로 10분 더 F를 생각했는데 아무 생각이 안 나서 잤다. 자고 일어났더니 겉보기에는 2339인데 아직 배치고사가 안 끝나서 속은 2489인 이상한 codinglunch가 탄생했다.
from http://jjang36524.tistory.com/30 by ccl(A) rewrite - 2021-11-14 10:27:13