작년 본선 진출 실패라는 안타까운 상황에서, 이번에는 다시 키보드를 타자는 일념으로 열심히 쳤다. 아침 9시에 우연히 일어나 있었기에 바로 시작했다.
문제 백업을 해 둘 걸 그랬다. 아침이 되고 대회가 끝나고 나서야 생각났다. 그리고 또 하나는 Markdown으로 렌더링 된 결과에 MathJax를 사용하고 싶어졌다. 종범이를 따라가는 중이다.
처음에 문제를 잘못 읽어서 차이가 K 이하이어야만 같이 탈 수 있다는 줄 알았다. 그리고 이걸 이분 탐색을 이용해 O(NlogN)으로 짰다. 생각해보니 이러면 O(N)으로도 가능했는데, 어차피 답이 아니라서 그냥 놔뒀다. 생각이 잘 안 나서 일단 넘어갔다.
입력이 10000으로 아주 작다. 4자리 이하의 회문 수는 9+9+90+90=198개이다. 숫자마다 더해가면서 BFS 처럼 탐색하면 최소 횟수로 더하는 방법을 알 수 있다.
#include<iostream>
using namespace std;
#include<algorithm>
#include<queue>
int t,n,a[10010];
queue<int> q;
vector<int> out;
void push(int now)
{
int i,j;
for(i=1;i<=9;++i)
{
if(now+i<=10000&&a[now+i]==-1)
{
q.push(now+i);
a[now+i]=now;
}
if(now+i*10+i<=10000&&a[now+i*10+i]==-1)
{
q.push(now+i*10+i);
a[now+i*10+i]=now;
}
for(j=0;j<=9;++j)
{
if(now+i*100+j*10+i<=10000&&a[now+i*100+j*10+i]==-1)
{
q.push(now+i*100+j*10+i);
a[now+i*100+j*10+i]=now;
}
if(now+i*1000+j*100+j*10+i<=10000&&a[now+i*1000+j*100+j*10+i]==-1)
{
q.push(now+i*1000+j*100+j*10+i);
a[now+i*1000+j*100+j*10+i]=now;
}
}
}
}
int main()
{
int i,j,now;
for(i=1;i<=10000;++i)a[i]=-1;
push(0);
while(!q.empty())
{
now=q.front();
q.pop();
push(now);
}
cin>>t;
for(i=1;i<=t;++i)
{
cin>>n;
out.clear();
while(n)
{
out.push_back(n-a[n]);
n=a[n];
}
cout<<"Case #"<<i<<endl;
if(out.size()<=3)
{
sort(out.begin(),out.end());
cout<<out.size();
for(j=out.size()-1;j>=0;--j)cout<<" "<<out[j];\
}
else cout<<"0";
cout<<endl;
}
return 0;
}그리디하게 접근해봤다. a라는 사람이 버스에 있을 때(그리고 현재 가장 큰 값일 때) a+k+1 이상이면서 가장 작은 사람을 태우는 것이 무조건 이득이다. 안 태운다면 그사이에 a+1이 있다면 동일하게 갈 수 있지만, 그 이상의 값이 존재하는 순간 버스를 하나 더 구해야 하는 상황이 된다. 그리고 이 방법은 위에서 구현해놨던 이분 탐색을 거의 그대로 사용할 수 있었다. 다만 배열에서 체크 이슈가 있어서 한 번 틀렸다. O(NlogN)이다.
#include<iostream>
using namespace std;
#include<algorithm>
#include<stdio.h>
int t,n,k,a[200010],chk[200010],out;
int main()
{
int i,j,now,bus;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d",&n,&k);
for(j=1;j<=n;++j)
{
scanf("%d",&a[j]);
chk[j]=0;
}
sort(&a[1],&a[n+1]);
out=0;
now=1;
while(1)
{
while(chk[now]&&now<=n)now++;
if(now>n)break;
out++;
bus=now;
while(bus<=n)
{
chk[bus]=1;
bus=lower_bound(&a[1],&a[n+1],a[bus]+k+1)-a;
while(chk[bus]&&bus<=n)bus++;
}
}
printf("Case #%d\n%d\n",i,out);
}
return 0;
}나는 이 생각을 못 했지만, K 범위 내에 있는 사람의 수의 최댓값이 이 문제의 답이다. 그리고 이건 슬라이딩 윈도로 O(N)만에 구현할 수 있다.
이 문제도 일부 증명이 필요한데, 엄밀하게 하지는 못하겠다. 간단하게만 적어보자면 현재 보고 있는 정점의 차수가 2이고 연결된 정점들이 서로 연결되어 있다면(즉, 삼각형을 이룬다면) 이는 문제의 "작업"에 따라 현재 정점을 추가할 수 있다는 얘기고, 그러면 무조건 떼는 것이 좋다. 연결된 정점들의 차수에 따라 나눠보면 아래와 같다.
이런 느낌으로 보면 현재 보이는 2짜리는 가능하다면 무조건 떼주고, 그에 따라 업데이트되는 간선 정보와 차수를 잘 트래킹해주면서 따라가면 된다. 차수가 2인걸 찾는 데는 우선순위 큐, 각 정점에서 연결된 정점은 셋으로 관리했다.
#include<iostream>
using namespace std;
#include<queue>
#include<set>
#include<stdio.h>
int t,n,m,out;
priority_queue<pair<int,int> > q;
set<int> a[200010];
int main()
{
int i,j,x,y;
pair<int,int> p;
set<int>::iterator it;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d",&n,&m);
for(j=1;j<=n;++j)a[j].clear();
for(j=1;j<=m;++j)
{
scanf("%d%d",&x,&y);
a[x].insert(y);
a[y].insert(x);
}
out=n;
while(!q.empty())q.pop();
for(j=1;j<=n;++j)q.push(make_pair(-a[j].size(),j));
while(!q.empty())
{
p=q.top();
q.pop();
if(p.first<-2)break;
if(p.first>-2||p.first!=-a[p.second].size())continue;
x=*a[p.second].begin();
y=*a[p.second].rbegin();
if(a[x].find(y)!=a[x].end())
{
out--;
a[x].erase(p.second);
q.push(make_pair(-a[x].size(),x));
a[y].erase(p.second);
q.push(make_pair(-a[y].size(),y));
}
}
printf("Case #%d\n%d\n",i,out);
}
return 0;
}무지막지한 문제인 것 같다. 내용만 대충 읽고 넘어갔다. 화이팅 ^^
y의 범위가 굉장히 넓어서 처음에는 0 세 개를 잘못 친 것이 아닌지 질문까지 했었다.
기약분수에 대한 언급이 나오는데, 사실 생각해보면 분모는 1 또는 2밖에 될 수 없다. 엄밀한 설명은 못 하겠는데 이를테면 1/3과 2/3보다는 1/2과 1/2로 맞춰질 수 있는 형태의 그림을 떠올리면 느낌이 들 수 있을 것이다.
한 가지 주목할 점은 y축 최대 높이를 정한다면 전등을 놓을 수 있는 후보들의 위치도 정해진다는 것이다. 이것은 꺾은 선의 기울기가 모두 +1 또는 -1이기 때문이다. 조금 더 구체적으로 말하자면 해당 x축과 평행한 직선과 꺾은 선과의 교점, 그리고 그 아래 있는 ^ 형태의 맨 위 점 말고는 신경 쓸 부분이 단 하나도 없다. 이렇게 위치들의 리스트가 나온다면 이게 L개의 전등으로 가능한지 여부는 쉽게 판정할 수 있을 것이라 본다. 역시 간략히 말하자면, 불이 닿는 범위가 끝나는 점 a가 있었다면 후보 중 (x좌표-y좌표) 값이 a 이하인 점들을 선택할 수 있을 것인데, 그중에서 가장 오른쪽에 있는(즉, x좌표가 큰) 점에 놓아야 한다. 그보다 왼쪽에 있는 점에 놓는다면 덮이는 범위가 반드시 더 좁아진다. 참고로 0 위치에 있는 점도 당연히 검사해 주어야 한다. 이걸 안 해서 한 번 틀렸다. 이렇게 검사 과정은 M 만에 할 수 있다.
그렇다면 이제 그 높이를 정해주면 되겠다. 문제의 특성상 가능/불가능 여부가 경계를 두고 나뉘기에 파라메트릭 서치를 사용할 수 있다. 0.5 단위까지만 사용할 수 있기에 주의해야 한다. 수가 굉장히 크므로 실수형을 그대로 사용하는 것도 위험할 수 있다. 처음에 입력을 받을 때부터 미리 다 2배를 해 주고 내부적으로는 정수로만 처리하는 것도 굉장히 좋은 방법이다. 최종 시간 복잡도는 O(MlogY)다. (Y = y 값의 최댓값, 즉 1,000,000,000,000)
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<stdio.h>
int t,n,m,k;
pair<int,long long> a[200010];
vector<pair<int,long long> > b;
bool isAvailable(long long p)
{
int i,pos=0,prv=-1,cnt=0;
long long now=0;
b.clear();
for(i=1;i<=m;++i)
{
if(a[i].second<a[i+1].second)
{
if(a[i+1].second<p)b.push_back(a[i+1]);
else if(a[i].second<=p&&p<=a[i+1].second)b.push_back(make_pair(a[i].first+p-a[i].second,p));
}
else
{
if(a[i].second<p)b.push_back(a[i]);
else if(a[i].second>=p&&p>=a[i+1].second)b.push_back(make_pair(a[i].first+a[i].second-p,p));
}
}
if(b.size()==0)return false;
if(b[0].first-b[0].second>0)return false;
while(now<n)
{
while(pos<b.size()-1&&b[pos+1].first-b[pos+1].second<=now)pos++;
if(pos==prv)return false;
cnt++;
now=b[pos].first+b[pos].second;
prv=pos;
}
return cnt<=k;
}
int main()
{
int i,j;
long long l,r,mid;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d%d",&n,&m,&k);
n=n*2;
for(j=1;j<=m+1;++j)
{
scanf("%d%lld",&a[j].first,&a[j].second);
a[j].first=a[j].first*2;
a[j].second=a[j].second*2;
}
l=0;
r=2000000000001ll;
while(l<r)
{
mid=(l+r)/2;
if(isAvailable(mid))r=mid;
else l=mid+1;
}
printf("Case #%d\n",i);
if(l==2000000000001ll)printf("-1\n");
else if(l%2)printf("%lld 2\n",l);
else printf("%lld 1\n",l/2);
}
return 0;
}5시간을 조금 넘겨서 마무리했다. 아래는 그 당시 상황이다.
최종 공식적으로 발표된 결과는 아래와 같다. 우주정거장 문제가 꽤 느리다.