본문 바로가기

공부/알고리즘 문제풀이

[Codeforces] Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

반응형

6번째 코포 도전기, 풀이 시작합니다!




A. Packets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have n coins, each of the same value of 1.

Distribute them into packets such that any amount x (1xn) can be formed using some (possibly one or all) number of these packets.

Each packet may only be used entirely or not used at all. No packet may be used more than once in the formation of the single x, however it may be reused for the formation of other x's.

Find the minimum number of packets in such a distribution.

Input

The only line contains a single integer n (1n109) — the number of coins you have.

Output

Output a single integer — the minimum possible number of packets, satisfying the condition above.

Examples
input
Copy
6
output
Copy
3
input
Copy
2
output
Copy
2
Note

In the first example, three packets with 12 and 3 coins can be made to get any amount x (1x6).

  • To get 1 use the packet with 1 coin.
  • To get 2 use the packet with 2 coins.
  • To get 3 use the packet with 3 coins.
  • To get 4 use packets with 1 and 3 coins.
  • To get 5 use packets with 2 and 3 coins
  • To get 6 use all packets.

In the second example, two packets with 1 and 1 coins can be made to get any amount x (1x2).



문제 해석


n이라는 수가 주어집니다!

그리고 '패킷'이라는 단위가 있습니다.

패킷은 딱 하나의 값을 가질 수 있습니다!

패킷은 중복해서 사용 불가능합니다.

다른 값을 가지는 패킷은 여러 개 사용할 수 있습니다!


이 때, 1<= x <= n일 때, 모든 x에 대하여 패킷의 값을 더해서 x를 나타내고 싶어합니다!

이 때 필요한 최소한의 패킷 수를 구하세요! 

사용한 패킷은, 다른 수에 대해서 필요한 패킷의 수를 구할때는 다시 사용할 수 있습니다!


ex)

1은 1의 패킷 하나로 얻을 수 있죠!.

2는 2의 패킷 하나로 얻을 수 있습니다!

3의 경우는 1과 2의 패킷으로 얻을 수 있습니다.

4의 경우는 4의 패킷을 이용해서 구할 수 있죠

5의 경우는 1과 4의 패킷을 사용하면 됩니다.

6의 경우는 2와 4의 패킷이 필요합니다.


어떻게 풀까?


모든 수를 나타내는 아주 심플한 방법이 있죠.

바로 이진수로 나타내는 것 입니다.

수에서 1을 뺀 것의 로그 값을 구한 다음에 그 값에 1을 더해주면 됩니다.


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#pragma once
#include<cstdio>
#include<vector>
 
using namespace std;
int getLog(int n) {
    int res = 0;
    while (n) {
        res++;
        n >>= 1;
    }
    return res;
}
int main() {
    int n;
    scanf("%d\n"&n);
    printf("%d\n", getLog(n));
 
    return 0;
}
cs


시간 복잡도


시간 복잡도는 입력값의 로그를 구하기만 하면 되기 때문에, O(log n) 입니다.



B. Reach Median
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a of n integers and an integer s. It is guaranteed that n is odd.

In one operation you can either increase or decrease any single element by one. Calculate the minimum number of operations required to make the median of the array being equal to s.

The median of the array with odd length is the value of the element which is located on the middle position after the array is sorted. For example, the median of the array 6,5,8 is equal to 6, since if we sort this array we will get 5,6,8, and 6 is located on the middle position.

Input

The first line contains two integers n and s (1n210511s109) — the length of the array and the required value of median.

The second line contains n integers a1,a2,,an (1ai109) — the elements of the array a.

It is guaranteed that n is odd.

Output

In a single line output the minimum number of operations to make the median being equal to s.

Examples
input
Copy
3 8
6 5 8
output
Copy
2
input
Copy
7 20
21 15 12 11 20 19 12
output
Copy
6
Note

In the first sample, 6 can be increased twice. The array will transform to 8,5,8, which becomes 5,8,8 after sorting, hence the median is equal to 8.

