올해는 현대모비스 알고리즘 경진대회 예선과 일정이 겹쳤지만, 나는 240점대의 점수를 받고 떨어져서 상관없었다.(학생부 컷은 빠른 300점, 일반부 컷은 180점대였다고 한다.)
올해 SCPC 문제는 1, 2, 3번 문제가 작년에 비해 쉬워서 예선이지만 방심하면 안 되겠다고 생각했다.
5번 문제를 분명 맞게 푼 것 같은데, 계속 TLE를 받다가 제출 기회 10번을 모두 사용해버렸다.
대회가 끝나고 여러 후기를 보니, 내가 시도했던 방법들로 만점을 받은 분들이 많았다. 뭐가 잘못 된 걸까...
풀이
1. A보다 B가 좋아
모든 A와 A 사이에 B가 최소 2개 이상 들어있으면 조건을 만족시킬 수 있다.
$O(N)$에 잘 돌아간다.
코드
#include <bits/stdc++.h>
using namespace std;
char s[300003];
void solve(){
int n;scanf("%d %s",&n,s);
int l=0,r,ans=0;
while(l<n&&s[l]=='B')l++;
r=l;
while(r<n){
r++;while(r<n&&s[r]=='B')r++;
if(r>=n)break;
ans+=max(0,2-(r-l-1));
l=r;
}
printf("%d\n",ans);
}
int main(){
setbuf(stdout, NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}2. 배달
$|d-c| + |c-b| + |b-a| + |a-d| = (d-a)*2$라서, 한번 배달을 나갈 때 무게가 가장 큰 물건과 가장 작은 물건을 들고 나가면 된다.
정렬이 필요해서 시간복잡도는 $O(NlogN)$.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;scanf("%d",&n);
vector<ll> a(n);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
sort(a.begin(),a.end());
ll ans=0,x=n/4,l=0,r=n-1;
while(x--)ans+=(a[r--]-a[l++])*2;
printf("%lld\n",ans);
}
int main(){
setbuf(stdout, NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}3. 보안망 점검
추가 라인으로 연결된 2개의 장비는 항상 3개의 라인으로 이어져 있고, 나머지 장비들은 2개의 라인으로 이어져 있다.
위의 성질을 이용해서 2개의 장비를 찾아서 그 장비들을 기준으로 망을 나눠보면, 각각 x개 / y개의 라인이 선형으로 이어진 모양이 된다.
이때 x개의 라인 중 2개의 라인을 파괴하면 망이 분리되고, 마찬가지로 y개의 라인 중 2개의 라인을 파괴하면 망이 분리되므로, 답은 $_xC_2 + _yC_2$가 된다.
라인의 수도 $N$에 비례하므로, 시간복잡도는 $O(N)$. (별 생각없이 구현해서 코드에 상수가 크게 붙은 것 같다.)
코드
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
void solve(){
int n;scanf("%d",&n);
vector<pii> edge;
vector<vector<int>> graph(n+1);
for(int i=0;i<=n;i++){
int x,y;scanf("%d%d",&x,&y);
graph[x].push_back(y),graph[y].push_back(x);
edge.push_back({x,y});
}
int X=-1,Y=-1;
bool deleted=0;
for(int i=1;i<=n;i++){
if(graph[i].size()!=3)continue;
if(X==-1)X=i; else Y=i;
}
vector<vector<int>> tmp(n+1);
for(auto [x,y]:edge){
if(!deleted&&((X==x&&Y==y)||(Y==x&&X==y))){
deleted=1;continue;
}
tmp[x].push_back(y),tmp[y].push_back(x);
}
vector<bool> vis(n+1);
vis[X]=1,vis[tmp[X][0]]=1;
int cnt=2;
queue<int> q;q.push(tmp[X][0]);
while(!q.empty()){
int cur=q.front();q.pop();
if(cur==Y)break;
for(int nx:tmp[cur])
if(!vis[nx])vis[nx]=1,q.push(nx),cnt++;
}
ll x=cnt-1,y=n-cnt+1;
printf("%lld\n",x*(x-1)/2+y*(y-1)/2);
}
int main(){
setbuf(stdout, NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}4. 딱 맞게
- $Max(F(A, B))$ 가 최소가 되는 경우는, 집합 A, B가 정렬된 상태에서 순서대로 대응되는 경우이다.
- 이때 $Max(F(A, B))$ 값이 L 초과라면 불가능하므로 -1을 출력한다.
이제 $Max(F(A, B))$ 값이 L 이하인 모든 경우를 확인할 건데, 아래 그림을 보자. (A, B는 정렬된 상태이다.)
만약 그림과 같이 대응된 경우, $Max(F(A, B)) = 10$으로 빨간 선에 의해 결정된다.
어차피 나머지 선들은 $Max(F(A, B))$ 값에 영향을 주지 않으므로, 아래와 같이 대응시켜도 똑같다. (나머지 선들은 차이가 최소가 되도록 대응시킨다.)
즉 빨간 선을 a[x] ↔ b[y]라고 하면, [x,y]내의 구간은 a[x+1] ↔ b[x], a[x+2] ↔ b[x+1], ..., a[y] ↔ b[y-1]로 대응시키고, 나머지 구간은 a[i] ↔ b[i]로 대응시키면 된다.
이것들의 최댓값은 range maximum query로 구할 수 있다(나는 세그먼트 트리를 사용했다).
이제 모든 [x,y] 쌍을 확인해야 하는데, 만약 어떤 x에 대한 y의 위치를 알고 있다면 x+1에 대한 위치는 반드시 y 이상인 구간에 속한다. 따라서 [x,y] 쌍을 스위핑으로 찾을 수 있다.
마지막으로 위 그림은 x<y인 경우만 고려했으므로, x>y인 경우도 같은 방법으로 구해주면 된다.
시간복잡도는 스위핑에 $O(N)$, 구간 최댓값 쿼리에$O(logN)$ 이므로 $O(NlogN)$.
코드
#include <bits/stdc++.h>
using namespace std;
const int sz=1<<17;
int a[sz],b[sz],arr[2][sz<<1];
void update(bool x,int i,int val){
i+=sz,arr[x][i]=val;
while(i>1)i>>=1,arr[x][i]=max(arr[x][i<<1],arr[x][i<<1|1]);
}
int query(bool x,int s,int e,int node=1,int ns=0,int ne=sz-1){
if(e<ns||ne<s)return 0;
if(s<=ns&&ne<=e)return arr[x][node];
int mid=(ns+ne)>>1;
return max(query(x,s,e,node<<1,ns,mid),query(x,s,e,node<<1|1,mid+1,ne));
}
void solve(){
memset(arr,0,sizeof(arr));
int n,L;scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
sort(a+1,a+1+n),sort(b+1,b+1+n);
int ans=0;
for(int i=1;i<=n;i++){
if(abs(a[i]-b[i])>L){printf("-1\n");return;}
ans=max(ans,abs(a[i]-b[i]));
}
for(int i=1;i<n;i++){
update(0,i,abs(a[i]-b[i+1]));
update(1,i,abs(a[i+1]-b[i]));
}
int A=1,B=1;
while(1){
B++;
if(A>n||B>n)break;
while(query(1,A,B-1)>L||abs(a[A]-b[B])>L)A++;
ans=max({ans,query(1,A,B-1),abs(a[A]-b[B])});
}
A=1,B=1;
while(1){
A++;
if(A>n||B>n)break;
while(query(0,B,A-1)>L||abs(a[A]-b[B])>L)B++;
ans=max({ans,query(0,B,A-1),abs(a[A]-b[B])});
}
printf("%d\n",ans);
}
int main(){
setbuf(stdout, NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}5. 스퀘어 (만점 X)
두 가지 풀이를 시도했다가 모두 TLE를 받아서, 각각의 풀이와 코드를 따로 작성했다.
일단 두 풀이의 공통 아이디어는 다음과 같다.
- $a_i = 1$이거나 $n<a_i$인 경우 스퀘어가 불가능하므로 무시한다.
- $a_i = 2$가 스퀘어된 경우 추가로 4가 스퀘어될 수 있는 지 확인해야 하는데, 2 → 4 → 16 → 256 → 65536(n초과)이므로 추가 연산 횟수가 매우 작아서 거의 상수로 취급해도 된다고 생각했다.
- $n \leq 50000, Q \leq 50000$이므로, $O(n\sqrt{n})$ 또는 $O(Q\sqrt{n})$ 안에 코드가 동작해야 한다고 생각했다.
1번 풀이)
mo's 알고리즘을 이용하여 쿼리를 정렬해 순서를 잘 정하여 평균 $\sqrt{n}$회의 연산을 했다.
따라서 시간복잡도는 $O(n+Q(\sqrt{n}+logQ))$인데, 상수를 줄이려고 long long → int로 고치고, vector<int>를 전역변수로 바꾸고, % 연산을 비교 연산으로 바꾸는 등 다양한 시도를 해봤으나 모두 TLE를 받았다. (대체 왜...?)
코드 (mo's)
#include <bits/stdc++.h>
using namespace std;
typedef array<int,3> tup;
typedef long long ll;
void solve(){
int n;scanf("%d",&n);
int root=sqrt(n);
vector<ll> candidate(50001);
vector<ll> a(n+1);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]>50000||a[i]==1)a[i]=0;
candidate[a[i]]++;
}
for(int i=2;i*i<=50000;i++)candidate[i*i]+=candidate[i]/i;
for(int i=1;i<=n;i++)
if(a[i]<=1||candidate[a[i]]<a[i])a[i]=INT_MAX;
int q;scanf("%d",&q);
vector<tup> v(q);
for(int i=0;i<q;i++){
int l,r;scanf("%d%d",&l,&r);
v[i]={l,r,i};
}
sort(v.begin(),v.end(),[&](tup a,tup b){
auto [al,ar,_]=a;auto [bl,br,__]=b;
ar/=root,br/=root;
return ar==br?al<bl:ar<br;
});
vector<ll> cnt(50001);
int l=v[0][0],r=v[0][1],ans=0;
for(int i=l;i<=r;i++){
if(a[i]==INT_MAX)continue;
if(++cnt[a[i]]%a[i]==0){
ans++;
ll x=a[i]*a[i];
while(x<=50000&&++cnt[x]%x==0)
ans++,x=x*x;
}
}
vector<int> answer(q);
for(auto [L,R,I]:v){
while(L>l){
if(a[l]==INT_MAX){l++;continue;}
if(cnt[a[l]]--%a[l]==0){
ans--;
ll x=a[l]*a[l];
while(x<=50000&&cnt[x]--%x==0)
ans--,x=x*x;
}
l++;
}
while(L<l){
--l;
if(a[l]==INT_MAX)continue;
if(++cnt[a[l]]%a[l]==0){
ans++;
ll x=a[l]*a[l];
while(x<=50000&&++cnt[x]%x==0)
ans++,x=x*x;
}
}
while(R>r){
++r;
if(a[r]==INT_MAX)continue;
if(++cnt[a[r]]%a[r]==0){
ans++;
ll x=a[r]*a[r];
while(x<=50000&&++cnt[x]%x==0)
ans++,x=x*x;
}
}
while(R<r){
if(a[r]==INT_MAX){r--;continue;}
if(cnt[a[r]]--%a[r]==0){
ans--;
ll x=a[r]*a[r];
while(x<=50000&&cnt[x]--%x==0)
ans--,x=x*x;
}
r--;
}
answer[I]=ans;
}
for(int i=0;i<q;i++)printf("%d\n",answer[i]);
}
int main(){
setbuf(stdout, NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}2번 풀이)
어떤 수 k가 스퀘어 작업이 가능해지려면, 그 수가 배열 a 안에 최소 k개 포함되어야 한다. (만약 수열 a가 [2, 2, 4, 4, 4]와 같은 경우 4가 3개만 있어도 스퀘어 작업이 가능하지만, 대충 k개에 비례하는 개수가 필요하다.)
$1+2+3+...+x = \frac{x(x+1)}{2}$이므로, $\frac{x(x+1)}{2} \leq n$이면 x는 최대 약 $\sqrt{n}$개가 된다.
따라서 스퀘어 작업이 가능한 수들만 모아 배열 c를 만들었고, 모든 k에 대해 구간 [1~i]의 개수를 누적 합으로 구해두면 쿼리당 배열 c의 길이만큼의 시간이 걸린다.
따라서 시간복잡도는 $O((n+Q)\sqrt{n})$으로 1번 풀이보다 약간 더 크지만, 상수가 작기를 기대하며 제출해봤으나 부분점수도 받지 못했다.
코드 (누적 합)
#include <bits/stdc++.h>
using namespace std;
#define UNIQUE(v) sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
int candidate[50001],a[50001];
void solve(){
int n;scanf("%d",&n);
memset(candidate,0,sizeof(int)*(n+1));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>n||a[i]==1)a[i]=0;
candidate[a[i]]++;
}
for(int i=2;i*i<=n;i++)candidate[i*i]+=candidate[i]/i;
vector<int> c;
for(int i=1;i<=n;i++)
if(a[i]<=1||candidate[a[i]]<a[i])a[i]=INT_MAX;
else c.push_back(a[i]);
UNIQUE(c);
vector<vector<int>> sum(c.size(),vector<int>(n+1));
for(int i=0;i<c.size();i++)
for(int j=1;j<=n;j++)sum[i][j]=sum[i][j-1]+(a[j]==c[i]);
int q;scanf("%d",&q);
while(q--){
int l,r;scanf("%d%d",&l,&r);
int ans=0;
unordered_map<int,int> ma;
for(int i=0;i<c.size();i++){
int x=c[i],cnt=sum[i][r]-sum[i][l-1];
int root=sqrt(x);
if(root*root==x&&ma.count(root))cnt+=ma[root];
ans+=cnt/x,ma[x]=cnt;
}
printf("%d\n",ans);
}
}
int main(){
setbuf(stdout, NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}후기
이번에 4번 문제를 풀면서, 처음엔 풀이가 전혀 생각나지 않다가 $N^2$ 코드를 짜고 나서야 자연스럽게 만점 풀이가 떠올랐다.
이전에 서브 태스크 문제를 순서대로 푸는 게 문제 해결에 도움이 될 수 있다는 말을 들었는데, 오늘에서야 그게 와 닿았다.
그리고 5번 문제... 나는 평소에 코드를 짤 때 구현만 편하다면 상수를 붙이는 것에 크게 신경 쓰지 않는데, 코드 자체가 문제인지 최적화를 덜한 게 문제인지 아직은 모르지만, 앞으로 신경을 좀 써야겠다.
만점을 받지 못한 건 아쉽지만, 접근 방향은 맞았다는 걸 위안으로 삼아본다.
모비스와 이번 대회에서 구현이 부족함을 느꼈으니, 다음 주 ucpc 전까지 구현 연습도 좀 해봐야겠다.
'CP > 대회 후기' 카테고리의 다른 글
| 제5회 고려대학교 MatKor Cup 후기 (4) | 2024.09.09 |
|---|---|
| SCPC 2024 Round 2 대회 후기 + 풀이 (0) | 2024.07.29 |
| 2024 SCSC 서울대학교 프로그래밍 경시대회 후기 (1) | 2024.06.02 |
| INU 코드페스티벌 2023 개최 과정 + 후기 (6) | 2023.12.20 |
| 2023 ICPC Seoul Regional 본선 후기 (2) | 2023.12.18 |