NWERC(Northwestern Europian Regional Contest) 2021

https://www.acmicpc.net/category/detail/2887

22.09.30

전체 12문제중 3솔(+종료 1분 뒤 1솔 더...)

NWERC눨ㅋ는 항상 문제가 적당히 좋은 것 같다.

이번주는 유난히 바빠서 전날 잠을 못잤고, 잡았던 A, B, D, E, G 중 2문제만 풀 수 있었다.

대회 도중에 중간중간 다른데 들러야 할 일이 있어서 1~2시간 정도 자리를 비웠고,

맡은 문제 이외의 다른 문제들에 대해서도 아이디어는 생각해두었으나 구현할 시간이 부족했다.

그 때문인지 아쉽게도 G를 대회 종료 1분 후에 맞혔다. 이번에야말로 team_sudal이 1등 할 수 있었는데 ㅠ

예선이 다음주로 다가왔는데, 잘 되면 좋을 것 같다.

---

A. Access Denied

문제

Password를 Query로 넣으면 Check process에 해당하는 delay(ms)가 나온다.

2500번 이하의 Query를 통해 Correct Password를 찾아라

 

풀이

아래와 같은 관찰을 할 수 있다.

1. 1번 예시를 통해서 길이가 다르면 5ms 반응이 오는 것을 알 수 있다.

2. 2~3번 예시를 통해 초기 연산에 14ms가 필요하며 앞에서부터 자리수가 맞을 때마다 맞은 자리수*9ms가 추가됨을 알 수 있다.

 

위 관찰을 통해 길이를 찾고, 앞에서부터 한 문자씩 찾아나가면 된다. (각 자리수의 문자는 약 60개 * 암호 길이 20 = 1200)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(){
    string t = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    int ch=0, ms, pre = -1, now, c;
    string s;
    char S[1000];
    while(1){
        if(!ch){
            s+='A'; 
        }
        else{
            now = (ms-14)/9;
            if(pre!=now) c=0, pre=now;
            s[now] = t[++c];
        }
        cout<<s<<endl;

        scanf("%*s %s",S);
        if(S[0]=='D') scanf("%*[^(](%d%*[^\n]",&ms);
        else break;

        if(ms!=5) ch=1;
    }
}

---

B. Boredom Buster

문제

1~n/2까지 번호가 적힌 카드가 2개씩 총 n개가 배열 A 있으며 순서가 잘 섞여있다.

(i, j)쿼리를 보내면 $A_i$와 $A_j$의 값을 순서를 섞어서 (x,y)로 반환해준다.

92000번 이하의 쿼리로 배열 A를 알아내라

 

풀이

인접한 2개의 카드들에 대해 미리 전처리 연산을 해둔다. (n/2개 쿼리)

(x,y)에 대해 x==y인 경우를 모두 떼두고 (min(x,y), max(x,y))로 바꾼 후, 각 좌표(2k, k=0~n/2-1)를 기억한 채로 정렬한다.

인접한 2개의 pair에 대해 다음과 같은 경우를 고려할 수 있다.

 

(X, Y) : Query(i,j)라고 하자

1. (x,y,i), (x,y,j)

1) X==Y : (x y), (x y)

2) X!=Y : (x y), (y x)

 

2. (x,y,i), (x,z,j)

1) X==Y : (x y), (x z)

2) X!=Y :

 (X', Y') : Query(i,j+1)라고 하자 

 (1) X'==Y' : (x y), (z x)

 (2) X'!=Y' : (y x), (z x)

 

3. 인접한 두 pair의 앞쪽 값이 같지 않은 경우 이미 해당 pair를 확인하기 전에 1. 및 2. 분류에서 y 혹은 z로 표시되었으므로

1번에 처리 가능

 

해당 방법을 사용할경우 에디토리얼 설명 기준 2번째 방법이며

15/16n으로 TLE가 난다.

정해는 11/12n이라고 한다. (각 번호 노드를 만들어두고 pair 쌍을 통해 그래프 체인을 처리하는 방식으로 풀 수 있다고 함)

 

소스코드