In the second sample, 19 can be increased once and 15 can be increased five times. The array will become equal to 21,20,12,11,20,20,12. If we sort this array we get 11,12,12,20,20,20,21, this way the median is 20.


문제 해석


수열이 주어집니다! 

주어지는 수열은 임의의 숫자로 구성되어있습니다.

단, 주어지는 수열의 개수는 무조건 홀수입니다.


이 수열을 정렬하면, 가운데의 배열의 수를 알 수 있습니다.


그리고 우리는 한 번에 하나의 연산을 할 수 있습니다.

딱 한 원소에 대해서 1을 빼거나, 1을 증가시키는 연산입니다!


만약 s가 주어졌을 때,

정렬한 후에 가운데 값에 s가 오게하기 위한 최소한의 연산의 개수를 구하세요!


예를들어,

6 5 8 의 경우에는

정렬한 후에 5 6 8이 됩니다.

이 때, 가운데에 8이 오게 하기 위해서는 6에 2번의 연산을 통해 6을 8로 만드는 것이 바로 최소 연산의 수 입니다.



어떻게 풀까?


크게 2개로 나눠서 생각해 봅시다.


1번, 중앙 값이 s보다 작다.

2번, 중앙 값이 s보다 크다.


중앙 값이 s보다 작다는 것은 무엇을 의미할까요!?

중앙 값을 s로 만들기 위해서, 중앙 값에 s와의 차이만큼 더해줘야 한다는 것이겠죠!

즉, 중앙값이 커집니다!


그렇다면 어떠한 일이 발생할까요!?



중앙 값을 s로 바꿉니다! (a,b,c는 0 이상인 어떤 수 라고하겠습니다. 그리고, a > b 입니다.)

그러면, s가 더 큰 수이기 때문에, s보다 큰 수 바로 직전 위치에 s가 옮겨지고, 중앙 값은 s-a가 옵니다.


중앙 값이 s가 아니기 때문에, 또 다시 중앙값을 바꿉니다.


그러면 위와 같은 일이 반복되어서, s-b가 중앙으로 올 것입니다.

그러면 또 차이만큼 중앙값에 더합니다.


이렇게 해야지 아래와 같이 중앙수를 s로 맞출 수 있습니다.



방법이 보이지 않습니까!?


중앙수가 s보다 작을 때 제가 더하기 연산을 시행해준 부분을 보겠습니다.

바로, 중앙수보다 같거나 큰 값이 나오는곳 까지 입니다!


즉, 일단 입력으로 주어지는 입력을 정렬을 하고 난 뒤에 중앙수가 만약 s보다 작다면, s와 같거나 큰 값이 나올 때 까지 인덱스를 늘리면서,

연산 횟수에는 s와의 차이를 더해주면 됩니다!


반대로, 중앙 값이 s보다 크다면, 중앙 값에 s와의 차이만큼 빼주고, 중앙값은 왼쪽으로 이동하겠죠.

위와 같은 작업을 반복한다면, 중앙값보다 작거나 같은 값이 나올때까지 해당 연산을 실행할 것입니다!

그럼 위와는 반대로 s와 같거나 더 작은 값이 나올때까지 인덱스를 왼쪽으로 옮기면서

연산 횟수에는 여전히 s와의 차이를 더해주면 됩니다.


그리고 주의점 한 가지!

주어지는 수열 모든 수가 s보다 작거나, s보다 클 수도 있습니다.

즉, 인덱스가 0보다 작아지거나, n을 넘어갈 수도 있다는 것이죠!

따라서 이를 넘어가지 않게 바운드 처리를 잘 해 줍시다.


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#pragma once
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
int main() {
    vector<int> vec;
 
    int n, s;
    scanf("%d %d\n"&n, &s);
    for (int i = 0; i < n; i++)
    {
        int in;
        scanf("%d\n"&in);
        vec.push_back(in);
    }
 
    sort(vec.begin(), vec.end());
 
    long long res = 0;
    int i = vec.size() / 2;
    if ( vec[i] < s) 
    {
        while (i < vec.size() && vec[i] < s)
        {
            res += s - vec[i];
            i++;
        }
    }
 
    else {
        while (i >= 0 && vec[i] > s) {
            res += vec[i] - s;
            i--;
        }
    }
    printf("%lld\n", res);
    return 0;
}
 
