SCPC 2025 Round 1
7월 11~12일 진행된 SCPC 1차 예선에 참가했습니다. 5문제가 출제되었으며 모두 해결하여 1150점을 받았습니다. 각 문제에 대한 저의 풀이는 다음과 같습니다.
1. 거스름돈
그리디하게 큰 금액부터 돈을 거슬러주는 것을 구현하면 됩니다.
2. 폭탄
왼쪽 폭탄을 L으로 가져가고 오른쪽 폭탄을 0으로 가져기는 것은 안 좋습니다. 따라서 그리디하게 어느 포인트를 잡아서 그 왼쪽 폭탄은 0으로, 오른쪽 폭탄은 L으로 가져간다고 생각하고 풀면 됩니다. 선형에 풀기 위해서, 왼쪽부터 몇 개의 폭탄을 0으로 가져오는 데 드는 거리의 prefix sum과 오른쪽부터 L으로 가져가는 suffix sum을 미리 구해줄 수 있습니다. 엣지케이스 몇 가지를 주의해서 처리합시다.
3. 십진수
주어진 수 이하의, 0, 1, 2로만 이루어진, 가장 큰 수를 찾아봅시다. 그 수를 삼진법으로 읽으면, 그 수 이하의 삼진수를 십진법으로 읽은 수는 모두 쓸 수 있는 수들입니다. 즉, 그 수를 삼진법으로 읽고 십진법으로 변환해 출력하기만 하면 됩니다.
‘주어진 수 이하의, 0, 1, 2로만 이루어진, 가장 큰 수’와 ‘수를 읽어서 2 이상인 자릿수를 다 2로 바꾼 수’는 다름을 조심합시다.
4. 상점
만약 대응 관계가 정해진다면 (즉 어떤 파란 집 사람이 빨간 상점에 출근할 지 정하면) 이동거리의 합은 왼쪽부터 색깔별로 그리디하게 잡아주기만 해도 됩니다.
(저는 수직선을 두 개 긋고 각각에 집과 상점을 올린 뒤 대응되는 집-상점 쌍 사이에 간선을 그리는 것을 생각했습니다. 이때 같은 색의 다른 두 집에서 나온 간선이 한 점에서 만나는 경우는 두 집을 swap해서 교점을 없애주는 것에 비해 suboptimal합니다.)
따라서, 그리디하게 매칭할 때 최소 거리의 합을 2번 문제처럼 prefix/suffix sum으로 저장한 뒤, 빨간 상점들마다 ‘그 빨간 상점에 파란 집 사람이 출근할 때 그 사람의 이동 거리’와 그 앞뒤의 누적합을 더해주면 선형에 이동거리의 합으로 가능한 모든 값을 구할 수 있습니다. 그중 최솟값을 내면 됩니다.
5. MST
크루스칼이 옳다는 사실에서 생각보다 많은 것을 끌어다 쓸 수 있습니다.
유파를 선언해, 적당히 가중치가 큰 간선 하나를 골라 그 간선을 유니언하고 그 간선보다 가중치가 작은 간선들에서 (혹은 그냥 나머지 간선 전부에 대해) 크루스칼을 돌리는 것을 생각합시다. 이때 만들어지는 신장 트리는 가중치 최대최소의 차가 (처음에 임의로 고른 간선 - 크루스칼에서 처음으로 고른 간선) 이고, 가중치의 합은 크루스칼을 통해 자연스럽게 구할 수 있게 됩니다. 즉, 가중치가 가장 큰 간선을 선택해 준다면 나머지 간선들으로 크루스칼을 돌린 MST는 문제의 조건을 만족하는 신장 트리입니다.
이떄, 주어진 그래프의 (그래프 전체에서 크루스칼을 통해 일반적으로 구한) MST에 어떤 간선을 하나 추가하는 것을 생각합시다. 트리에 정확히 하나의 사이클이 생기게 됩니다. 이 사이클의 간선 중 (직접 추가한 것 빼고) 가장 가중치가 큰 것을 삭제합시다. 이렇게 만들어진 새로운 스패닝 트리는 위의 방법(크루스칼)으로 그리디하게 만들어질 수 있는 스패닝 트리 중 하나임을 어렵지 않게 확인할 수 있습니다.
트리의 두 정점에 대해 두 정점 사이 가장 무거운 간선을 찾는 것은 LCA로 전처리하면 질의 당 로그 시간에 구할 수 있으므로, 문제를 해결할 수 있습니다.
후기
예년의 문제들을 보고 들어갔는데, 최근의 1차 예선들은 어떤 스탠다드 문제를 풀어봤으면 / 어떤 알고리즘을 알고 있으면 풀 수 있는 문제가 많다고 느꼈습니다. 저는 개인적으로 여기에 다소 약합니다. 그래서 만점을 받지 못할 수도 있겠다는 생각 혹은 시간을 꽤나 많이 박아야겠다는 생각으로 대회에 임했고, 그런 것치고 생각보다 풀이를 내는 데 시간이 오래 걸리지 않았습니다.
4번 문제까지는 문제의 풀이를 생각하는 데까지 몇 분 걸리지 않았습니다. 5번 문제에서는 초반의 발상에서 말렸는데, ‘MST에서 가중치 큰 간선을 하나 넣고 사이클 없애주기’만 해도 정답이 될 수 있는 스패닝 트리(의 크기)를 모두 확인할 수 있다는 점을 못 알아채서 약간 고생했습니다. 사실 오프라인 동적 MST를 박을 생각까지 했습니다.
조금 더 자세히 이야기하자면 - 크루스칼의 그리디가 작동한다는 사실을 써먹는 문제는 많기에, 이 문제를 처음 봤을 때도 아무래도 ‘크루스칼 그리디를 적절하게 응용해 써먹는 문제’이겠다는 생각은 바로 했습니다. 이걸 구체화하다가 한 방향으로 샜는데, 여기에 너무 깊게 들어가서 빠져나오는 데 시간을 다소 오래 썼습니다. 5번 문제는 30분에서 1시간 정도 생각만 한 것 같습니다.
그럼에도 능지만 있으면 정말 기초적인 사전지식만으로도 모든 문제를 해결할 수 있어서 개인적으로는 다행이었습니다. 사실 발상보다는 구현 파트에서 많이 절었습니다. ‘시간 패널티 없이 제출 횟수로 동점을 가르는’ 방식이 제게는 그리 유리하지 않은 방식인 것 같습니다. 특히 5번 문제의 경우 초반 풀이가 틀린 이슈로 제출 횟수 몇 번을 버리고 시작했는데, 그 다음에 구현한 제 솔루션이 Segfault를 내어 디버깅하는 것이 다소 어려웠습니다.
SCPC에서는 Segfault가 나면 이것이 전반적인 MLE인지 (공간복잡도가 선형로그라 가능성이 있었습니다), 스택 메모리가 터진 것인지 (유파부터 DFS까지 다 재귀함수로 구현했으니까 역시 가능성이 있었습니다), 배열 인덱스를 잘못 접근했는지(저는 제 구현 실력을 못 믿습니다), 혹은 그냥 구현 미스에 의한 UB인지 알려주지 않습니다. 아무리 로컬에서 반례를 만들어 넣어도 코드가 안 터졌고, 그래서 다양한 컴파일 환경에서 시험하기 위해 코드포스와 앳코더의 내장 invocation 시스템에서 코드를 돌렸습니다. 앳코더에서 예제부터 틀리는 것을 보고 코드가 UB를 내는 것을 인지했고 (전역변수 하나의 테케별 초기화를 빼먹었습니다), 그제서야 고쳐서 AC를 냈습니다.
사실 SCPC 1차예선은 ‘1번만 풀 수 있어도 통과한다’는 말이 있을 만큼 컷이 널널합니다. 그럼에도 SCPC 시스템에 익숙해지기 위해 (그리고 그래도 나름 오렌지인데 1차도 올솔을 못하면 어떡합니까) 만점을 목표로 했고, 그러길 잘한 것 같습니다. 전 글에 나왔던 문제점인 ‘구현에 오류가 많고 디버깅을 잘 못 한다’는 점이 아주 잘 드러났습니다. (제출 횟수에 대한 패널티가 없는 KOI나, 난이도에 비해 구현이 매우 짧은 코포/앳코더에서는 잘 안 보였지만, ICPC 같은 대회에서는 중요한 문제입니다…)
고로, 구현 실력을 늘려야 합니다. 보다 정확히, 오류가 안 날 만한 방향으로 - 혹은 적어도 오류가 난 것을 빠르게 확인할 수 있는 방향으로 - 깔끔하게 구현을 하는 능력을 길러야겠습니다.
구현
아마 템플릿에 #define int long long이 붙어있었을 겁니다.
1. 거스름돈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[201010];
void f(){
int n,i,t; cin>>n;
int x=0,y=0,z=0;
for(i=0;i<n;i++)cin>>a[i];
for(i=0;i<n;i++){
t=a[i];
if(t==500) ++x;
if(t==1000){
if(x==0)break;
--x; ++y;
}if(t==5000){
++z;
while(t>1000&&y>0)--y, t-=1000;
while(t>500&&x>0)--x, t-=500;
if(t>500)break;
}
} cout<<i<<endl;
}
2. 폭탄
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[201010],x[201010],y[201010];
void f(){
int n,l,i; cin>>n>>l;
for(i=0;i<n;i++) cin>>a[i];
if(n==1){
cout<<min(l,a[0]*2)<<endl;
return;
}
x[0]=a[0]*2;
for(i=1;i<n;i++)x[i]=x[i-1]+a[i]*2;
y[n-1]=(l-a[n-1])*2;
for(i=n-2;i>=0;i--)y[i]=y[i+1]+(l-a[i])*2;
int mn=min({x[n-1],x[n-2]+l,l+y[1]});
for(i=1;i<n-1;i++)mn=min(mn,x[i-1]+y[i+1]+l);
cout<<mn<<endl;
}
3. 십진수
1
2
3
4
5
6
7
8
void f(){
string s; cin>>s; int ans=0,t,tt=0;
for(auto i:s){
ans*=3; t=i-'0';
ans+=max(tt,min(t,2ll)); ans%=1000000007ll;
if(t>2)tt=2;
} cout<<ans<<endl;
}
4. 상점
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int x0[201010],x1[201010];
pair<int,int>y[201010];
int z[201010];
void f(){
int n,r,i,j; cin>>n>>r;
for(i=0;i<n-r;i++)cin>>x0[i];
for(i=0;i<r;i++)cin>>x1[i];
for(i=0;i<n;i++){
cin>>y[i].first;
if(i<n-r-1) y[i].second=0;
else y[i].second=1;
} sort(y,y+n); sort(x0,x0+n-r); sort(x1,x1+r);
int cur=0,id0=n-r-1,id1=r-1,bd=-1,ans=-1;
for(i=n-1;i>=0;i--){
z[i]=cur;
if(y[i].second==0){
cur+=abs(y[i].first-x0[id0]);
id0--;
}else{
if(id1<0){
bd=i;
break;
}
cur+=abs(y[i].first-x1[id1]);
id1--;
}
} cur=0; id0=id1=0;
for(i=0;i<n;i++){
if(y[i].second==0){
cur+=abs(y[i].first-x0[id0]);
id0++;
}else{
if(ans==-1||ans>cur+z[i]+abs(y[i].first-x0[id0])) ans=cur+z[i]+abs(y[i].first-x0[id0]);
cur+=abs(y[i].first-x1[id1]);
id1++;
}
} cout<<ans<<'\n';
}
5. MST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
vector<pair<int,pair<int,int>>>sel;
vector<pair<int,int>>adj[101010];
int p[101010];
int mx[101010][20],par[101010][20],dep[101010];
int find(int x){
if(p[x]==x)return x;
return p[x]=find(p[x]);
}
void union_(int x,int y){
x=find(x); y=find(y);
if(x!=y)p[x]=y;
}
void dfs(int x, int pp, int w){
par[x][0]=pp;
mx[x][0]=w;
for(auto u:adj[x]){
if(u.first!=pp){
dep[u.first]=dep[x]+1;
dfs(u.first,x,u.second);
}
}
}
int query(int u, int v){
if(dep[u]<dep[v])swap(u,v);
int mxt=0,diff=dep[u]-dep[v],i;
for(i=0;i<20;i++)if(diff&(1LL<<i)){
mxt=max(mxt,mx[u][i]);
u=par[u][i];
} if(u==v)return mxt;
for(i=19;i>=0;i--){
if(par[u][i]!=par[v][i]){
mxt=max(mxt,mx[u][i]);
mxt=max(mxt,mx[v][i]);
u=par[u][i];
v=par[v][i];
}
} mxt=max({mxt,mx[u][0],mx[v][0]});
return mxt;
}
void f(){
int n,m,i,j; sel.clear();
cin>>n>>m; for(i=0;i<n;i++)p[i]=i,adj[i].clear();
for(i=0;i<m;i++){
int u,v,w; cin>>u>>v>>w; u--; v--;
if(u>v)swap(u,v);
sel.push_back({w,{u,v}});
} sort(sel.begin(),sel.end());
if(n==2){
cout<<"0 "<<sel[0].first<<endl; return;
}
vector<int>mst; int d=0;
for(i=0;i<m;i++){
int x=find(sel[i].second.first),
y=find(sel[i].second.second);
if(x!=y){
union_(x,y);
mst.push_back(i);
d+=sel[i].first;
}
} for(auto x:mst){
int u=sel[x].second.first,
v=sel[x].second.second;
adj[u].push_back({v,sel[x].first});
adj[v].push_back({u,sel[x].first});
}
for(i=0;i<n;i++)for(j=0;j<20;j++)mx[i][j]=0,par[i][j]=n;
for(i=0;i<n;i++)dep[i]=0;
dfs(0,0,0);
for(i=1;i<20;i++)for(j=0;j<n;j++){
int mid=par[j][i-1];
if(mid==n){
par[j][i]=n;
mx[j][i]=mx[j][i-1];
}else{
par[j][i]=par[mid][i-1];
mx[j][i]=max(mx[j][i-1],mx[mid][i-1]);
}
}
multiset<int>x,xi;
for(auto i:mst){
x.insert(sel[i].first);
xi.insert(-sel[i].first);
}
pair<int,int> ans={-*xi.begin()-*x.begin(),d};
for(i=0;i<m;i++){
int u=sel[i].second.first,v=sel[i].second.second,w=sel[i].first;
int xx=query(u,v),y,z;
x.erase(x.find(xx)); xi.erase(xi.find(-xx));
x.insert(w); xi.insert(-w);
y=-*xi.begin()-*x.begin();
z=d-xx+w;
if(y>ans.first || (y==ans.first && z<ans.second)){
ans.first=y; ans.second=z;
} x.erase(x.find(w)); xi.erase(xi.find(-w));
x.insert(xx); xi.insert(-xx);
} cout<<ans.first<<" "<<ans.second<<endl;
}