Google Code Jam 2021 Round 1C

Closest Pick

• 문제 설명: N개의 티켓이 주어질 때 각 티켓은 1~K 사이의 정수를 가진다. 다른 티켓이 같은 정수를 가질 수도 있다. 1~K 사이의 정수 c가 랜덤으로 선택될 때 가지고 있는 티켓 중 하나가 N개의 티켓들보다 c에 가장 가까운 숫자일수록 이길 확률은 올라간다. 티켓 두 장을 구입해서 이길 확률을 최대화할 때 확률을 구하라.
  • N개의 티켓에 적힌 숫자와 같은 티켓일 경우 어떤 점수도 얻지 못한다. 두 티켓이 모든 c에 대해 같은 차이를 가지기 때문이다.
• 입력
  • 1 <= T <= 100
  • 1 <= N <= 30
  • Test Set 1: 1 <= K <= 30
  • Test Set 2: 1 <= K <= 10^9
• 출력: 오차 10^-6 이하이면 ok
• 첫번째 접근법: Test Set 1은 K가 적기 때문에 브루트 포싱으로 해결할 수 있을 것이다.
  • 먼저 N개의 티켓에 적힌 숫자들의 집합을 P라고 할 때, 1~K 사이의 모든 숫자에 대해 P에 있는 숫자들 중 가장 작은 차이(min_diff)를 구한다.
  • P를 제외한 다른 숫자들 중에서 min_diff 보다 작은 차이를 가진 숫자를 찾는다. 참고로 숫자가 하나도 없다면 즉, P에 1~K 사이의 모든 숫자가 있다면 확률은 0이 될 것이다.
  • 이전에 선택한 숫자 2개에 대해 확률을 계산해야 한다. 확률은 P에 있는 숫자들보다 가까운 c의 개수를 K로 나눈 것이 된다. 이 확률의 의미는 모든 가능한 c에서 몇 개의 c가 가장 가까운지에 대한 것이다.
  • 여기서 P에 속한 숫자들을 제외한 것들 중 2개를 고르는 경우의 수는 (K-|P|)C(2) 이다. 여기서 C는 이항계수이다. Test Set 1은 K가 적기 때문에 브루트 포싱으로 해결할 수 있다.
  • 시간 복잡도: O(K^3)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;