cs


시간 복잡도


시간 복잡도는 배열을 정렬하는 시간이 있기 때문에 입니다.


C. Equalize
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two binary strings a and b of the same length. You can perform the following two operations on the string a:

  • Swap any two bits at indices i and j respectively (1i,jn), the cost of this operation is |ij|, that is, the absolute difference between i and j.
  • Select any arbitrary index i (1in) and flip (change 0 to 1 or 1 to 0) the bit at this index. The cost of this operation is 1.

Find the minimum cost to make the string a equal to b. It is not allowed to modify string b.

Input

The first line contains a single integer n (1n106) — the length of the strings a and b.

The second and third lines contain strings a and b respectively.

Both strings a and b have length n and contain only '0' and '1'.

Output

Output the minimum cost to make the string a equal to b.

Examples
input
Copy
3
100
001
output
Copy
2
input
Copy
4
0101
0011
output
Copy
1
Note

In the first example, one of the optimal solutions is to flip index 1 and index 3, the string a changes in the following way: "100 "000"001". The cost is 1+1=2.

The other optimal solution is to swap bits and indices 1 and 3, the string a changes then "100 "001", the cost is also |13|=2.

In the second example, the optimal solution is to swap bits at indices 2 and 3, the string a changes as "0101 "0011". The cost is |23|=1.


문제 해석


이진수 2 개가 주어집니다!

할 수 있는 연산은 2개가 있습니다!


1번, 자리 바꾸기!

자리 바꾸기의 비용은 a위치에 있는 원소와 b위치에 있는 원소의 자리를 바꾸는 것입니다.

비용은 a의 위치 b의 위치 절대값 차이 만큼입니다!


예를 들어, 100 에서 1번째와 3번째 '1'과 '0'의 위치를 바꾼다고 하겠습니다.

그렇다면, 비용은 (3-1) = 2 라는 것입니다!


2번, 수 반전!

말 그대로, 한 위치의 원소를 '1' 은 '0'으로 '0'은 '1'로 바꿉니다.


자, 이제, 두 개의 2 진수를 같게 하기 위한 최소의 비용을 구하면 됩니다!


어떻게 풀까?


그렇습니다.

위의 예에서 1번째와 3번째 위치를 바꾸면 비용이 2라는 것에 주목해야합니다.

실은 저 값은 두 수를 그냥 껐다 켜는 비용 2와 같습니다.

다른 말로 하면, 1번 자리 바꾸기는 위치의 차이가 2 이상이 되면 쓸 필요가 없다는 것입니다.

또한, 1번 자리 바꾸기는 한 지점 a를 기준으로

01

10

이나 


10

01


의 경우에만 사용해야 합니다.


우선, 00이나 11의 경우에는 자리 바꾸기를 하는 의미가 없고,

01

01

인 경우에는 어짜피 똑같은 문자이기 때문에 바꿀 필요가 없기 때문입니다!


나머지 경우에는, 만약 두 이진수의 자리 수가 다르면 그냥 나머지 하나를 반전해주면 됩니다.


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#pragma once
#include<string>
#include<cstdio>
 
using namespace std;
char str[2][1000001];
 
int main() {
    int n;
    
    scanf("%d\n%s\n%s"&n, str[0], str[1]);
    int price = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[0][i] == str[1][i]) continue;
        if (str[0][i + 1!= str[1][i + 1]) {
            if (str[0][i] != str[0][i + 1])
            {
                str[0][i + 1= str[0][i];
                price++;
                continue;
            }
        }
 
        price++;
    }
    printf("%d\n", price);
    return 0;
 
 
}
cs


시간 복잡도