#include <bits/stdc++.h>
const int N = 1e5+10;
using namespace std;
struct pp{
    int x, y, i;
};
int rec[N];
int res[N];
vector<int> vis;
vector<pp> p;
inline bool cmp(const pp a, const pp b){
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}
int main(){
    int n;
    scanf("%d",&n); vis.resize(n/2+1); p.resize(n/2);
    int t=0;
    for(int i=0, x, y; i<n/2; ++i){
        printf("? %d %d\n",i*2+1,i*2+2);
        fflush(stdout);
        scanf("%d %d",&x,&y);
        if(x==y) vis[x]=1, res[i*2]=res[i*2+1]=x;
        else p[t++] = {min(x,y),max(x,y),i*2+1};
    }
    p.resize(t);
    sort(p.begin(),p.end(),cmp);
    t=0;
    for(int x, y;t<p.size();){
        if(t+1<p.size() && p[t].x==p[t+1].x && p[t].y==p[t+1].y){
            printf("? %d %d\n",p[t].i,p[t+1].i);
            fflush(stdout);
            scanf("%d %d",&x,&y);
            if(x==y) {
                y=(p[t].x==x)?p[t].y:p[t].x;
                vis[x]=1, res[p[t].i-1]=res[p[t+1].i-1]=x;
                vis[y]=1, res[p[t].i]=res[p[t+1].i]=y;
            }
            else{
                printf("? %d %d\n",p[t].i,p[t+1].i+1);
                fflush(stdout);
                scanf("%d %d",&x,&y);
                y=(p[t].x==x)?p[t].y:p[t].x;
                vis[x]=1, res[p[t].i-1]=res[p[t+1].i]=x;
                vis[y]=1, res[p[t].i]=res[p[t+1].i-1]=y;
            }
            t+=2;
        }
        else if(t+1<p.size() && p[t].x==p[t+1].x){
            printf("? %d %d\n",p[t].i,p[t+1].i);
            fflush(stdout);
            scanf("%d %d",&x,&y);
            if(x==y){ // 1 2 1 3
                vis[x]=1, res[p[t].i-1]=res[p[t+1].i-1]=x;
                res[p[t].i] = p[t].y;
                rec[p[t].y] = p[t].i;

                res[p[t+1].i] = p[t+1].y;
                rec[p[t+1].y] = p[t+1].i;
            }
            else{
                printf("? %d %d\n",p[t].i,p[t+1].i+1);
                fflush(stdout);
                scanf("%d %d",&x,&y);
                if(x==y){ // 1 2 3 1
                    vis[x]=1, res[p[t].i-1]=res[p[t+1].i]=x;
                    res[p[t].i] = p[t].y;
                    rec[p[t].y] = p[t].i;

                    res[p[t+1].i-1] = p[t+1].y;
                    rec[p[t+1].y] = p[t+1].i-1;
                }
                else{ // 2 1 1 3
                    x = p[t].x;
                    vis[x]=1, res[p[t].i]=res[p[t+1].i-1]=x;
                    res[p[t].i-1] = p[t].y;
                    rec[p[t].y] = p[t].i-1;

                    res[p[t+1].i] = p[t+1].y;
                    rec[p[t+1].y] = p[t+1].i;
                }
            }
            t+=2;
        }
        else{
            printf("? %d %d\n",rec[p[t].x]+1, p[t].i);
            fflush(stdout);
            scanf("%d %d",&x,&y);
            if(x==y){
                y = p[t].y;
                vis[x]=1, res[p[t].i-1]=x;
                if(rec[p[t].y]) vis[y]=1, res[p[t].i]=y;
                else rec[p[t].y]=p[t].i, res[p[t].i]=y;
            }
            else{
                x=p[t].x;
                y=p[t].y;
                vis[x]=1, res[p[t].i]=x;
                if(rec[p[t].y]) vis[y]=1, res[p[t].i-1]=y;
                else rec[p[t].y]=p[t].i-1, res[p[t].i-1]=y;
            }
            ++t;
        }
    }
    printf("!");
    for(int i=0; i<n; ++i) printf(" %d",res[i]);
    fflush(stdout);
}

---

C. Cutting Edge

문제

주어진 직육면체를 "직육면체 내부의 세 정수 좌표를 포함하는 평면"으로 잘 잘라서 꼭짓점이 좌표 평면인 3차원 볼록다면체를 $k/6 mm^3$크기로 만들어라

 

풀이

풀이는 떠올리지 못했는데, 채점 코드가 궁금했다. 3차원 convexhull을 어떻게 구한걸까

---

D. Dyson Circle

문제

점들이 주어지며 해당 점을 둘러싸는 인접 혹은 대각선으로 연결된 점들의 개수를 구하여라