void solve() {
    int N, K;
    cin >> N >> K;
    set<int> tickets;
    for (int i = 0, tmp; i < N; i++) {
        cin >> tmp;
        tickets.insert(tmp);
    }
    
    int min_diff[K];
    for (int c = 1; c <= K; c++) {
        int& diff = min_diff[c-1];
        diff = 1e9;
        for (auto& t : tickets)
            diff = min(diff, abs(t-c));
    }
    
    int max_wins = 0;
    for (int a = 1; a <= K; a++) {
        if (tickets.find(a) != tickets.end()) continue;
        for (int b = a; b <= K; b++) {
            if (tickets.find(b) != tickets.end()) continue;
            int wins = 0;
            for (int c = 1; c <= K; c++)
                if (abs(a-c) < min_diff[c-1] or abs(b-c) < min_diff[c-1])
                    wins++;
            max_wins = max(max_wins, wins);
        }
    }
    
    double ans = (double)max_wins / K;
    ans = round(ans * 1e6) / 1e6;
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

• 두번째 접근법: Test Set 2 부터는 K가 너무 크기 때문에 모든 c에 대해 시도해볼 수 없다. 두 숫자를 선택할 때 후보의 개수를 줄일 필요가 있다. P에 속한 숫자의 좌우 양 옆의 숫자들이 후보에 적합한데 그 이유는 P에 속한 숫자로부터 멀리 떨어진 숫자를 선택하게 되면 P에 속한 숫자와 선택한 숫자 사이의 중앙값을 기준으로 가까운 숫자들이 나뉘게 되기 때문이다. 예를 들어 P=[1,2,3,7] 이고 K=7일 때 3 4 5 6 7 에서 5를 선택하는 것보다 4 또는 6을 선택하는 것이 가까운 숫자들을 더 많이 포함하게 된다. (5를 선택하면 숫자 5 1개만 가까운 숫자이지만, 4와 6을 선택하게 되면 4,5 또는 5,6을 가까운 숫자로 얻게 된다.)
  • 또한, 후보에 있는 숫자들은 가까운 c의 개수를 계산할 때 어차피 P에 속한 숫자 사이에만 위치하기 때문에 1~K 사이의 모든 숫자에 대해서 가까운 c의 개수를 계산할 필요가 없다. 단순히 후보 숫자의 양 옆에 있는 Pi-1과 Pi 와의 차이를 계산하면 될 것이다. 그 외의 숫자는 어차피 Pi-1과 Pi와 더 가깝기 때문이다.
  • 처음에 후보 숫자들을 고를 때 가까운 c의 개수를 미리 계산할 수 있고, 이후에 가까운 c의 개수를 내림차순으로 정렬했을 때 2개를 선택하면 된다.
  • 참고로 P에 속한 숫자 집합의 양 끝에 대해서도 검사해주어야 한다. 범위 안에만 있다면 P1 - 1 과 Pn + 1 위치를 후보에 넣고 P1 - 1 그리고 K - Pn 을 미리 계산해준다.
  • 예외 처리: Pi-1 과 Pi 사이에 숫자가 3개 이상 있을 때 홀수 개수이면 중간에 1개 숫자가 겹치므로 빼주어야 한다. 예를 들어 3 4 5 6 7 에서 3과 7이 P에 속할 때 4를 선택하면 4,5 해서 2점이고 6을 선택하면 5,6 해서 2점인데 여기서 큰 값 2개를 고르는데 후보가 4 와 6 밖에 없다면 5가 중복되니 가까운 c의 개수를 4와 6중에서 1개 빼주어야 한다. 후보가 무엇인지는 중요하지 않기 때문에 4,6을 선택하거나 4,X 또는 6,X 를 선택할 때 가까운 c의 개수는 정확하게 계산될 수 있다.
  • 시간 복잡도는 O(N)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#define pb push_back
#define sz(c) (int)(c).size()
using namespace std;

const static int _ = []() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
    return 0;
}();