문자를 한번 훑는 것 밖에 없기 때문에 시간복잡도는 O(n)입니다.


D. Valid BFS?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The BFS algorithm is defined as follows.

  1. Consider an undirected graph with vertices numbered from 1 to n. Initialize q as a new queue containing only vertex 1, mark the vertex 1 as used.
  2. Extract a vertex v from the head of the queue q.
  3. Print the index of vertex v.
  4. Iterate in arbitrary order through all such vertices u that u is a neighbor of v and is not marked yet as used. Mark the vertex u as used and insert it into the tail of the queue q.
  5. If the queue is not empty, continue from step 2.
  6. Otherwise finish.

Since the order of choosing neighbors of each vertex can vary, it turns out that there may be multiple sequences which BFS can print.

In this problem you need to check whether a given sequence corresponds to some valid BFS traversal of the given tree starting from vertex 1. The tree is an undirected graph, such that there is exactly one simple path between any two vertices.

Input

The first line contains a single integer n (1n2105) which denotes the number of nodes in the tree.

The following n1 lines describe the edges of the tree. Each of them contains two integers x and y (1x,yn) — the endpoints of the corresponding edge of the tree. It is guaranteed that the given graph is a tree.

The last line contains n distinct integers a1,a2,,an (1ain) — the sequence to check.

Output

Print "Yes" (quotes for clarity) if the sequence corresponds to some valid BFS traversal of the given tree and "No" (quotes for clarity) otherwise.

You can print each letter in any case (upper or lower).

Examples
input
Copy
4
1 2
1 3
2 4
1 2 3 4
output
Copy
Yes
input
Copy
4
1 2
1 3
2 4
1 2 4 3
output
Copy
No
Note

Both sample tests have the same tree in them.

In this tree, there are two valid BFS orderings:

  • 1,2,3,4,
  • 1,3,2,4.

The ordering 1,2,4,3 doesn't correspond to any valid BFS order.


문제 해석


BFS는 다음과 같은 순서로 시작됩니다.


1. 노드는 1번부터 n까지 이고, 방향성이 없는 그래프입니다. 큐에는 1 하나만 들어있습니다. 1은 사용 처리합니다.

2. 큐에서 노드 하나를 뽑습니다.

3. 노드 v를 출력합니다.

4. 해당 노드에서 갈 수 있는 노드들 중에서 아직 사용되지 않은 노드들을 랜덤한 순서로 큐에 넣습니다. 그리고 v를 사용 처리 합니다.

5. 큐에 남은 노드가 있다면 2번으로 다시 갑니다.

6. 큐가 비어있으면 종료합니다.


 주어지는 그래프는 트리임을 보장하고, n-1개의 인접한 노드의 정보를 줍니다.


그리고, 마지막에는 트리 순회에 대한 정보를 줍니다.

해당 트리 순회가 가능한 순회 순서가 맞다면 Yes를 출력하고, 아니라면 No를 출력하세요!


어떻게 풀까?


이 부분에서 생각해야할 부분은 랜덤한 순서로 인접 노드를 큐에 담는 부분입니다.

랜덤한 순서이기 때문에, 정말로 어떤 것이 먼저 들어가야 하는지 모릅니다!


하지만, 잘 보시면 해답을 찾을 수 있습니다!

바로, 마지막에 나와야하는 트리 순회에 대한 정보가 나와있기 때문입니다!!

세상에!


즉, 주어진 트리 순회 순서에 따라서 우선순위를 준다고 생각해 봅시다!

그렇다면 우선순위 큐를 이용해서 인접한 노드들을 모두 넣고, 

우선순위가 낮은 순서대로 뽑는다면, 랜덤한 순서에 대해서 어떤 간선을 먼저 큐에 넣을지 정할 수 있습니다!


되게 예제가 간단해서.. 살짝 바꾸겠습니다.



우선 순위를 주어진 순회 순서에 따라서 부여합니다!

1번은 맨 앞에 있기 때문에, 0 순위 입니다!

