NANC(North Central North America) 2020

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

NCNA 2020

22.09.23

전체 12문제 중 4문제 해결

이번 셋은 참 EOF와 String, Geometry, Implementation을 좋아하는 것 같다. 구데기다

 

3인 1컴의 한계에 대해 다시 고민해게 되었다.

사실 작년까지는 제각기 팀원들이 아이디어를 내면 순식간에 뚝딱 구현이 가능했었는데,

아쉽게도 올해 팀원들에게는 미안한 말이 되겠지만 뚝딱 구현까지는 어려운 것 같았다.

CDEF를 내가 해결했었고, 맡겨두었던 HJK에서 절반의 시간을 사용했었다.

내 실력이 지금에 비해 압도적으로 좋았다면 이런 문제도 없었겠다는 생각에 게을렀던 나를 탓하게 된다.

 

팀 연습이 마무리 될 때 쯤 다음과 같은 생각을 하게 되었다.

1. 어려운 문제들 아이디어를 내가 낼 수 있도록 고민하고 구현은 팀원에게 맡긴다.

2. 모든 구현을 내가 하고 팀원들이 아이디어를 고민할 수 있게 한다.

3. 초반에 어지간한 문제들을 내가 해결하고 어려운 문제들에 대해 팀원들과 함께 논의한다.

아주 독선적이라는 생각일지 모르겠지만, 지금 당장에의 팀 연습 과정을 볼때,

대회 성과를 내기 위해서는 해결해야 할 문제가 확실히 있는 것 같다.

어떤 것을 선택할지, 또 다른 선택지가 생길지는 대회 전까지 차차 고민해봐야 할 것 같다.

---

A. LogDB

문제

첫 줄에 여러 개의 함수이름과 그 인자의 수 및 관계를 알려준다. 쿼리문들이 주어지는데 각 줄에 대해 해당 쿼리로 사용될 수 있는 함수의 개수를 출력하라.

 

풀이

구현 문제인 것 같다.

---

B. Ride-Hailing

문제

그래프에서 에지의 가중치는 두 노드 사이를 이동하는데 걸리는 시간이다. 몇 개의 trip이 주어지는데 이동하고 싶은 두 정점과 trip의 시작 시간이 주어진다. trip은 항상 가이드가 필요한데, 동시에 진행되는 trip이 있을 경우 가이드가 여러 명 필요하다. 필요한 최소 가이드 수를 구하여라.

 

풀이

문제를 제대로 확인하지는 않았는데, 아마 Floyd-Warshall로 모든 정점 쌍 최단경로를 구해놓고 각 trip의 DAG를 구한 뒤 잘 잘라보거나, 회의실 배정 문제같이 그리디하게 구하면 될 것 같았다.

---

C. Redundant Binary Notation

문제

2진수는 각 자리수가 $2^k$를 나타내고 0, 1로 이루어져 있다. 이 문제에서는 각 자리수는 [0, t]의 정수로 이루어질 수 있는데, 특정 수 N을 RBN으로 표기할 수 있는 방법의 수를 구하여야 한다.

 

풀이

메모이제이션과 DP를 사용하면 되는데, 앞에서부터 x자리수에 y(0<=y<=t and y<=x)를 사용한 경우 (x-y)/2를 표기하는 방법의 수를 찾으면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 998244353;
map<ll, ll> mp;
int b;
ll dfs(ll w){
    if(mp[w]) return mp[w];
    if(w<2) return 1LL;
    ll sum=0;
    for(int i=w&1; i<=b; i+=2){
        if(w<i) break;
        sum = (sum + dfs((w-i)>>1)) % M;
    }
    return mp[w]=sum;
}
int main(){
    ll n;
    scanf("%lld%d",&n,&b);
    printf("%lld",dfs(n));
}

---

D. Substring Characters

문제

문자열 S에 포함된 기저 문자 set s를 구하자.

S의 연속하는 substring 중 s의 원소를 모두 포함하는 경우를 t라고 하자.

t의 원소들 중 앞 뒤를 떼면 s의 모든 원소를 포함하지 않는 경우를 p라고 하자.

p의 수를 구해라.

 

풀이

투포인터로 구해보면 된다. s의 모든 원소를 포함할 때까지 뒷쪽 포인터를 증가시키고, s의 모든 원소를 포함하는동안 앞족 포인터를 증가시키면서 하나씩 카운트한다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    for(char s[100];~scanf("\n%s",s);){
        int no=0, cno=0, p=0, ch=0;
        map<char,int> mp, cmp;
        set<string> st;
        for(int i=0; s[i]; ++i) if(mp[s[i]]==0) mp[s[i]]=++no;
        for(int i=0, j=0; s[i]; ++i){
            for(;s[j]&&cno!=no;++j) if(cmp[s[j]]++==0) ++cno;
            for(;i<j&&cmp[s[i]]>1;) --cmp[s[i]], ++i;
            if(cno == no){
                string ss;
                for(int x=i; x<j; ++x) ss.push_back(s[x]);
                st.insert(ss);
                if(i==0 && !s[j]) ch=1;
            }
            if(cmp[s[i]]--==1) --cno;
        }
        printf("%d\n",st.size()-ch);
    }
}

 

---

E. Curve Speed

문제

커브에서의 속도를 구하는 문제인데 풀이를 보자. 매우 쉽다.

 

풀이

문제에서 주어진 수식을 구하고 소수 첫 자리에서 반올림하면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    int r;
    double s;
    for(;~scanf("%d %lf",&r,&s);){
        int p = (int)(sqrt((r*(s+0.16))/0.067)+0.5);
        printf("%d\n",p);
    }
}

