Codeforces Round #530 (Div. 2) A ~ D

codeforces.com/contest/1099

Dashboard - Codeforces Round #530 (Div. 2) - Codeforces

혼자 풀은 문제: A, C

풀이만 보고 풀은 문제: B, D

풀이와 코드 전부 본 문제: E, F

 

문제 난이도

A - 800
B - 1100

C - 1200

D - 1600

E - 2100

F - 2400

 

 

E는 풀이가 있긴한데 풀이 이해를 못하겠고, F는 세그먼트 트리로 푸는 Tree DP인데 일반 Tree DP조차 문제를 몇 개 풀어보지 못해서 코드를 봐도 이해가 잘 안간다. 나중에 공부해야할 것 같다.

 

 

 

 

 

A. Snowball

눈의 무게를 현재 위치한 높이만큼 더하다가, 돌을 만나면 돌의 무게만큼 빼면 되는 문제이다.

여기서 주의할 점은 눈이 음수이면 눈의 중량이 음수가 아닌 0이 된다는 것이다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int a,b,c,d,e,f;
    cin >> a >> b;
    cin >> c >> d;
    cin >> e >> f;
 
    for(int i = b; i > -1; i--){
        a += i;
        if(i==d) a-=c;
        if(i==f) a-=e;
        if(a<0) a=0;
    }
    if(a<0) cout << 0;
    else cout << a;
}

 

 

B. Squares and Segments

문제를 해석하기 힘들어서 해법을 검색해서 찾아보았다.

지금도 문제를 제대로 이해를 못했지만, 일단 제일 먼저 생각나는 것은 한 변의 길이가 n인 정사각형이 있을 때의 답은 2*n이고, 한 변의 길이가 n-1일때의 정사각형이 있을 때의 답은 2*(n-1)인 것을 알 수 있다.

이제 최소의 갯수로 최대의 넓이를 구하는 방법을 이용하여 만약 넓이가 x인 값이 들어올 때, 직사각형도 최대한 정사각형과 비슷하게 만들어서 그렇게 만든 직사각형 혹은 정사각형의 넓이가 x이상이 나오면 코드를 멈추고 출력하도록 만들었다.

코드에서는 while문을 사용하였는데, 왜 a*b의 값이 x이상이냐면 만약 a*a(a=b일떄) = x인 경우 답을 2*a로 출력해야 하는데 x초과(a*b<=x)로 해버리면  a*b = x일때 while문이 한번 더 돌아가기 때문에 while문의 조건을 a*b<x로 하였다

 

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

int main()
{
    int a,b,x;
    cin >> x;
    a = b = 0;
    while (a * b < x)
    {
        if(b>a) a++;
        else b++;
    }
    cout << a + b;
}

 

 

 

C. Postcard

-캔디: 바로 앞 문자를 없애거나, 아무 행동도 하지 않음

-눈송이: 바로 앞의 문자를 없애거나, 바로 앞의 문자를 복사하여 몇 번이고 붙이던가, 아무행동도 하지 않을 수 있다.

 

이건 잘 생각해보면 몇가지 케이스로 나눌 수 있다.

일단 for문으로 문자를 탐색하여 알파벳의 갯수, 캔디의 갯수, 눈송이의 갯수를 구한다.

그다음 for을 통해 아래 과정을 거치면 된다.

 

1. 입력값에 나온 알파벳의 수가 요구하는 길이(k)보다 긴 경우

1-1. 눈송이가 없을 경우

눈송이가 문자를 몇 번이고 복사하는 기능이 있는데, 이 눈송이가 없으면 k 길이만큼 문자열을 만들지 못한다.

1-2. 눈송이가 하나라도 있을 경우

눈송이 하나만 가지고 문자열을 필요한 길이만큼 문자를 복사해서 붙이면 된다. 그래서 딱 1개만 있어도 요구하는 길이만큼 문자열을 만들 수 있다.

1-3. 눈송이가 하나 있지만 알파벳을 복사 못하는 경우

이경우는 문자열에서 알파벳이 나오기전에 눈송이가 먼저 나오는 것이다. ex) *b, 3

이러면 문자 복사를 못하므로 k 길이만큼 문자열을 만들 수 없다.

 

2. 입력값에 나온 알파벳의 갯수가 요구하는 길이(k)보다 작은 경우

2-1. (알파벳의 갯수) - (캔디의 갯수) - (눈송이의 갯수)의 값이 k 보다 클 경우

캔디와 눈송이의 기능인 글자를 하나 없애는 기능을 모든 캔디와 눈송이에 적용하여도 알파벳의 수가 k보다 클 경우 k 길이만큼 문자열을 만들지 못한다.

2-2. (캔디의 갯수)와 (눈송이의 갯수)가 충분하지만 문자를 삭제시키지 못하는 경우

ex) *?bba, 2  |   b???abc, 1

이런 경우에는 k길이만큼 문자열을 만들지 못한다.