1 순위는 3번 노드,

2 순위는 2번 노드

3 순위는 4번 노드 입니다. 


1 번 노드를 방문 했었으면, 인접 한 노드들 중에서 2와 3을 큐에 넣어야 합니다.

우선순위 큐에 넣으면, 3번 노드가 순위가 가장 낮기 때문에, 가장 먼저 방문해야 한다는 것을 알 수 있습니다!

다음엔 2번 노드이죠!




이제, 잘 정렬된 방문 노드의 순서를 예쁘게 큐에 쌓아 올리면 됩니다.

다음에 큐에서 나오는 노드는 3번 노드이겠죠!



그럼, BFS를 만드는 방법은 깨달았습니다! 그럼 어떻게 하면 될까요?


간단합니다!

현재 방문한 노드의 순서는 바로 출력하기 전이죠!

즉, 큐에서 노드를 꺼낸 순간입니다.


노드를 꺼낸 순간에 해당 노드가 몇 번째로 출력된 노드인지 알 수 있죠!

그렇다면, 주어진 결과에 대한 노드의 순서와 현재 우리가 진행하고 있는 노드의 순서가 다르면, No를 출력하면 되고,

일치한다면 Yes를 출력하면 됩니다!


한가지 주의해야할 점은, 해당 문제에서 주어지는 결과의 첫 번째 인덱스가 항상 1로 시작하지 않는다는 것입니다!

이 점 유의하면 됩니다!


제 코드에서는 높은 값이 우선순위를 가지는 큐를 사용했기 때문에, 우선순위에 -를 붙였습니다!


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#pragma once
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
vector<int> adj[200001];
bool visit[200001];
int order[200001];
 
int main() {
    int f, r;
    f = r = 0;
    int n;
    scanf("%d\n"&n);
 
    for (int i = 1; i < n; i++) {
        int from, to;
        scanf("%d %d\n"&from, &to);
 
        adj[from].push_back(to);
        adj[to].push_back(from);
    }
    visit[1= true;
    order[1= 1;
    for (int i = 0; i < n; i++) {
        int in;
        scanf("%d \n"&in);
        order[in] = i;
    }
    
    queue<int> que;
    priority_queue<pair<intint> > pq;
    que.push(1);
    visit[1= true;
 
    int cnt = 0;
    while (que.size()) {
        int now = que.front();
        que.pop();
 
        if (order[now] != cnt++) {
            printf("No\n");
            return 0;
        }
 
        for (auto next : adj[now]) {
            if (visit[next]) continue;
            visit[next] = true;
            pq.push({ -order[next], next });
        }
 
        while (pq.size()) {
            int next = pq.top().second;
            pq.pop();
 
            que.push(next);
        }
    }
    printf("Yes\n");
    return 0;
}
cs


시간 복잡도


간선을 한 번씩 방문 하고, 우선순위 큐를 이용한 정렬때문에 시간복잡도는 입니다.


여담


오늘도 떡락입니다.

일단, A가 이진수라는 것을 결국 생각해내지 못했습니다!

N*(N-1)/2로 생각했네요!

그리고, A 해석이 너무너무너무너무너무너무 오래 걸렸어요 ㅠㅠ

C부터 풀었으면 엄청난 떡상!이었을지도 몰라요 ㅋㅋㅋㅋ


그리고 B를 틀려버렸어요..

나중에 보니까 너무 코드를 지저분하게 짰더라구요!

그래서 어디선가 실수를 했던것 같습니다.


코포에 익숙해지고 시퍼요 흑흑...


만년 그린인 것인가.. 민트도 못가는 것인가!


반응형

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

[BOJ] 5622. 다이얼  (0) 2018.09.18
[BOJ] 12782. 비트 우정지수  (0) 2018.09.04
[BOJ] 1405. 미친로봇  (0) 2018.08.31
[BOJ] 2206. 벽 부수고 이동하기  (0) 2018.08.31
[BOJ] 6603. 로또  (0) 2018.08.31