단, 주어진 점들 끼리는 둘러싸는 점들을 통과하지 않고 인접하게 연결되어야 한다.

 

풀이

점들의 convex hull을 구하는 문제인데, 두 가지만 더 고려하면 된다.

직사각형 점이므로 convex hull을 구성하는 인접한 점들 사이의 max(abs(x-x'), abs(y-y'))과 더불어 4개의 점을 추가한다.

구성 점이 2개인 경우 abs(x-x') == abs(y-y')일 때, 위의 방법으로만 계산하면 문제의 두번째 줄 조건을 만족하지 못할 수 있다. 한 칸을 더 추가하여 한쪽 변의 점을 모두 shift해주면 해결이 된다.

 

소스코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ld;
typedef pair<ld,ld> P; // Point

// return distance between two points
ld Dis(P a, P b){ return ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }

int ccw(P a, P b, P c){
	ld X = a.x*b.y + b.x*c.y + c.x*a.y;
	ld Y = a.y*b.x + b.y*c.x + c.y*a.x;
	return X>Y?1:X<Y?-1:0;
}
// return convex hull with graham scan
vector<P> ConvexHull(vector<P> v){
	sort(v.begin(), v.end());
	sort(v.begin()+1, v.end(), [&](P x,P y){ return ccw(v[0],x,y) > 0 || (ccw(v[0],x,y) == 0 && Dis(v[0],x) < Dis(v[0],y)); });
	vector<P> r{v[0],v[1]};
	if(v.size()>2) for(int i=2; i<v.size(); r.push_back(v[i]), ++i) while(r.size()>1 && ccw(r[r.size()-2],r[r.size()-1],v[i])<=0) r.pop_back();
	return r;
}

int main(){
    int n;
    scanf("%d",&n);
    if(n==1) puts("4"), exit(0);
    vector<P> v(n);
    for(auto&[x,y]:v) scanf("%lld%lld",&x,&y);
    
    v = ConvexHull(v);
    if(v.size()==2){
        ld X = abs(v[0].x-v[1].x), Y = abs(v[0].y-v[1].y);
        printf("%lld",2*max(X,Y)+4+(X==Y));
    }
    else{
        v.push_back(v[0]);
        ld p=4;
        for(int i=0; i<v.size()-1; ++i){
            ld X = abs(v[i].x-v[i+1].x), Y = abs(v[i].y-v[i+1].y);
            //printf("%d\n",max(X,Y)+1);
            p+=max(X,Y);
        }
        printf("%lld",p);
    }
}

---

E. Exchange Students

문제

처음에는 문제를 잘못 이해하여 중복수를 포함할 때, 원하는 위치로 swap만을 사용하여 옮기기 위한 최소 swap 횟수 및 그 순서 출력인 줄 알았다.

문제를 다시 읽어보니, swap할 때 그 사이의 모든 수가 swap할 두 수 중 작은 수 이하여야 한다는 조건이 있었다.

 

풀이

첫 이해에서는 잘 생각났지만, 두 번째로 조건을 확인한 후 풀이가 생각나지 않아 포기하였다

---

F. Flatland Olympics

문제

평면 상에서 원하는 선분 구간이 있었을 때, 선분의 모든 구간이 보이며 앞에 사람이 없는 경우의 수를 구하여라

 

풀이

선분의 한쪽 끝에서 각도순정렬을 하고, 또 반대쪽 끝에서 각도순 정렬을 한다.

두 사람 A, B의 좌표 (x,y)와 (x', y')에 대해 x<x' && y<y'인 경우 A는 B를 가리게 된다.

잘 계산하면 풀 수 있을 것 같다.

---

G. Glossary Arrangement

문제

파일이 lexicographical하게 주어진다. 이를 주어진 조건에 맞게 잘 배열할 때 사용할 수 있는 최소 row 수를 구하라

주어진 파일은 여러 column으로 나누어 나열되며 한 column에는 최대 row 수보다 적은 파일이 있을 수 있다.

파일은 (1)상->하, (2)좌->우의 우선순위를 가진다. 각 column의 파일명 길이의 최대값들의 합이 주어진 w를 넘지 않아야 한다.

 

풀이

row에 대해 parametric search를 진행한다.

parametric search에서 boolean인 solve 함수를 두었는데, 점화식을 통해 가부를 판단한다.

$D_i$ : row가 k로 제한된 상태에서 i번째 파일까지 쓸 때 width의 최소 길이

