USACO 2020 Open contest Gold 풀이
Intro
PS를 거의 한달간 접었었는데, 올해 ICPC를 나갈 수 있다는 희망이 보여서 급하게 PS 재활 중입니다. 최대한 빨리 플래티넘을 안정적으로 해결할 수 있는 실력까지 올렸으면 좋겠네요. 가능할지는 아직 미지수입니다. 이 셋 푸는데도 두시간은 넘게 걸렸으니 미래가 어둡네요 :(
18874 Haircut
문제 링크 : https://www.acmicpc.net/problem/18874
문제를 요약하면 각 $j$에 대해 $j$보다 큰 수열의 원소들이 정확히 $j$로 바뀔 때, 수열의 inversion을 구하는 문제입니다. 이런 문제에서 흔히 나오듯이 $j$를 큰 수부터 작은 수까지 움직이면서 차례대로 구해봅시다. 수열의 inversion은 수열의 각 원소 $a_i$에 대해 인덱스가 $i$보다 작으면서 수가 $a_i$보다 큰 수의 개수를 모두 더한 것입니다. 수열의 inversion이 변하려면 당연히 수열의 원소가 하나 이상 변해야 합니다. 이 사실을 조금 확장하면 다음과 같이 생각해볼 수 있습니다.
- 이 문제에서는 $j$가 1만큼 줄어들면 기존에 길이가 $j$였던 원소들의 값이 모두 동일하게 1만큼 줄어듭니다.
- 수열에 $j$보다 크기가 큰 원소는 당연하게도 존재할 수 없습니다.
- 결정적으로, $j$가 1 줄어들 때 기존에 값이 $j-1$이었던 원소를 포함하는 쌍을 제외한 모든 쌍에 대한 대소관계가 그대로 유지됩니다.
생각의 편의를 위해, 원소의 값이 $j$에 걸치는 순간 그 원소에 X를 친다고 합시다. 따라서 X가 쳐져있는 원소들은 모두 같은 값을 가지면서, 또 수열에서 최댓값이 됩니다. 그러면 사실 inversion count는 이 X를 치는 순간에만 변하게 됩니다(그 전까지는 원소 간 대소관계가 변하지 않으므로). 예를 들어 5 2 3 3 0은 $j=5$일 때 X 2 3 3 0, $j=3$일 때 X 2 X X 0 이 될 것입니다. 이렇게 두면 특정 원소가 X로 바뀔 때 inversion count가 얼마나 줄어드는지를 계산할 수 있습니다. 원래는 그 원소 앞쪽에 있으면서 자신보다 큰 원소들이 inversion count를 1씩 증가시키고 있는 중이었으나, X로 바뀌면서 이 원소는 최댓값이 되어버렸으므로 그 inversion count가 모두 사라지게 됩니다. 따라서 특정 원소가 X가 되는 순간 앞쪽에 있으면서 기존에 자신보다 컸던 원소의 개수만큼 inversion count가 줄어들게 됩니다. 그런데 $j$를 감소시키면서 생각해 보면 지금 원소 $a_i$가 X로 바뀐다는 것은 기존 $j$가 $a_i+1$이었다가 $a_i$로 바뀐다는 것이기에 '기존에 자신보다 컸던 원소'는 X 밖에 없습니다. 따라서 그냥 현재 X로 바뀌는 원소 앞쪽에 있는 X 개수를 세주고 빼면 됩니다. 이는 펜윅 트리를 이용해서 잘 해줄 수 있습니다.
시간복잡도는 맨 처음에 inversion도 세 줘야 하고, 그 뒤에도 X 하나가 늘어날 때 마다 펜윅 트리에 업데이트와 쿼리를 한번 날려야 하니(다 합치면 총 $O(N)$번 쿼리를 날립니다) $O(N \lg N)$입니다.
#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
#define double long double
/*#define cin file_in
#define cout file_out*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
const int MOD = 1000000007; // PLZ check
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
struct fenwick {
int sz; vector<ll> v;
fenwick(int _sz) : sz(_sz), v(_sz + 1) {}
void update(int i, ll val) {
for (; i <= sz; i += (i & -i))
v[i] += val;
}
ll query(int i, ll s = 0) {
for (; i>0; i -= (i & -i))
s += v[i];
return s;
}
};
int n;
int a[101010];
ll ans[101010];
int main() {
fio();
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pii> t;
for (int i = 1; i <= n; i++) t.emplace_back(a[i], i);
sort(all(t), greater<pii>());
fenwick f(n), g(n);
ll s = 0;
for (int i = 1; i <= n; i++) {
s += g.query(n) - (a[i] ? g.query(a[i]) : 0);
if(a[i]) g.update(a[i], 1);
}
int chk = n;
ans[n] = s;
for (auto [val, idx] : t) {
while (chk > val) {
chk--;
ans[chk] = ans[chk + 1];
}
ans[val] -= f.query(idx);
f.update(idx, 1);
}
while (chk > 0) {
chk--;
ans[chk] = ans[chk + 1];
}
for (int i = 0; i < n; i++)
cout << ans[i] << endl;
return 0;
}18875 Favorite Colors
문제 링크 : https://www.acmicpc.net/problem/18875
문제 지문이 굉장히 복잡한데, 그냥 편하게 말하면 정점을 최대한 많은 색으로 색칠하되 색깔 번호가 사전순 최소가 되도록 하면 됩니다. 단, 색이 같은 정점 $u$와 $v$가 있다면 임의의 간선 $(u,p)$와 $(v,q)$를 선택했을 때 $p$와 $q$도 색이 같아야 합니다.
일단 정점을 최대한 많은 색으로 색칠하려면 어떻게 해야 할 지 생각해봅시다. 만약 반드시 같은 색으로 색칠해야 하는 정점들의 관계를 모두 알 수 있다면, 그 정점들을 merge했다고 할 때 총 컴포넌트 개수가 답이 될 것입니다. 가장 먼저 생각해볼 수 있는 것은 $u=v$인 경우로 한 정점의 outdegree가 2 이상이라면 그 정점에서 직접적으로 간선이 꽂히는 정점들은 모두 같은 색으로 색칠되어야 한다는 것입니다. 그러면 그렇게 묶인 정점들의 집합을 $S$라고 할 때, $S$에 속하는 원소를 간선의 시작점으로 두는 모든 간선들의 끝점의 집합 $E$도 모두 같은 색으로 색칠되어야 할 것입니다. 이 과정은 계속 연쇄적으로 일어나지만, 어쨌던 간에 같은 색으로 색칠되어야 하는 정점들을 Union-Find로 관리해주면 두 집합이 합쳐질 때 마다 Union-Find의 집합 개수가 적어도 하나씩 줄어드므로($E$의 크기가 2개 이상일 때 집합을 합쳐야 하는데, 이때 모든 집합이 합쳐져 1개로 바뀌므로 적어도 하나씩 줄어듬) 이 합쳐지는 과정은 최대 $V$번 정도만 일어나게 됩니다. 물론 같은 집합을 합치려고 시도하는 것 까지 고려하면 대강 $E$번 정도 수행해야 하지만 큰 상관은 없습니다.
요약하면 다음과 같은 과정을 거치면 됩니다.
- 맨 처음에 $V$개의 벡터를 만들고, $i$번째 벡터를 집합 $s_i$에서 간선을 통해 바로 이동할 수 있는 집합의 번호를 담는 벡터라고 정의합니다.
- 벡터를 Compress하는 함수를 정의합니다; 집합 $s_i$에서 간선을 통해 바로 이동할 수 있는 집합들은 모두 같은 색으로 칠해져야 하므로 Union되어야 합니다. 따라서 벡터에 들어있는 모든 집합들을 Union해주면 됩니다. 그렇게 Union해주면 더 커진 집합 $x$ 하나만이 남는데, 합쳐지기 전 각 벡터에 있었던 원소(각 집합에서 간선을 타고 바로 이동할 수 있는 집합)또한 마지막으로 남는 집합의 벡터에 모두 합쳐줘야 합니다. $x$가 만들어지면서 $S=x$인 상황에서의 $E$인 $x$의 벡터는 원소가 2개 이상이게 될 수 있고, 따라서 연쇄적으로 Union되어야 하는 집합들이 생기므로 그 집합도 다시 Compress 해줘야 합니다.
- 저 같은 경우는 BFS 하는 느낌으로 구현했습니다. 자세한 내용은 코드를 참조해주세요.
위 알고리즘이 종료하게 되면 모든 같은 색으로 색칠되어야 하는 정점들은 한 컴포넌트에 존재하게 됩니다. 다른 컴포넌트에 존재하는 정점들은 다른 색으로 칠해도 무방함을 쉽게 보일 수 있습니다. 그 뒤는 정점 번호 작은 순서대로 보면서 직접 색칠해주면 됩니다.
시간 복잡도는 $O(V \lg V + E \lg E)$ 입니다.
#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
#define double long double
/*#define cin file_in
#define cout file_out*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
const int MOD = 1000000007; // PLZ check
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
struct UF {
vector<int> pa;
void init(int _n) {
pa.resize(_n + 1);
for (int i = 0; i <= _n; i++)
pa[i] = i;
}
int fi(int x) {
return pa[x] = pa[x] == x ? x : fi(pa[x]);
}
void un(int x, int y) { //x를 y에 합침
x = fi(x); y = fi(y);
if (x != y) pa[x] = y;
}
};
int n, m;
vector<int> out[201010];
UF uf;
queue<int> Q;
void compress(int x) {
x = uf.fi(x);
int chk = -1;
while (out[x].size() >= 2) {
auto t1 = out[x].back(); out[x].pop_back();
chk = t1;
auto t2 = out[x].back(); out[x].pop_back();
t1 = uf.fi(t1); t2 = uf.fi(t2);
out[x].push_back(t1);
if (t1 == t2) continue;
uf.un(t2, t1);
while (!out[t2].empty()) {
auto tmp = out[t2].back(); out[t2].pop_back();
out[t1].push_back(tmp);
}
}
if(chk>0) Q.push(chk);
}
int ck[201010], ax;
int main() {
fio();
cin >> n >> m;
for (int i = 0; i < m; i++) {
int t1, t2;
cin >> t1 >> t2;
out[t1].push_back(t2);
}
uf.init(n);
for (int i = 1; i <= n; i++) Q.push(i);
while (!Q.empty()) {
int h = Q.front(); Q.pop();
compress(h);
}
for (int i = 1; i <= n; i++) {
int t = uf.fi(i);
if(!ck[t]) ck[t] = ++ax;
cout << ck[t] << ends;
}
return 0;
}18876 Exercise
문제 링크 : https://www.acmicpc.net/problem/18876
순열을 계속 적용시키는 것은 결국 사이클 여러개로 분할한다는 것과 같습니다. 사이클의 크기가 $c_1, c_2, \cdots, c_t$일 때, $K= \text{lcm} (c_1,c_2,\cdots,c_t)$가 됩니다. 잘 생각해 보면 사이클은 우리가 원하는 대로 잘 분할할 수 있다는 것을 알 수 있습니다(구성적으로 보이면 됩니다). 따라서 문제는 $\sum c_i$가 $N$이 될 때 만들 수 있는 모든 $K$의 합을 구하는 문제로 바뀝니다.
$c_i$로 분할할 때 소인수가 공유되도록 사이클을 만들 이유는 없습니다. 다시 말해, 크기가 2인 사이클을 2개 만드는 것과 크기가 2인 사이클과 크기가 1인 사이클 2개를 만드는 것은 같습니다. 따라서 각 소인수 $p$ 별로 지수 $k$ 를 정했으면, 소인수 $p$를 가지는 $c_i$는 $p^k$ 하나만 있어야 합니다.
10000 이하의 소수 개수는 1300개정도 됩니다. 이 점을 활용해서 DP 점화식을 세워볼 수 있습니다. $\text{DP}[x][y]$를 $x$를 $\text{prime}[y]$ 이하의 소수로 적절히 분할하는 모든 경우에 대한 LCM의 합이라고 합시다. 그러면 $\text{DP}[i][j] = \sum_z (\text{DP}[x-\text{prime}[y] ^ z][y - 1] \times \text{prime}[y]^z)$이 되는 것을 볼 수 있습니다. $x-\text{prime}[y]^z$가 0 이상이어야 해서 $z$는 대부분의 $y$에 대해 0 또는 1에서만 정의되므로, 시간 안에 돌기에는 충분합니다.
#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
#define double long double
/*#define cin file_in
#define cout file_out*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
const int MOD = 1000000007; // PLZ check
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
ll N, M;
ll cache[10101][1300];
int chk[10101];
vector<int> pr;
void process() {
for (int i = 2; i <= 10000; i++) {
if (chk[i]) continue;
chk[i] = 1;
pr.push_back(i);
for (int j = i * 2; j <= 10000; j += i)
chk[j] = 1;
}
}
ll dp(int x, int y) {
if (x < 0) return 0;
if (y < 0) return 1;
ll& ret = cache[x][y];
if (ret != -1) return ret;
ret = 0;
ll pw = 1;
ret += dp(x, y - 1);
for (int z = 1; ; z++) {
pw *= pr[y];
if (pw > x) break;
ret += dp(x - pw, y - 1) * pw % M;
ret %= M;
}
return ret;
}
int main() {
fio();
process();
cin >> N >> M;
memset(cache, -1, sizeof(cache));
cout << dp(N, pr.size() - 1);
return 0;
}