한참 PS에서 손을 떼고 있었지만, 오랜만에 키보드나 타볼까 싶어서 문제를 읽기 시작했다.
금요일 15시부터 24시간이기는 하지만 업무, 게임 등으로 금요일의 시간은 거의 못 썼고, 자고 일어나면 토요일 한참 지나 있을 것 같고 출제도 해야 해서 새벽에 많이 하려 했다.
이번에도 문제 아카이빙을 했고 2019년에 미뤄뒀던 것도 드디어 했다. <span>을 지워주는 것이 좋다.
</?span( class[^>]*)?>한편 코드도 길고 4번 문제의 풀이도 길다 보니 오랫동안 미뤄 왔던 접기 기능을 블로그에 드디어 만들었다.
문제를 읽다가 1번은 그냥 구현이 귀찮았고 2번은 잘 안 떠올랐다. 3번도 확신은 없는 Branch&Bound 풀이가 하나 생각났는데 틀리면 그냥 접자는 생각으로 구현했다.
다행히도 Bound가 꽤 세게 잘 걸리는 것 같았고, 통과했다.
#include<iostream>
using namespace std;
#include<cstring>
#include<vector>
int t,n,m,k,c[510],chk;
char out[2010];
vector<int> a[510];
pair<int,int> b[2010];
bool dfs(int p)
{
int i,ret=0;
c[p]=1;
for(i=0;i<a[p].size();++i)
{
if(!c[a[p][i]])ret=ret|dfs(a[p][i]);
else if(c[a[p][i]]==1)return true;
}
c[p]=2;
return ret;
}
bool hasCycle()
{
int i,ret=0;
memset(c,0,sizeof(c));
for(i=1;i<=n;++i)if(!c[i])ret=ret|dfs(i);
return ret;
}
void back(int p)
{
if(p>k)
{
out[p]=0;
chk=1;
return;
}
out[p]='0';
a[b[p].first].push_back(b[p].second);
if(!hasCycle())back(p+1);
a[b[p].first].pop_back();
if(chk)return;
out[p]='1';
a[b[p].second].push_back(b[p].first);
if(!hasCycle())back(p+1);
a[b[p].second].pop_back();
}
int main()
{
int i,j,x,y;
cin>>t;
for(i=1;i<=t;++i)
{
cin>>n>>m>>k;
for(j=1;j<=n;++j)a[j].clear();
for(j=1;j<=m;++j)
{
cin>>x>>y;
a[x].push_back(y);
}
for(j=1;j<=k;++j)cin>>b[j].first>>b[j].second;
chk=0;
back(1);
cout<<"Case #"<<i<<endl<<out+1<<endl;
}
return 0;
}2번 생각이 여전히 잘 안 나서 1번조차도 미뤄두고 일단 점수 긁기부터 해보기로 했다. 전체 문제는 별로 생각을 안 해 보았고, '모든 1번 종류 쿼리에서 차이 값이 0인' 그룹 점수 합이 51점이나 되면서도 풀이가 바로 눈에 보여서 잡았다. 그냥 disjoint set을 union-find로 묶어주면서 같은 집합에 있다면 0, 아니라면 NC이다.
#include<iostream>
using namespace std;
#include<vector>
#include<stdio.h>
int t,n,k,p[100010];
int uf(int i)
{
if(p[i]==i)return i;
return p[i]=uf(p[i]);
}
int main()
{
int i,j,x,y,z,w,flag;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d",&n,&k);
for(j=1;j<=n;++j)p[j]=j;
printf("Case #%d\n",i);
flag=1;
for(j=1;j<=k;++j)
{
scanf("%d%d%d",&x,&y,&z);
if(x==1)
{
scanf("%d",&w);
if(w)flag=0;
else p[uf(y)]=uf(z);
}
else
{
if(!flag)printf("0\n");
else
{
if(uf(y)==uf(z))printf("0\n");
else printf("NC\n");
}
}
}
}
return 0;
}문제에서 주어지는 조건대로 disjoint set을 union-find로 묶어주고 마지막에 집합의 개수를 세주면 된다.
#include<iostream>
using namespace std;
#include<algorithm>
#include<stdio.h>
int t,n,p[100010],out;
int uf(int i)
{
if(p[i]==i)return i;
return p[i]=uf(p[i]);
}
int main()
{
int i,j,x;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d",&n);
for(j=1;j<=n;++j)p[j]=j;
for(j=1;j<=n;++j)
{
scanf("%d",&x);
if(j+x<=n)p[uf(j)]=uf(j+x);
}
for(j=1;j<=n;++j)uf(j);
sort(&p[1],&p[n+1]);
out=0;
for(j=1;j<=n;++j)if(p[j]!=p[j-1])out++;
printf("Case #%d\n%d\n",i,out);
}
return 0;
}도저히 2번 생각이 안 나서 일단 자고 일어나서 잡았다. 처음에 문제 읽을 때는 지문이나 수식이 너무 복잡해 보인다고 생각했는데 다 이해하고 나니 상당히 재미있는 문제였다.
부분 문제가 나에게는 매우 큰 힌트가 되었다. 부분 문제를 함께 따라가며 풀이를 찾아보자.
일단 최대한 충돌을 줄이기 위해 같은 집합에 속한 예약자들은 덩어리로 붙여 놓는 것이 좋겠다는 생각을 할 수 있다. 그렇다면 아래와 같은 형태가 된다. (Markdown 특성상 첫 행이 <th>일 수밖에 없어 bold가 들어갔지만 MathJax 수식은 영향이 없다. 집합이 달라지는 부분을 Markdown에서 border로 표현하기가 어려워 집합에 색을 칠했고 큰 의미는 없다.)
예시로
| … | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| … |
이 경우 충돌을 표시해보면 다음과 같다.
| … | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| … |
그렇다면 충돌이 있는 방에는 최대한 스트레스 지수가 작은 사람을 배치해야 하겠다. 즉, 집합마다 스트레스 지수로 정렬하여 가장 작은 4명을 각 직사각형의 꼭짓점 위치에 배치한다.
또한, 집합의 순서를 살펴보면, 배치된 맨 왼쪽 집합과 맨 오른쪽 집합은 2개의 꼭짓점 위치만 충돌이 발생함을 볼 수 있다. 그렇다면 양 끝 집합은 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개를 선택하면 된다.
1)과 비슷하게 배치한 모습을 살펴보자.
예시로
| … | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| … |
이번에도 충돌을 표시해보면 다음과 같다. 주황색은 좌우로도, 상하로도 충돌이 발생함을 의미한다.
| … | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| … |
그렇다면 여기서 주황색의 경우 스트레스 지수가 2번씩 더해짐을 관찰할 수 있다. 따라서 집합에서 스트레스 지수가 가장 작은 사람을 해당 주황색 위치에 배치해야 한다. 나머지 3개 충돌 위치에는 스트레스 지수가 2-4번째로 작은 사람을 배치하면 된다.
1)과 같이 양 끝 집합은 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개를 선택하면 된다.
이제 남은 부분 문제는 원래의 조건 외에는 제약조건이 없는 전체 문제이지만, 조금 더 나눠 생각해보자.
양 끝 집합을 선택하는 방법을 다시 떠올려보자. 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개 집합을
ㅁ…ㅁ 형태로 배치한다.
| … | ||||||||
|---|---|---|---|---|---|---|---|---|
| … |
ㅁ…ㄴㄱ 형태로 배치한다.
| … | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| … |
예시는
ㄴㄱ…ㄴㄱ 형태로 배치한다.
| … | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| … |
a.-c.에서 모두 가능하다는 것을 확인하였으니 통합하여 계산할 수 있다.
다시 3)과 같이 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개 집합을
ㅁ…ㅁ 형태로 배치한다. 예시는 3) a.와 동일하여 생략한다.
ㅁ…ㄴㄱ 형태로 배치한다.
이 경우가 가장 문제이다. 두 가지 가능성을 보고 둘 중 작은 값을 선택해야 한다.
하나는 앞에서 해왔던 것처럼 ㅁ…ㄴㄱ 형태로 배치하는 것이다. 가장 오른쪽에는
또 다른 가능성은
이렇게 모든 경우에 대해서 살펴보았다. 경우들이 복잡했지만 구현은 꽤 간단한데, 단지 스트레스 지수의 범위상 답 계산에 8바이트 정수형 변수를 활용해야 함에 유의하여라. 시간복잡도는
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<stdio.h>
int t,n,m,cnt[2];
long long out,out2;
vector<int> a[20010];
pair<int,int> sum34[20010];
int main()
{
int i,j,k,x,y;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d",&n,&m);
cnt[0]=0;
cnt[1]=0;
for(j=1;j<=n;++j)
{
scanf("%d",&x);
cnt[x%2]++;
a[j].clear();
for(k=1;k<=x;++k)
{
scanf("%d",&y);
a[j].push_back(y);
}
sort(a[j].begin(),a[j].end());
sum34[j]=make_pair(a[j][2]+a[j][3],x%2);
}
sort(&sum34[1],&sum34[n+1]);
out=0;
if(cnt[0]==n||cnt[1]==n)
{
for(j=1;j<=n;++j)out=out+((a[j].size()%2)+1)*a[j][0]+a[j][1]+a[j][2]+a[j][3];
out=out-sum34[n].first-sum34[n-1].first;
}
else
{
if(cnt[1]==2&&sum34[n].second==1&&sum34[n-1].second==1)
{
for(j=1;j<=n;++j)out=out+((a[j].size()%2)+1)*a[j][0]+a[j][1]+a[j][2]+a[j][3];
out=out-sum34[n].first-sum34[n-2].first;
out2=0;
for(j=1;j<=n;++j)
{
if(a[j].size()%2)out2=out2+2*a[j][0]+a[j][1];
else out2=out2+2*a[j][0]+2*a[j][1]+a[j][2]+a[j][3];
}
if(out2<out)out=out2;
}
else
{
for(j=1;j<=n;++j)out=out+((a[j].size()%2)+1)*a[j][0]+a[j][1]+a[j][2]+a[j][3];
out=out-sum34[n].first-sum34[n-1].first;
}
}
printf("Case #%d\n%lld\n",i,out);
}
return 0;
}처음에 2-SAT이 떠오른 것이 패인으로 보인다. 어렵게만 접근하고 있었고 결국 최소를 어떻게 찾을지 마지막 1시간까지도 생각이 나지 않아서 결국
#include<iostream>
using namespace std;
int t,n,k,chk,a[50010];
char b[50010],out[50010];
void back(int p)
{
int i,x;
if(p>n)
{
out[p]=0;
for(i=1;i<=n;++i)
{
out[i]=a[i]+'0';
x=0;
if(i>k)x=x|a[i-k];
if(i<=n-k)x=x|a[i+k];
if(x+'0'!=b[i])break;
}
chk=i>n;
return;
}
a[p]=0;
back(p+1);
if(chk)return;
a[p]=1;
back(p+1);
}
int main()
{
int i;
cin>>t;
for(i=1;i<=t;++i)
{
cin>>n>>k>>b+1;
chk=0;
if(n<=15)back(1);
cout<<"Case #"<<i<<endl<<out+1<<endl;
}
return 0;
}532/800, 이번에는 대회 화면에서 찍는 것을 깜빡했다.
정말 오랜만에 문제 풀이를 했는데 4번 같이 재밌는 문제를 풀어서 즐거웠다. 2차 예선은 갈 수 있다고 믿고 (아니라면 그새 PS판 수준이 엄청나게 올라간 것이므로 빨리 접어야 한다) 2차 예선 일정 때 바쁘지 않아서 잘 칠 수 있으면 좋겠다.