Codeforces Educational #82

A. Erasing Zeroes

Problem - A - Codeforces

Problem - A - Codeforces

길이 $n$의 binary string $s$가 주어진다.

$1$과 $1$ 사이에 존재하는 $0$의 개수를 세는 문제이다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        int cnt = 0;
        int prv = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') {
                cnt += (prv == -1 ? 0 : i - prv - 1);
                prv = i;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

 

 

B. National Project

Problem - B - Codeforces

Problem - B - Codeforces

길이 $n$의 도로를 수리해야 한다.

해당 지방은 날씨가 좋은 $g$일과 날씨가 나쁜 $b$일이 번갈아가며 나타나는데 ($g, b, g, b, \dots$)

날씨가 좋은 날 수리한 구간은 퀄리티가 좋고, 날씨가 나쁜 날 수리한 구간은 퀄리티가 나쁘다.

날마다 도로를 한 unit만큼 수리할지, 그냥 쉴지 선택할 수 있다.

전체 도로의 절반 이상이 퀄리티 좋은 상태로 수리가 끝나려면 최소 며칠이 필요한지 구해야 한다.

 

반드시 퀄리티 좋아야 하는 구간의 길이 $h = \frac{n+1}{2}$

 

$q = h / g$, $r = h\% g$, $f = \begin{cases}1  & \text{if $r = 0$} \\ 0  & \text{else}\end{cases}$일 때

날씨 좋은 날이 $h$일이 되는 데 필요한 최소 일수 $k = h + b * (q - f)$

 

답은 $\max(n, k)$이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        ll n, g, b;
        cin >> n >> g >> b;
        ll h = (n + 1) / 2;
        ll q = h / g;
        ll r = h % g;
        ll cnt = h + b * max(0ll, (r ? q : q-1));
        cout << max(n, cnt) << '\n';
    }
    return 0;
}

 

 

C. Perfect Keyboard

키보드는 $26$개의 소문자 알파벳 한 줄로 구성된다.

패스워드가 문자열 $s$로 주어지는데,

$s$ 안에서 이웃한 문자들은 키보드에서도 이웃해야 한다.

위 조건을 만족하는 키보드 조합을 구하는 문제이다.

 

그래프로 모델링하여 생각할 수 있다.

 

키보드 구성이 불가능한 케이스

1) 어떤 정점에 연결된 간선이 3개 이상인 경우

2) 사이클이 존재하는 경우

 

#include <bits/stdc++.h>
using namespace std;
 
vector<bool> visited(26);
vector<set<int> > adj;
 
bool dfs1(int u, int p) {
    bool ret = false;
    visited[u] = true;
    for (int v: adj[u]) {
        if (v == p) continue;
        if (!visited[v]) ret = ret || dfs1(v, u);
        else return true;
    }
    return ret;
}
 
void dfs2(int u) {
    cout << (char)('a'+u);
    visited[u] = true;
    for (int v: adj[u]) {
        if (!visited[v]) {
            dfs2(v);
        }
    }
}
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        adj.clear(); adj.resize(26);
        for (int i = 1; i < s.size(); i++) {
            int a = s[i-1] - 'a';
            int b = s[i] - 'a';
            adj[a].insert(b);
            adj[b].insert(a);
        }
        
        bool flag = false;
        visited.assign(26, false);
        for (int i = 0; i < 26; i++) {
            if (!visited[i]) {
                flag = dfs1(i, i);
                if (flag) break;
            }
            if (adj[i].size() >= 3) {
                flag = true;
                break;
            }
        }
        if (flag) {
            cout << "NO\n";
        }
        else {
            cout << "YES\n";
            visited.assign(26, false);
            for (int i = 0; i < 26; i++) {
                if (!visited[i] && adj[i].size() == 1) dfs2(i);
            }
            for (int i = 0; i < 26; i++) {
                if (!visited[i]) cout << (char)('a'+i);
            }
            cout << '\n';
        }
    }
    return 0;
}

 

 

D. Fill The Bag

Problem - D - Codeforces

Problem - D - Codeforces

사이즈가 $n$인 가방 하나와 $m$개의 박스가 주어진다.

박스의 사이즈는 모두 $2$의 거듭제곱 꼴이다.

$2^p$ 사이즈의 박스 하나를 $2^{p-1}$ 사이즈의 박스 2개로 나눌 수 있다.

가방을 박스로 빈틈없이 채울 때 필요한 최소 division 횟수를 구하는 문제이다.

 

우선 박스들의 크기 합이 $n$ 이상이면 가방을 채울 수 있다.

모든 박스를 크기 $1$의 박스로 만들 수 있기 때문이다.

 

binary representation of $n$의 낮은 비트부터 채우자.

1) $i$번째 비트가 0인 경우

$2^i$ 사이즈 박스가 필요 없음을 알 수 있다.

남은 $2^i$ 사이즈 박스들은 $2^{i+1}$ 사이즈 박스로 만든다.

 

2) $i$번째 비트가 1인 경우 & $2^i$ 사이즈 박스가 있는 경우

$2^i$ 사이즈 박스 하나를 사용한다.

남은 $2^i$ 사이즈 박스들은 $2^{i+1}$ 사이즈 박스로 만든다.

 

3) $i$번째 비트가 1인 경우 & $2^i$ 사이즈 박스가 없는 경우

남은 박스들 중 가장 작은 박스의 사이즈를 $2^k$라고 하자.

해당 박스를 쪼개서 $2^i$ 사이즈 박스를 만들어야 한다.

이때 필요한 division 횟수는 $k-i$이다.

이 과정에서 만들어지는 박스들을 통해 $n$의 $i \le x \le k-1$번째 비트들을 채울 수 있다.

ex) $10000$ -> $1111$

이후 $n$의 $k$번째 비트부터 다시 시작한다.

$2^{k-1}$ 사이즈 이하의 박스들을 모두 합쳐도 $2^k$ 사이즈 박스를 만들 수 없기 때문이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int log2(ll a) {
    int ret = 0;
    while (a > 1) {
        ret++;
        a /= 2;
    }
    return ret;
}
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        ll n, m, sum = 0;
        cin >> n >> m;
        vector<int> box(65);
        while (m--) {
            ll a; cin >> a;
            sum += a;
            box[log2(a)]++;
        }
        if (n > sum) {
            cout << -1 << '\n';
            continue;
        }
        ll ans = 0;
        for (int i = 0; i < 64; i++) {
            if (n & (1LL << i)) {
                if (box[i]) {
                    box[i]--;
                }
                else {
                    while (!box[i]) i++, ans++;
                    box[i]--; i--;
                    continue;
                }
            }
            box[i+1] += box[i] / 2;
        }
        cout << ans << '\n';
    }
    return 0;
}