---

F. Agamemnon's Odyssey

문제

(문제를 안보고 팀원이 구한 풀이만 듣고 구현했다.)

 

풀이

k=1일 때, 트리에서 두 정점 간 거리 중 가장 긴 것을 구하면 된다.

k=2 이상일 때, 모든 간선의 합을 구하면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5+100;
vector<pair<ll,ll>> e[N];
ll v[N];
ll pmx;
ll dfs(ll w){
    v[w]=1;
    ll mx=0, mx2=0;
    for(auto&[u,c]:e[w]){
        if(v[u]) continue;
        ll t = dfs(u) + c;
        if(mx<t) mx2 = mx, mx = t;
        else if(mx2<t) mx2=t;
    }
    if(mx&&mx2&&pmx<mx+mx2) pmx=mx+mx2;
    return mx;
}

int main(){
    ll n, k, tot=0;
    scanf("%lld%lld",&n,&k);
    for(ll i=1; i<n; ++i){
        ll x, y, w;
        scanf("%lld%lld%lld",&x,&y,&w);
        e[x].push_back({y,w});
        e[y].push_back({x,w});
        tot+=w;
    }
    if(k==1){
        ll st;
        for(ll i=1; i<=n; ++i) if(e[i].size()>1) {st=i; break;}
        dfs(st);
        printf("%lld",pmx);
    }
    else printf("%lld", tot);
}

---

G. Safest Taxi

문제

도로와 각 차선에 대한 정보가 주어진다. 각 차선은 좌회전/우회전/직진 중 한가지 이상을 할 수 있다.

쿼리는 시작도로와 종료도로 그리고 X, Y가 주어지는데, 시작도로에서 종료도로까지 X 이하의 좌회전과 Y 이하의 차선 변경으로 도달할 수 있으면 그 최소 시간을 출력하고 불가능하다면 -1을 출력하라.

 

풀이

이것도 구현 문제라서 그냥 풀지 않았다,,,

---

H. Digital Speedometer

문제

0<tf<tr<1에 대해 입력되는 수 s에 대해 아래와 같이 수를 출력한다. (아래의 i = floor(s))

1. i<=s<=i+fr : i

2. i+tr<=s<=i : i+1

3. i+tf<=s<=i+tr : 

 1) 가장 최근에 [i+tf,i+tr] 범위 밖의 수가 i+tr보다 작다면 : i

 2) 가장 최근에 [i+tf,i+tr] 범위 밖의 수가 i+tr보다 크다면 : j

4. 0<s<1 : 1

 

풀이

분기 그대로 구현하면 된다. (업솔빙)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
double s[10000];
int main(){
    double tf, tr;
    scanf("%lf%lf",&tf,&tr);
    for(int i=0;~scanf("%lf",&s[i]); ++i){
        if(s[i]==0.0) puts("0");
        else if(s[i]<1.0) puts("1");
        else if(s[i]<=double(int(s[i]))+tf) printf("%d\n",int(s[i]));
        else if(double(int(s[i]))+tr<=s[i]) printf("%d\n",int(s[i])+1);
        else{
            for(int j=i-1; j>=0; --j){
                if(s[j]<=double(int(s[i]))+tf) {printf("%d\n",int(s[i])); break;}
                else if(double(int(s[i]))+tr<=s[j]) {printf("%d\n",int(s[i])+1); break;}
            }
        }
    }
}

---

I. Staggering to the Finish

문제

처음에 문제를 보고 '망연자실한 물고기'인가 했는데 finish였었다.

제대로 읽지는 못했는데 운동장의 형태(반원 2개 + 직진구간 2개)가 주어지고 각 lane에 대해 출발점을 얼마나 당겨야 하는지 혹은 미뤄야하 하는지 구하는 문제인 것 같다.

---

J. Ada Loveslaces

문제

신발끈을 묶을 것이다. 신발끈 구멍이 2N개(0번부터 2N-1번) 있다.

2k번째 구멍과 2k+1번째 구멍은 같은 행에 있고 거리는 s이다.

k번째 구멍과 k+2번째 구멍은 같은 열에 있고 거리는 d이다.

각 구멍을 통과할 때마다 t의 길이가 필요하다.

0, 1번 구멍은 무조건 가로로 연결되어야 한다.

2N-1, 2N-2번 구멍에서 무조건 신발끈이 나와야 한다.

신발끈의 길이들이 주어질 때 2N-1, 2N-2 구멍에서 나오는 신발끈의 길이가 $f_min < 길이 < f_max$인 묶는 방법의 수를 구하여라

 

풀이

dfs로 모든 묶는 방법의 수를 구할 수 있다.

직접 해보면 되는줄 알았는데 잘 되지 않았던 것 같다.

---

K. ICPC Record Matching

문제

Input Section과 Output Section은 empty line으로 구분되어 있다.

각 Section의 각 줄은 "First_Name(tab)Last_Name(tab)E-mail"로 주어진다.

대소문자를 무시했을 때 Input Section의 쿼리와 Output Section의 쿼리가 매칭된다면 두 쿼리는 사라진다.

남은 쿼리에 대해

Input Section이라면 "I E-mail Last_Name First_Name"

Output Seciton이라면 "O E-mail Last_Name First_Name"를 출력해라.

남은 쿼리가 없다면 "No mismatches."를 출력해라

 

풀이

구현 문제인 것 같다.

구현에 이슈가 있었던 것 같다.

---

L. Codenames

문제

(문제를 확인하지 않았다..)