void solve() {
    int N, K;
    cin >> N >> K;
    set<int> pset;
    for (int i = 0, tmp; i < N; i++) {
        cin >> tmp;
        pset.insert(tmp);
    }

    vector<int> tickets(pset.begin(), pset.end());
    vector<int> scores;
    if (tickets.front() > 1) scores.pb(tickets[0]-1);
    if (tickets.back() < K) scores.pb(K - tickets.back());
    for (int i = 1; i < sz(tickets); i++) {
        int diff = tickets[i] - tickets[i-1];
        if (diff > 1) { // 사이에 숫자가 1개 이상 있을 때
            scores.pb(diff >> 1); // 가까운 c의 개수 계산 (두 숫자의 차이 / 2)
            if (diff > 2) { // 숫자가 2개 이상 있을 때
                if ((diff-1) & 1) scores.pb((diff >> 1) - 1); // 홀수개이면 중복 제외
                else scores.pb(diff >> 1); // 짝수개이면 중복이 없으므로 그대로 계산
            }
        }
    }
    
    // 내림차순 정렬
    sort(scores.begin(), scores.end(), [&](int a, int b) { return a > b; });
    int wins = 0;
    // 최대 2개를 선택
    for (int i = 0; i < min(2, sz(scores)); i++) wins += scores[i];
    double ans = (double)wins / K;
    ans = round(ans * 1e6) / 1e6;
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

 

Roaring Years

• 문제 설명: 입력으로 년도가 주어질 때 다음 roaring 년도를 구하라.
  • roaring 의 유무는 숫자가 연속되는 숫자로 이루어진 것을 의미한다.
    2021 -> 20 / 21
    78910 -> 7 / 8 / 9 / 10
    99100 -> 99 / 100
    
    778, 122, 2020 같은 경우는 해당되지 않는다.
    
    
• 입력
  • Test Set 1: 1 <= Y <= 10^6
  • Test Set 2: 1 <= Y <= 10^18
• 첫번째 접근법: Y가 작기 때문에 1씩 증가시켜서 roaring 인지 파악하는 것으로 해결할 수 있다. 연속되려면 시작 번호는 최대 전체 자릿수의 절반정도 차지해야 하므로 L/2 부터 1까지 숫자를 나누는 단위를 줄이면서 roaring인지 시도해볼 수 있다. 큰 단위로 나누어질수록 가장 가까운 숫자이기 때문이다. 주의할 점은 자릿수 올림이 발생할 수 있기 때문에 L만큼 단위를 나눴을 때 연속되지 않는다면 L+1만큼 단위를 나눠서 검사할 필요가 있다. 또한 숫자의 맨 앞에 0이 오는 경우 예외 처리를 해주어야 한다.
  • 시간 복잡도: O(Y)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define sz(c) (int)(c).size()
using namespace std;

bool is_roaring(const string y, int l) {
    int prev = stoi(y.substr(0, l)), curr = -1;
    for (int i = l; i < sz(y); i += l, prev = curr) {
        if (y[i] == '0') return false;
        if (i+l > sz(y)) return false;
        curr = stoi(y.substr(i, l));
        if (prev + 1 == curr) continue;
        if (i+l+1 > sz(y)) return false;
        curr = stoi(y.substr(i, l+1));
        if (prev + 1 == curr) {
            l++;
            continue;
        } else return false;
    }
    return true;
}

void solve() {
    string year;
    cin >> year;
    int next = stoi(year);
    while (next++) {
        string y = to_string(next);
        for (int l = sz(y)>>1; l > 0; l--) {
            if (is_roaring(y, l)) {
                cout << next << endl;
                return;
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

• 두번째 접근법: Y의 범위가 10^18 이기 때문에 위의 방법대로 하면 시간 초과가 발생한다. 풀이 아이디어는 모든 roaring year의 집합에서 시작 번호를 이분법(bisection method)으로 찾는 것이다. 시작번호만 알면 뒤에 연속되는 자릿수에 따라 roaring year를 알 수 있기 때문에 시작번호만 이분법으로 탐색한다. 개인적으로 다른 사람 풀이를 봤을 때는 매개변수 탐색이라고 보는 것이 맞는 듯하다. 알고리즘은 다음과 같다.
  • 최초 연속되는 숫자의 개수를 2부터 시작하고 한 자릿수일 때 10^18까지 검사하기 위해 최대 18개까지 이분법을 수행한다.
  • 시작 번호는 10^18의 절반인 10^9가 최댓값이 되고 최솟값은 1이 된다. 이분 탐색으로 시작번호를 찾을 때는 시작번호로 만들어진 숫자가 입력 Y보다 크면 시작번호를 줄이고, Y보다 작거나 같으면 시작번호를 늘린다. 모든 집합의 원소에서 Y 다음으로 올 수 있는 가장 작은 값을 찾는 것이기 때문에 입력 Y보다 크면 시작번호를 줄여야 된다.
  • 매 연속되는 숫자 개수(2~18)마다 이분법을 수행해서 찾은 roaring year 중 최솟값을 반환하면 된다.
  • 시간 복잡도: O(log2(1e9) * 18 * 18) = 29.897352853986263 * 18 * 18 < 9,720

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define sz(c) (int)(c).size()
using namespace std;
typedef long long ll;

const ll INF = 2e18;
ll Y;

ll make_roaring_year(ll nbr, int num_consecutives) {
    auto digits = [&](ll v) {
        ll x = v, y = 1;
        while (x) x /= 10, y *= 10;
        return y;
    };

    ll ret = 0;
    for (int i = 0; i < num_consecutives; i++, nbr++) {
        ll d = digits(nbr);
        // 이미 범위를 넘는 경우 roaring year은 없는 것이므로 INF를 반환한다.
        if (ret > INF/d) return INF;
        ret = ret * d + nbr;
        ret = min(ret, INF);
    }
    return ret;
}

ll search(int num_consecutives) {
    ll lo = 0, hi = 1e9;
    while (lo + 1 < hi) {
        ll mid = (lo + hi) >> 1;
        if (make_roaring_year(mid, num_consecutives) > Y) hi = mid;
        else lo = mid;
    }
    ll ret = make_roaring_year(hi, num_consecutives);
    return ret;
}

void solve() {
    cin >> Y;
    ll ans = INF;
    for (int n = 2; n <= 18; n++)
        ans = min(ans, search(n));
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

 

Double or NOTing