SCPC 2021 1차 예선 풀이
SCPC 2021 1차 예선
1차 예선이 오후 3시부터 시작했는데, 3시에 바로 문제 풀러 가서 앞 3문제 푼 후에 저녁 먹고 좀 쉬다 나머지 2문제 풀었다. 전체 5문제로, SCPC를 참가해본 적이 없어서 쉬운 건지 어려운 건지 모르겠다.
1. 친구들
i번째 사람이 i+D[i]번째 사람과 친구를 맺을 때 파벌의 개수를 구하는 문제이다. 친구 관계를 맺을 때마다 DSU로 merge하고 전체 집합 개수를 세주면 된다.
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;
const int MAX = 1e5;
int N, D[MAX];
/*
DSU is from <https://github.com/atcoder/ac-library/>
*/struct DSU {
/*세부구현 생략 */
};
void solve(){
cin >> N;
rep(i, 0, N) cin >> D[i];
DSU dsu(N);
rep(i, 0, N){
if(i + D[i] < N) dsu.merge(i, i + D[i]);
}
cout << dsu.groups().size() << '\\n';
}
int main() {
cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
int TC;
cin >> TC;
rep(tc, 0, TC){
cout << "Case #" << tc + 1 << '\\n';
solve();
}
}
2. 이진수
- 사전순으로 가장 앞선 답을 찾아야 한다.
- 0-0, 1-0, 0-1, 1-1등의 조합을 고려하여 모순이 없도록 해야한다.
이 두 사실을 이용해 자명한 사실만을 뽑아내어 구현하면 된다. 주어진 문자열 B의 어느 한 원소가 0이라면 i-T와 i+T에 위치한 A의 두 원소는 무조건 0이어야 한다. 이걸 먼저 처리해주고, 1이라면 i-T나 i+T에 위치한 A의 원소 중 하나는 무조건 1이어야 하니 두 위치의 원소가 모두 0인 경우가 없도록, 그리고 사전순으로 앞서도록 처리해 주면 된다. 자세한 구현은 소스코드를 보자.
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;
const int MAX = 50002;
int N, T, C[MAX];
string S;
char E[MAX];
void solve(){
cin >> N >> T >> S;
fill(C, C + N + 1, 0);
fill(E, E + N + 1, 0);
rep(i, 0, N){
if(S[i] == '0'){
if(i - T >= 0) E[i - T] = '0';
if(i + T < N) E[i + T] = '0';
}
}
rep(i, 0, N){
if(S[i] == '1'){
if(i >= T && E[i - T] == '1') continue;
if(i + T < N && E[i + T] == 0){
E[i + T] = '1';
} else {
assert(i - T >= 0);
E[i - T] = '1';
}
}
}
rep(i, 0, N) if(E[i] == 0) E[i] = '0';
cout << E << "\\n";
}
int main() {
cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
int TC;
cin >> TC;
rep(tc, 0, TC){
cout << "Case #" << tc + 1 << '\\n';
solve();
}
}
3. No Cycle
일단 주어진 그래프를 잘 만들어 놓고, K개의 쿼리를 처리해야 한다. 근데 사전순으로 앞서게 출력해야 하므로 가능한 v->u가 아닌 u->v 방향으로 간선을 만들어야 한다. 여러 경우의 수 중 u->v가 사이클을 만들며 v->u가 사이클을 만드는 경우는 불가능하다. 애초에 그 전부터 v->u 경로와 u->v 경로가 존재했다는 뜻이므로, 이 쿼리를 처리하기 전부터 u와 v를 잇는 사이클이 만들어져 있다는 뜻이기 때문이다. 그래서 처음부터 모순이 있는 그래프를 주지 않는 한 일단 모순이 생겨서 답이 안 나오는 경우는 안 나올 것이고, 뒤의 쿼리는 미래의 알고리즘이 잘 처리해 줄것이라 생각하고(적어도 앞에서 무슨 뻘짓을 하든 모순이 생겨 답이 안 나오는 경우는 안 생기니까..) 앞에서는 사전순으로만 최대한 앞서게 처리해주면 된다. 즉, 일단 u->v 만들어 놓고, 사이클 탐색하고, 모순 생기면 v->u 간선을 대신 만들면 된다.
사이클 탐색은 보통 dfs를 쓸텐데, 매 쿼리마다 dfs를 돌리면 시간복잡도가 걱정될 수 있지만 입력 크기가 너무 작아서 상관없다.
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;
const int MAX = 505;
int N, M, K, u, v, vis[MAX], fin[MAX], cnt;
bool cycle;
char ans[MAX * 4];
stack<int> S;
vector<int> adj[MAX];
int dfs(int u){
vis[u] = ++cnt;
S.push(u);
int res = vis[u];
for(auto v: adj[u]){
if(vis[v] == 0) res = min(res, dfs(v));
else if(!fin[v]) {
cycle = 1;
res = min(res, vis[v]);
}
}
if(res == vis[u]){
while(1){
int t = S.top(); S.pop();
fin[t] = 1;
if(t == u) break;
}
}
return res;
}
inline bool query(){
fill(vis, vis + N, 0);
fill(fin, fin + N, 0);
cnt = cycle = 0;
rep(i, 0, N) if(vis[i] == 0) dfs(i);
return cycle;
}
void solve(){
cin >> N >> M >> K;
rep(i, 0, N) adj[i].clear();
fill(ans, ans + K + 1, 0);
rep(i, 0, M){
cin >> u >> v; u--; v--;
adj[u].eb(v);
}
rep(i, 0, K){
cin >> u >> v; u--; v--;
adj[u].eb(v);
if(query()){
assert(adj[u].size() > 0);
adj[u].erase(--adj[u].end());
adj[v].eb(u);
ans[i] = '1';
} else ans[i] = '0';
}
cout << ans << "\\n";
}
int main() {
cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
int TC;
cin >> TC;
rep(tc, 0, TC){
cout << "Case #" << tc + 1 << '\\n';
solve();
}
}
4. 예약 시스템
삽질할 필요가 없는데 매우 오래 삽질했던 문제다. 홀-홀, 짝-짝, 홀-짝 섞여서 나오는 경우를 고려해서 여러 답의 후보를 뽑아낸 다음 그 중 최선의 값을 출력하면 된다. 구현 중간에 중복이 되서 아주 약간 비효율적인 부분이 있긴 한데 솔직히 이거 짤 때는 삽질 너무 오래한 것 때문에 짜증이 나서 좀 길어지더라도 명쾌한 소스코드를 짜고 싶었다. 처음에는 대충 완전히 틀리지는 않은 로직으로 짰는데 전체 구조가 명료하지 않다보니 도대체 어디서 뭘 약간 잘못한 건지는 모르겠고, 반례 입력 넣어봐서 돌려봐도 반례를 찾을 수가 없고, 점수는 만점이 안 나와서 꽤 오래 고생하다 그냥 싹 다 갈아엎고 다시 짰더니 만점 맞았다.
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;
struct GRP{
GRP(): GRP(5, 0, 0, 0, 0) {}
GRP(int S, ll a, ll b, ll c, ll d): S(S), a(a), b(b), c(c), d(d) {}
int S;
ll a, b, c, d;
bool operator < (const GRP& other) const {
return c + d > other.c + other.d;
}
};
vector<GRP> odd, even;
int N, M, S;
void solve(){
ll ret = 6e18;
ll ans = 0;
cin >> N >> M;
odd.clear();
even.clear();
rep(i, 0, N){
cin >> S;
auto& v = S % 2 ? odd : even;
vector<ll> V(S);
rep(j, 0, S) cin >> V[j];
sort(all(V));
v.eb(S, V[0], V[1], V[2], V[3]);
}
for(auto& grp: odd) ans += grp.a * 2 + grp.b + grp.c + grp.d;
for(auto& grp: even) ans += grp.a + grp.b + grp.c + grp.d;
sort(all(odd));
sort(all(even));
if(odd.size() >= 2){
ans -= odd[0].c + odd[0].d + odd[1].c + odd[1].d;
if(even.empty()){
ret = min(ret, ans);
} else {
if(odd.size() >= 4){
ret = min(ret, ans);
} else {
ll tmp = 0;
for(auto& grp: even) tmp += grp.a + grp.b;
ret = min(ret, ans + tmp);
}
}
ans += odd[0].c + odd[0].d + odd[1].c + odd[1].d;
}
if(!odd.empty() && !even.empty()){
ret = min(ret, ans - (odd[0].c + odd[0].d + even[0].c + even[0].d));
}
if(even.size() >= 2){
ret = min(ret, ans - (even[0].c + even[0].d + even[1].c + even[1].d));
}
cout << ret << "\\n";
}
int main() {
cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
int TC;
cin >> TC;
rep(tc, 0, TC){
cout << "Case #" << tc + 1 << '\\n';
solve();
}
}
5. 차이
i j d로i j거리(방향을 고려함)을d로 설정하라는 쿼리i j로i j거리(방향을 고려함)을 출력하라는 쿼리이 두 쿼리가 들어온다. 2번 쿼리는i, j가 공통된 트리 루트를 가지고 있다면 루트에서 i까지 거리와 루트에서 j까지 거리만을 이용해 나타낼 수 있다. 1번 쿼리는i j가 공통된 트리 루트를 가지도록 만들고 거리를 적절히 설정하면 된다. 만약 이미 두 정점이 공통된 트리 루트를 가지고 있는데 거리d가 만족되지 않는다면 모순이 일어난 것이므로 이 트리 전체에Invalid을 메모하면 된다.
대충 풀이의 개요는 이렇게 되나, 여기에서 시간 안에 문제를 풀려면 조금 더 생각을 해야 한다. 일단 2번 쿼리는 만약 i,j가 트리 루트와 가까이(간선 하나만을 사이에 두고) 존재한다면 매우 빨리 구할 수 있다. 그리고 1번 쿼리는 i, j 각각의 트리 루트를 최대한 빨리 구하고 잘 합치면 되는데, 시간복잡도를 충분한 정도로 낮추려면 DSU를 사용하고 Union-By-Rank까지 사용해줘야 한다. (그럼 상술한 2번 쿼리 처리방법을 다시 보면, 하려고 했던 게 Path Compression라는 것을 알 수 있다.) 3번 쿼리는 트리 전체에 Invalid를 메모하는 방법으로는 그냥 트리의 루트에만 Invalid 플래그를 꽂아주면 된다.
구현을 좀 더 구체화해보자. 일단 Union-By-Rank가 필요하므로 DSU Tree의 크기를 저장할 배열 하나가 필요하다(sz[u]). 또한, 어떤 정점의 부모를 저장할 배열 하나가 필요하다(par[u]). 그리고 거리를 처리해야 하는데, 어떤 정점 u가 있을 때 그 정점 바로 위의 부모까지의 거리만을 저장하는 배열 dist[u]가 있으면 된다. 그리고 어떤 정점이 Invalid한지 체크하는 배열 isValid[u]가 필요하다.
dist[u]는 dsu.find(u)에서 진행하는 Path Compression 도중 노드 u를 최상위 루트 바로 아래에 달아버리는 데 사용할 수 있다. 만약 u의 부모가 v면 (루트에서 v까지 거리)+(v부터 u까지 거리)만 해주면 (루트에서 u까지 거리)를 바로 구할 수 있기 때문이다. dsu.find 함수에서 Path Compression도 진행하는 겸 재귀적인 방식으로 dist[u]를 적절히 업데이트해주면 된다.
자세한 구현은 아래 소스코드를 참고하자. 내 소스코드에서는 sz과 par 배열을 합치고 dist과 isValid배열을 합쳤다. 굳이 배열을 4개나 둘 필요 없으니까.
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;
const int INF = 2e9;
int N, K, op, i, j, d;
/*
DSU is from <https://github.com/atcoder/ac-library/>
*/struct DSU {
// if u is root : par[u] = -(size of tree)// else: par[u] = parent of upublic:
DSU() : N(0) {}
explicit DSU(int N) : N(N), par(N, -1), dist(N, 0) {}
int merge(int u, int v, int d) {
assert(0 <= u && u < N);
assert(0 <= v && v < N);
find(u); find(v);
d += dist[u] - dist[v];
u = find(u); v = find(v);
if (u == v) return u;
if (-par[u] < -par[v]) swap(u, v), d *= -1;
par[u] += par[v];
par[v] = u;
dist[v] = d;
return u;
}
int find(int u) {
assert(0 <= u && u < N);
if (par[u] < 0) return u;
int p = find(par[u]);
dist[u] = dist[par[u]] + dist[u];
return par[u] = p;
}
bool same(int u, int v) {
assert(0 <= u && u < N);
assert(0 <= v && v < N);
return find(u) == find(v);
}
int size(int u) {
assert(0 <= u && u < N);
return -par[find(u)];
}
int getDistance(int u, int v){
find(u); find(v);
return dist[v] - dist[u];
}
vector<vector<int> > groups() {
vector<int> roots(N), groups(N);
for (int i = 0; i < N; i++) {
roots[i] = find(i);
groups[roots[i]]++;
}
vector<vector<int> > result(N);
for (int i = 0; i < N; i++) {
result[i].reserve(groups[i]);
}
for (int i = 0; i < N; i++) {
result[roots[i]].push_back(i);
}
result.erase(
remove_if(result.begin(), result.end(), [&](const vector<int>& v) { return v.empty(); }), result.end()
);
return result;
}
void makeInvalid(int u){
u = find(u);
dist[u] = INF;
}
bool isInvalid(int u){
u = find(u);
return dist[u] == INF;
}
private:
int N;
vector<int> par, dist;
};
void solve(){
cin >> N >> K;
DSU dsu(N);
rep(_, 0, K){
cin >> op;
if(op == 1){
cin >> i >> j >> d; i--; j--;
if(!dsu.same(i, j)) dsu.merge(i, j, d);
else if(dsu.getDistance(i, j) ^ d) dsu.makeInvalid(i);
} else {
cin >> i >> j; i--; j--;
if(!dsu.same(i, j)) cout << "NC\\n";
else if(dsu.isInvalid(i) || dsu.isInvalid(j)) cout << "CF\\n";
else cout << dsu.getDistance(i, j) << "\\n";
}
}
}
int main() {
cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
int TC;
cin >> TC;
rep(tc, 0, TC){
cout << "Case #" << tc + 1 << '\\n';
solve();
}
}