티스토리 뷰
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 <iostream>
#include <algorithm>
#include <vector>
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 << '\n';
else
cout << 1 << '\n';
}
}0:01~0:05
A번 AC를 확인한 후, B번으로 넘어갔다. 이 문제에서 중요한 관찰은, 정렬됐을 때 0이여야 하는데 현재 1인 위치와, 정렬됐을 때 1인데 현재 0인 위치의 개수가 같다는 것이다. 이 모든 위치들을 뒤집어주면 1과 0이 바뀌면서 정렬이 된다. 이를 통하면 최대 1번에 정렬이 가능하며, 이미 정렬되어 있는 경우 0을 출력하는 것을 잊으면 안 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
signed main()
{
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
string s;
cin >> s;
int i;
vector<int>a;
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 << '\n';
cout << a.size() << ' ';
for (i = 0; i < a.size(); i++)
cout << a[i]+1 << ' ';
cout << '\n';
}
else
cout << 0 << '\n';
}
}0:05~0:09
C번을 생각하기 시작했다. a들의 위치를 모두 저장한 뒤, 바로 전 a와 지금 탐색하는 a 사이에 b,c가 각각 2개 미만이면 최솟값에 저장하고, 아니면 넘기는 풀이를 생각했다. 구현했더니 wa를 받았다.
0:09~0:14
이 코드의 반례는 abbacca이다. 바로 전 a만 봐서는 답을 찾을 수 없지만, 길이 7의 답이 있다. 이를 해결하기 위해, 바로 전 a뿐만 아니라 두 번째 전 a까지 체크하도록 코드를 짰고, ac를 받을 수 있었다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
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;
vector<int>ap;
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 << '\n';
else
cout << ans << '\n';
}
}0:14~0:25
이제 D번 문제를 볼 수 있었다. 맨 처음에는 기본 O(N)이 필요한 tree dp를 모든 정점에 대해 해야 한다고 생각해서 어려워 보였다. 하지만 중요한 관찰을 두 개 하고 나니, 문제를 쉽게 풀 수 있었다. 관찰 1. 엣지를 타고 다른 노드로 이동할 필요충분조건은 시작 노드와 도착 노드의 2진법 자리수가 같다는 것이다. 증명: 자릿수가 다르면 더 큰 수의 최고 자릿수는 xor할 때 항상 1이고, 이러면 시작과 도착 중 더 작은 수보다 크다. 자릿수가 같으면 xor의 최고 자릿수는 0이 되고, 이러면 둘 중 더 작은 수보다 작다. 관찰 2: 어떤 간선도 사용하지 못하도록 정점을 배치할 수 있다. 트리에서 임의의 정점을 루트로 잡고 depth가 홀수인 것과 짝수인 것을 나누자. 그러면 depth가 홀수인 것에 몇몇 자릿수의 정점을 배정하고, depth가 짝수인 것에 나머지를 배정할 수 있다. 이는 자릿수가 큰 것(특정 자릿수의 가짓수가 많은 것이 아님에 주의하자)부터 그리디하게 배정할 수 있으면 배정하는 방식으로 해줄 수 있다. 그러면 어떤 정점에 돌을 놓아도 이동을 하지 못하고 선이 이기게 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
vector<int>link[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<vector<int>>r;
vector<int>to;
vector<int>oo;
for (i = 1; i <= N; i*=2)
{
vector<int>t;
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 << '\n';
}
}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 <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define int long long
int a[200100];
int b[200100];
int rop[200100];
vector<int>op[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 << '\n';
}
}그 뒤
순위를 확인해 봤는데 1등이여서 기분 좋게 F번을 생각했다. 20분 정도 F번을 생각했는데 아무 것도 생각이 안나서 순위를 다시 봤더니 2등이 되어 있었다. C번을 한번 틀린 것 때문이다 ㅠㅠ. 그 뒤로 10분 더 F를 생각했는데 아무 생각이 안 나서 잤다. 자고 일어났더니 겉보기에는 2339인데 아직 배치고사가 안 끝나서 속은 2489인 이상한 codinglunch가 탄생했다.