2-3. 그 이외의 경우

어떠한 수(err)를 (알파벳의 갯수) - (요구하는 길이)로 초기화 시킨다.

그리고 err = 0이 될 때까지 캔디와 눈송이를 만날때마다 err의 값에 1을 빼준다. err = 0이 되면 그 다음부터는 눈송이와 캔디를 만나면 넘어가면 된다.

 

 

이렇게 해서 나온게 아래 코드이다.

먼저 1-1과 2-1은 처음부터 구할 수 있으므로 바로 exit(0)을 통해 나가주고, 1-3과 2-2는 답에 해당하는 문자열을 다 만들고 길이를 확인하여 Impossible을 출력하게 만들었다.

 

n = input()
k = int(input())
a,c,s = 0,0,0
ans = ''
for i in range(len(n)):
    if n[i] == '?':c+=1
    elif n[i] == '*':s+=1
    else:a+=1
if (a - c - s > k) or (a < k and s == 0) : print('Impossible'); exit(0)

if a < k and s != 0:
    err = 0
    for i in range(len(n)):
        if n[i] == '*' and not err and len(ans):
            ans += ans[len(ans)-1]*(k-a)
            err = 1
        elif 97 <= ord(n[i]) <= 122: ans+=n[i]
        else: continue
else:
    err = a-k
    for i in range(len(n)):
        if n[i] in ['?','*'] and err and len(ans):
            ans = ans[:len(ans)-1]
            err -= 1
        elif 97 <= ord(n[i]) <= 122: ans += n[i]
        else: continue
if len(ans) != k:print('Impossible')
else:print(ans)

 

 

 

 

D. Sum in the tree

 

문제에서 짝수 깊이에 해당하는 s_v의 값들을 전부 지워버렸다고 한다.

그런다음 각 노드마다 최소의 a_v의 값을 구하고 1부터 n까지 a_i의 합을 모두 구하라는 문제이다.

 

일단 구조체를 이용하여 루트로 부터 노드v까지의 누적합(s_v)인 value, 해당 노드의 값(a_v)인 r_value, 자손들을 vector에 넣어준 children을 만들어준다.

 

그리고 두 가지 상황으로 나눈다.

1. 짝수 깊이에 있는 노드가 리프노드가 있는 경우

a_v의 최소 값을 구하므로 a_v = 0이다. 이러면 value는 부모노드의 value와 같고, r_value는 0이다.

2. 홀수 깊이에 있는 노드가 리프노드인 경우

루트노드가 아닌이상 해당 리프노드의 부모 노드는 짝수 깊이의 노드임이 자명하다.

a_v의 최소 값을 구해야하므로 부모 노드의 자식 노드들, 그니까 홀수 깊이의 노드의 부모노드가 가지고 있는 자식 노드중에 가장 작은 값을 홀수 깊이의 노드의 부모노드의 value값으로 정한다.

 

그림으로 설명하자면

 

위와 같은 그림이 입력으로 주어졌을 때

s_2의 값을 min(s_3, s_4) = 3으로 정하는 것이다.

그래야 3번 노드의 r_value(a_3)는 0이고, 4번 노드의 r_value(a_4)는 2가 되어 최소값을 구할 수 있다.

 

이 부분을 잘 구현하면 된다.

DFS1은 먼저 지워진 짝수 깊이의 s_i(value)의 값을 정해주는 함수이고, DFS2는 s_i의 값을 토대로 a_i(r_value)을 정해주는 함수이다.

그리고 모든 a_i의 최대 합이 10**9 * 10**5이므로 ans의 자료형을 long long으로 해주었다.

 

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

typedef struct node{
    int value;
    int r_value;
    vector<int> children;
}Node;

Node NODE[100000];

void DFS1(int x, int h){
    for(auto nx: NODE[x].children){
        if(h % 2 == 0 && (NODE[x].value == -1 || NODE[x].value > NODE[nx].value)){
            NODE[x].value = NODE[nx].value;
        }
        DFS1(nx,h+1);
    }
}

void DFS2(int x){
    for(auto nx: NODE[x].children){
        if(NODE[nx].value == -1) NODE[nx].r_value = 0;
        else NODE[nx].r_value = NODE[nx].value - NODE[x].value;
        if(NODE[nx].r_value < 0){
            cout << -1;
            exit(0);
        }
        DFS2(nx);
    }
}

int main()
{
    int n,x;

    cin >> n;
    for(int i=0; i<n; i++){
        NODE[i].r_value = -1;
    }

    for(int i=1; i<n; i++){
        cin >> x; x--;
        NODE[x].children.push_back(i);
    }
    for(int i=0; i<n; i++) {
        cin >> NODE[i].value;
    }
    DFS1(0,1);
    NODE[0].r_value = NODE[0].value;
    DFS2(0);
    long long ans = 0;
    for(int i=0; i<n; i++)
        ans += NODE[i].r_value;
    cout << ans;
}