2018 SCPC 2차 예선 풀이
들어가며
오늘도 아침 9시에 일어나 있었기에 바로 시작했다.
이번에는 문제 백업을 해 놓았다. 다만 HTML만 받아 놓은 상태라서 이걸 내 형태에 맞추기 위해서는 꽤 작업이 필요해 보인다. 순차적으로 정규표현식을 적용하는 툴이 있으면 좋겠는데 어떻게 찾아야 할지 모르겠다. 어찌 됐건 아무래도 MathJax를 곧 지원하게 될 것 같다.
1. Quick Sort
쉽다. N개를 앞에서부터 보면서 그때까지의 최댓값보다 큰지 아닌지를 기록하고, 뒤에서부터 보면서 그때까지의 최솟값보다 작은지 아닌지를 기록한다. 둘 모두를 만족하는 것의 개수를 세면 된다.
#include<iostream>
using namespace std;
#include<stdio.h>
int t,n,a[200010],chk1[200010],chk2[200010],out;
int main()
{
int i,j,mn,mx;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d",&n);
for(j=1;j<=n;++j)
{
scanf("%d",&a[j]);
chk1[j]=0;
chk2[j]=0;
}
chk1[1]=1;
mx=a[1];
for(j=2;j<=n;++j)
{
if(a[j]>mx)
{
mx=a[j];
chk1[j]=1;
}
}
chk2[n]=1;
mn=a[n];
for(j=n-1;j>=1;--j)
{
if(a[j]<mn)
{
mn=a[j];
chk2[j]=1;
}
}
out=0;
for(j=1;j<=n;++j)if(chk1[j]&&chk2[j])out++;
printf("Case #%d\n%d\n",i,out);
}
return 0;
}2. 메모지
어디서 본 것 같은데…. 하고 일단 넘어갔다.
3. Bitonic Paths
데이크스트라 알고리즘을 약간 변형하면 단조 증가 하는 경로 중 최단 거리를 찾을 수 있다.# 간선들을 가중치 내림차순으로 정렬한 후, 계속 더 작은 간선을 선택하도록 반복하면 된다. 이때 우선순위 큐에 최대 E번 들어갈 수 있으므로 시간복잡도는 O(ElogE) 이다.
위 과정을 거친 후 1번 정점으로부터의 값과 N번 정점으로부터의 값을 합하여 그 중 최솟값을 찾아주면 된다. 여기서 간선이 최대 100000개, 가중치가 최대 200000이므로 수의 범위에 유의해야 한다.
-1 처리와 순증가 실수로 인해 몇 번 틀렸다.
#include<iostream>
using namespace std;
#include<algorithm>
#include<queue>
#include<stdio.h>
struct Edge
{
int s,e,c;
bool operator()(Edge a,Edge b)
{
return a.c>b.c;
}
}e[200010];
int t,n,m,pos[100010];
long long d1[100010],d2[100010],out;
vector<int> idx[100010];
priority_queue<pair<long long,int> > q;
inline long long mn2(long long a,long long b)
{
if(a>b)return b;
return a;
}
void dijkstra(int s,long long d[])
{
int i;
pair<long long,int> p;
for(i=1;i<=n;++i)
{
pos[i]=0;
d[i]=0x3FFFFFFFFFFFFFFFll;
}
d[s]=0;
for(i=0;i<idx[s].size();++i)
{
q.push(make_pair(-e[idx[s][i]].c,idx[s][i]));
d[e[idx[s][i]].e]=e[idx[s][i]].c;
}
while(!q.empty())
{
p=q.top();
q.pop();
while(pos[e[p.second].e]<idx[e[p.second].e].size()&&e[idx[e[p.second].e][pos[e[p.second].e]]].c>=e[p.second].c)
{
q.push(make_pair(p.first-e[idx[e[p.second].e][pos[e[p.second].e]]].c,idx[e[p.second].e][pos[e[p.second].e]]));
d[e[idx[e[p.second].e][pos[e[p.second].e]]].e]=mn2(d[e[idx[e[p.second].e][pos[e[p.second].e]]].e],-p.first+e[idx[e[p.second].e][pos[e[p.second].e]]].c);
pos[e[p.second].e]++;
}
}
}
int main()
{
int i,j;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d",&n,&m);
for(j=1;j<=m;++j)
{
scanf("%d%d%d",&e[j*2-1].s,&e[j*2-1].e,&e[j*2-1].c);
e[j*2].s=e[j*2-1].e;
e[j*2].e=e[j*2-1].s;
e[j*2].c=e[j*2-1].c;
}
sort(&e[1],&e[m*2+1],Edge());
for(j=1;j<=n;++j)idx[j].clear();
for(j=1;j<=m*2;++j)idx[e[j].s].push_back(j);
dijkstra(1,d1);
dijkstra(n,d2);
out=0x7FFFFFFFFFFFFFFFll;
for(j=1;j<=n;++j)
{
if(d1[j]==0x3FFFFFFFFFFFFFFFll||d2[j]==0x3FFFFFFFFFFFFFFFll)continue;
if(d1[j]+d2[j]<out)out=d1[j]+d2[j];
}
if(out==0x7FFFFFFFFFFFFFFFll)out=-1;
printf("Case #%d\n%lld\n",i,out);
}
return 0;
}2. 메모지 (Cont'd)
2017 ACM-ICPC 대전 리저널 인터넷 예선 기출 문제다.# 기출 문제다 보니 공개된 풀이도 있다.#
예전에 풀어 놓은 것이 있지 않을까 해서 컴퓨터를 열심히 뒤져 봤지만 별 소득이 없었다. 일단 결정적으로 우리 팀(AeRaMoLeuGetDaPPAP)은 그 문제를 풀지 못했었다.# 대충 보니 그리디로 열심히 해 보려다가 실패한 것처럼 보였다. 그래서 처음부터 다시 생각해 보기로 했다. N이 10000이라는 점을 이용해 O(N2) 솔루션을 찾는 것에 주력했다.
d[i][j]를 y좌표 기준으로 아래서부터 i번째까지 메모지를 배치하고 연결했을 때 j개가 꺾인 표시선일 경우 메모지가 위치한 가장 위 y좌표 중 최소값으로 정의하자. 그러면 d[1][0]은 y[1]이고 d[1][1]은 -∞이다. 비슷하게 d[i][i]는 모두 -∞이다. 그 다음으로 d[i][j]를 채우기 위한 점화 관계를 살펴보자. 먼저 i번째 점에 대해 메모지와 연결할 때 연결선이 꺾일 수 있는 것으로 추가하면 d[i-1][j-1]+h[i]의 값이 가능하다. 물론 j가 1 이상이어야 한다. 수평선으로만 연결하고자 한다면, 즉 d[i-1][j]에서 가져오려면 d[i-1][j]가 y[i] 이하임을 확인해야 한다. 만약 그렇지 않다면 수평선으로만은 연결할 수 없기 때문이다. 이 조건을 만족한다면 max(d[i-1][j]+h[i],y[i])의 값도 가능하다. "가능하다"고 표현한 것은 불가능한 경우도 있기 때문이다. 조건이 모두 안 맞는다면 불가능하다고 표시해 준다. 최종적으로 d[n][i] 중 가능한 값이 들어 있는 가장 작은 i를 찾아주면 최소 꺾은 표시선의 개수를 알 수 있다.
N이 10000이므로 이를 10000×10000 배열을 잡아서 구현하기는 곤란하다. d[i][j]를 구하기 위해서는 d[i-1][j-1]과 d[i-1][j] 만을 사용한다는 것을 활용하면 2행만으로 구성할 수 있다.
#include<iostream>
using namespace std;
#include<algorithm>
#include<stdio.h>
struct Point
{
int y,h;
bool operator()(Point a,Point b)
{
return a.y<b.y;
}
}a[10010];
int t,n,d[2][10010];
inline int mn2(int a,int b)
{
if(a>b)return b;
return a;
}
inline int mx2(int a,int b)
{
if(a>b)return a;
return b;
}
int main()
{
int i,j,k,x;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d",&n);
for(j=1;j<=n;++j)scanf("%d%d%d",&x,&a[j].y,&a[j].h);
sort(&a[1],&a[n+1],Point());
d[1][0]=a[1].y;
d[1][1]=-1999999999;
for(j=2;j<=n;++j)
{
for(k=0;k<j;++k)
{
d[j%2][k]=1999999999;
if(k)d[j%2][k]=d[(j-1)%2][k-1]+a[j].h;
if(d[(j-1)%2][k]<=a[j].y)d[j%2][k]=mn2(d[j%2][k],mx2(d[(j-1)%2][k]+a[j].h,a[j].y));
}
d[j%2][j]=-1999999999;
}
for(j=0;j<=n;++j)if(d[n%2][j]<1999999999)break;
printf("Case #%d\n%d\n",i,j);
}
return 0;
}4. 지진
먼저 M개의 수와 패턴이 있을 때 일치하는지 검사를 어떻게 할지 생각해 보았다. map을 이용하면 O(MlogM) 만에 할 수 있다. M개의 수를 키로 하고 값은 위치로 하여 map에 넣은 후, iterator를 통해 순회하면서 그 위치의 패턴 값이 단조 증가하는지를 파악하면 된다.
그렇다면 이제 최대 K개의 수와 해당하는 패턴을 빼는 것에 대해서 고려하는 것은 LIS라는 간단한 문제로 단순화되는 것을 관찰할 수 있다. 이 역시 O(MlogM) 이다. 따라서 전체 시간복잡도는 O(NMlogM) 이다.
코드는 매우 간단하다.
#include<iostream>
using namespace std;
#include<algorithm>
#include<map>
#include<stdio.h>
int t,n,m,k,a[10010],b[310],c[310],len,out;
map<int,int> p;
int main()
{
int i,j,s,pos;
map<int,int>::iterator it;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d%d",&n,&m,&k);
for(j=1;j<=n;++j)scanf("%d",&a[j]);
for(j=1;j<=m;++j)scanf("%d",&b[j]);
out=0;
p.clear();
for(j=1;j<m;++j)p[a[j]]=j;
for(;j<=n;++j)
{
p[a[j]]=j;
len=0;
for(it=p.begin();it!=p.end();++it)
{
pos=lower_bound(&c[0],&c[len],b[it->second-j+m])-c;
if(pos>=len)len++;
c[pos]=b[it->second-j+m];
}
if(len>=m-k)out++;
p.erase(a[j-m+1]);
}
printf("Case #%d\n%d\n",i,out);
}
return 0;
}5. 히스토그램
해결하지 못했다.
결과
6시간 정도에 마무리했다. 아래는 그 당시 상황이다.
두 번 연속 생각보다 좋은 결과를 냈다. 이 정도면 거의 본선 진출일 것 같은데 본선에서도 좋은 결과가 있었으면 좋겠다.
7/13 추가
최종 공식적으로 발표된 결과는 아래와 같다. 예상대로 본선에 진출했다. 들리는 얘기로는 400점대까지도 본선에 진출했다고 한다. 3번 문제가 꽤 시간제한이 빡빡했다고 하는데 나는 못 느끼기는 했다.
