NYPC 본선에서 떨어지고 대학 ps 대회를 대비해서 실력을 늘릴겸 코포 버츄얼을 쳤다.
A. Make All Equal (00:04)
최솟값만 존재하게 한다면 풀 수 있어 보여 구현하였고, 예제에서 답이 다르게 나왔다.
모든 i에 대해 항상 ai와 같은 값을 가지는 원소만 남게 할 수 있다는 사실을 관찰하였고, 가장 출현하는 빈도가 높은 수를 배열을 통해 구하여 출력하였다.
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[105];
int main()
{
int i,t;
scanf("%d",&t);
while(t--)
{
int mx = 0,n,cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
int b;
scanf("%d",&b);
a[b]++;
if(a[b]>mx)mx=a[b];
}
for(i=1;i<=100;i++)
{
a[i] = 0;
}
printf("%d\n",n-mx);
}
}
B. Generate Permutation (00:12)
문제를 이해 못해서 예제를 보고 문제를 이해했다. 애드혹 느낌이 강하게 들었고, 홀수일 때는 1부터 n/2까지 순서대로 나열한 후, 나열하지 않은 수들을 역순으로 나열하면 정답이라는 관찰을 하였다. 짝수일 때는 몇 번 해봐도 불가능하길래 짝수일 때는 불가능할 것이라는 믿음을 가지고 제출하였고 AC를 받았다.
#include <stdio.h>
int main()
{
int i,t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
if(n%2==0)printf("-1\n");
else
{
for(i=1;i<=n/2;i++)
{
printf("%d ",i);
}
for(i=n;i>n/2;i--)
{
printf("%d ",i);
}
printf("\n");
}
}
}
C. Guess the tree (00:31)
노드 a, b를 쿼리로 보냈을 때 답으로 a가 돌아오면 두 노드가 연결되어 있는 것이고, 아니면 중간 노드를 반환한다. 따라서 분할정복을 통해 중간 노드를 m이라고 하고, (a,m), (m,b)에 대해 쿼리를 보내 주는 것을 반복하여 주면 노드 a, b의 경로를 알 수 있다. 이를 1부터 n까지 모든 노드에 대해 수행시켜주면 14n보다 작은 탐색 횟수로 정답을 구할 수 있다.
#include <stdio.h>
#include <vector>
using namespace std;
vector < int > adj[1005];
int dfs(int node,int fin,int par)
{
int i,flag = 0;
if(node==fin)return 1;
for(i=0;i<adj[node].size();i++)
{
if(adj[node][i]==par)continue;
if(dfs(adj[node][i],fin,node))flag = 1;
}
return flag;
}
void dq(int st,int en)
{
if(dfs(st,en,-1))return;
printf("? %d %d\n",st,en);
fflush(stdout);
int mid;
scanf("%d",&mid);
if(mid==st)
{
adj[st].push_back(en);
adj[en].push_back(st);
return;
}
dq(st,mid);
dq(mid,en);
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(i=2;i<=n;i++)
{
dq(1,i);
fflush(stdout);
}
printf("! ");
for(i=1;i<=n;i++)
{
for(j=0;j<adj[i].size();j++)
{
if(i>adj[i][j])continue;
printf("%d %d ",i,adj[i][j]);
}
}
printf("\n");
fflush(stdout);
for(i=1;i<=n;i++)
{
adj[i].clear();
}
}
}
D. Longest Max Min Subsequence (01:23)
사전순으로 가장 빠른 문자열을 출력하는 문제는 그리디하게 맨 앞 문자를 사전순으로 최대한 빠르게 하면 된다. 이 아이디어를 그대로 적용하되, 문자열의 길이가 줄지 않도록 하여야 한다. 각 수를 포함시키기 위해 최대한 나중에 포함시킬 수 있는 위치인 각 수가 마지막으로 등장하는 위치를 기록하자. 이후, 각 수가 마지막으로 등장하는 위치 중 제일 작은 값을 기준으로 이전에 선택한 수 + 1과 그 값 사이의 최댓값, 또는 최솟값을 선택하는 것이 가장 이득이다. (홀수 번째인지 짝수 번째인지에 따라서) 이 최댓값, 최솟값을 세그먼트 트리를 통해 관리해주면서, 이미 선택한 수들에 해당하는 인덱스는 최댓값, 최솟값으로 채워 더 이상 선택되지 않게 하면 문제를 해결할 수 있다.
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define siz 524288
#define inf 0
vector < int > adj[300005];
int p[300005],a[300005],arr[300005],cnt,tail;
int mn[siz*4],mx[siz*4],mnidx[siz*4],mxidx[siz*4],ch[300005],idx,vs;
void update(int s,int e,int l,int r,int node,int v)
{
if(s>r||e<l)return;
if(l<=s&&e<=r)
{
mnidx[node] = node;
mxidx[node] = node;
mn[node] = v;
mx[node] = v;
return;
}
int mid = (s+e)>>1;
update(s,mid,l,r,node*2,v);
update(mid+1,e,l,r,node*2+1,v);
mx[node] = max(mx[node*2],mx[node*2+1]);
if(mx[node]==mx[node*2])mxidx[node] = mxidx[node*2];
else mxidx[node] = mxidx[node*2+1];
if(mn[node*2]==-inf)mn[node] = mn[node*2+1];
else if(mn[node*2+1]==-inf)mn[node] = mn[node*2];
else mn[node] = min(mn[node*2],mn[node*2+1]);
if(mn[node]==mn[node*2])mnidx[node] = mnidx[node*2];
else mnidx[node] = mnidx[node*2+1];
}
int mxquery(int s,int e,int l,int r,int node)
{
if(s>r||e<l)return 0;
if(l<=s&&e<=r)
{
if(mx[node]>vs)idx = mxidx[node];
else if(mx[node]==vs&&idx>mxidx[node])idx = mxidx[node];
vs = max(vs,mx[node]);
return mx[node];
}
int mid = (s+e)>>1;
return max(mxquery(s,mid,l,r,node*2),mxquery(mid+1,e,l,r,node*2+1));
}
int mnquery(int s,int e,int l,int r,int node)
{
if(s>r||e<l)return 100000000;
if(l<=s&&e<=r)
{
if(mn[node]==inf)return 100000000;
if(mn[node]<vs)idx = mnidx[node];
else if(mn[node]==vs&&idx>mnidx[node])idx = mnidx[node];
vs = min(mn[node],vs);
return mn[node];
}
int mid = (s+e)>>1;
int left = mnquery(s,mid,l,r,node*2);
int right = mnquery(mid+1,e,l,r,node*2+1);
if(left==inf)return right;
if(right==inf)return left;
return min(left,right);
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
p[a[i]] = i;
adj[a[i]].push_back(i);
update(1,siz,i,i,1,a[i]);
}
for(i=1;i<=n;i++)
{
if(p[i]!=0)arr[cnt++] = p[i];
}
sort(arr,arr+cnt);
printf("%d\n",cnt);
int bef = 1;
for(i=1;i<=cnt;i++)
{
int val;
if(i%2)
{
vs = 0;
val = mxquery(1,siz,bef,arr[tail],1);
printf("%d ", val);
ch[val] = 1;
bef = idx+2-siz;
}
else
{
vs = 100000000;
val = mnquery(1,siz,bef,arr[tail],1);
printf("%d ", val);
ch[val] = 1;
bef = idx+2-siz;
}
for(j=0;j<adj[val].size();j++)
{
update(1,siz,adj[val][j],adj[val][j],1,-inf);
}
while(1)
{
if(ch[a[arr[tail]]])tail++;
else break;
}
}
printf("\n");
for(i=1;i<=n;i++)
{
adj[i].clear();
p[i] = 0;
ch[i] = 0;
}
cnt = 0;
tail = 0;
}
}