$D_i$ : min(D[j] + max_file_length(j+1,i) + 1) // 각 column 사이 공백을 고려하여 "+1"을 하였다.

D_n <= w+1이면 True를 반환해준다.

 

첫 시도에서 max_file_length를 segment tree를 사용하여 구했으나 $O(N^2 log^2 N)$으로 TLE가 났다.

두 번째 시도에서 N<=5000임을 알고 전처리로 구해두었고 $O(N^2 log N)$으로 AC를 받았다.

 

소스코드

#include<bits/stdc++.h>
const int N = 5e3+10;
using namespace std;
#define endl '\n'

int LEN[N], Query[N][N];

string S[N];

const int INF = 2e9;
int D[N], n, K;
bool solve(int k){
    for(int i=1; i<N; ++i) D[i]=INF;
    for(int i=1; i<=n; ++i){
        for(int j=max(0,i-k); j<i; ++j){
            D[i] = min(D[i], D[j] + Query[j+1][i] + 1);
        }
    }
    return D[n]-1<=K;
}

int P[N], W[N];
void back(int k){
    for(int i=1; i<N; ++i) D[i]=INF;
    for(int i=1; i<=n; ++i){
        for(int j=max(0,i-k); j<i; ++j){
            int Q = Query[j+1][i];
            if(D[i] > D[j] + Q + 1){
                D[i] = D[j] + Q + 1;
                P[i] = j;
                W[i] = Q;
            }
        }
    }
    vector<int> pr, iv(1,n);
    while(iv.back()) {
        pr.push_back(W[iv.back()]);
        iv.push_back(P[iv.back()]);
    }
    reverse(pr.begin(),pr.end()); 
    vector<int> jv=iv;
    iv.pop_back();
    reverse(iv.begin(),iv.end());
    reverse(jv.begin(),jv.end());

    cout << k << " " << pr.size() << endl;
    for(auto&t:pr) cout << t << " "; cout << endl;
    for(int i=0; i<k; ++i){
        for(int j=0; j<pr.size(); ++j){
            if(jv[j]==iv[j]){
                for(int l=0; l<=pr[j]; ++l) cout << " ";
            }
            else{
                string &s=S[++jv[j]];
                cout<<s;
                for(int l=s.size(); l<=pr[j]; ++l) cout << " ";
            }
        }
        cout << endl;
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> K;
    for(int i=1; i<=n; ++i){
        string &s=S[i];
        cin>>s;
        LEN[i]=s.size();
    }
    for(int i=1; i<=n; ++i) Query[i][i]=LEN[i];
    for(int i=1; i<n; ++i) for(int j=1; j<=n-i; ++j) Query[j][j+i]=max(Query[j][j+i-1],Query[j+i][j+i]);

    int s=1, e=n, ans=e;
    while(s<=e){
        int m = (s+e)/2;
        if(solve(m)) e=m-1, ans=m;
        else s=m+1;
    }
    back(ans);
}

---

H. Heating Up

문제

원형 수열이 주어진다. k의 threshold값을 가지고 임의의 위치에서 시작한다.

해당 위치의 값이 k이하이면 k에 그 수를 더하고 수열에서 제거한 후, 인접한 자리로 이동할 수 있다.

모든 수를 없앨 수 있는 최소 threshold값을 구하여라

 

풀이

parametric search를 하면 될 것 같은데, 깊게 구상해보지 못했다.

---

I. IXth Problem

문제

로마자 숫자 표기를 위한 문자(MDCLXVI)가 각기 $A_i$개 주어져 있다.

몇 가지 종류의 로마자 숫자를 사용하여 $A_i$를 모두 0으로 만들 때, 사용될 숫자의 최소 개수를 구하고 사용된 로마자 숫자 종류를 출력하라

 

풀이

모르겠다 ㅠ

---

J. Jet Set

문제

주어진 좌표 순서대로 여행을 떠날 것이다.

각 여행은 좌표간 거리가 짧은 경로로 진행된다.

이때, 지나가지 않은 경도선이 있다면 출력하고 없다면 "YES"를 출력하라

 

풀이

간단하게 구현할 수 있을 것 같지만, 맡은 문제가 아니라 넘겼다..

---

K. Knitpicking

문제

순식간에 다른 분이 푸셔서 잘 모른다.

---

L. Lucky Shirt

문제

예제만 보면 기댓값을 출력하는 문제인데, 읽어보지 못했다.