Facebook Hacker Cup 2020 Qualification Round 후기

알고리즘/대회 후기

Facebook Hacker Cup 2020 Qualification Round 후기

IKnoom 2020. 8. 3. 22:06

올해 해쉬코드, 코드잼에 이어서 해커컵에도 처음으로 참가했다.

토요일부터 3일동안 진행되었고 한 문제 이상 맞으면 예선은 통과다.

A번

각 국가는 인접한 국가로만 이동할 수 있다.
각 국가에서 입국/출국이 가능한지 입력으로 주어진다.

N개의 국가에 대해서 다른 국가로 이동이 가능한지 N×N 행렬로 출력하면 된다.

행렬을 채울 때 일단 모두 N으로 초기화하고 각 국가마다

자신의 국가는 Y로 채운다.
양옆으로 for문을 돌면서 현재 국가에서 출국이 가능하고 다음 국가에서 입국이 가능한지 체크한다.
가능하면 계속 Y로 채우고 불가능하면 break한다.

import sys
f_name = "travel_restrictions"
sys.stdin = open(f_name + "_input.txt", 'r')
sys.stdout = open(f_name + "_output.txt", 'w')

def solution():
    N = int(input())
    incoming = input().rstrip()
    outcoming = input().rstrip()
    answer = [['N'] * N for _ in range(N)]
    for i in range(N):
        answer[i][i] = 'Y'
        for j in range(i - 1, -1, -1):
            if outcoming[j + 1] == 'N': break
            if incoming[j] == 'N': break
            answer[i][j] = 'Y'
        for j in range(i + 1, N):
            if outcoming[j - 1] == 'N': break
            if incoming[j] == 'N': break
            answer[i][j] = 'Y'
    return answer

if __name__ == "__main__":
    T = int(input())
    for case in range(1, T + 1):
        M = solution()
        print(f"Case #{case}:")
        for row in M:
            print(''.join(row))

처음에 validation_input.txt를 받고 validation_output.txt을 제출하면

실제 input.txt를 주는데 "6분 내로" output.txt + 소스코드를 제출해야한다.

이때 해커컵을 처음 참여해서 몰랐는데 나중에 제출해도 되는건가?하고 있다가

6분이 지나서 Timer Expired를 받았다. 찾아보니까 이러면 다시 제출을 할 수 없다..

B번

지문이 길지만 문제는 간단하다.

순서, 위치에 상관없이 {A, A, B}를 {A}로 바꾸거나 {A, B, B}를 {B}로 바꿀 수 있고 마지막에 하나만 남기면 된다.

위 과정은 서로 다른 색깔 2개를 공집합으로 대체하는 과정과 같기 때문에

두 색깔 갯수의 차이가 1개가 되는지 확인하면 끝이다.

import sys
f_name = "alchemy"
sys.stdin = open(f_name + "_input.txt", 'r')
sys.stdout = open(f_name + "_output.txt", 'w')

def solution():
    N = int(input())
    C = input().rstrip()
    cnt_B = cnt_A = 0
    for i in range(N):
        if C[i] == 'A': cnt_A += 1
        if C[i] == 'B': cnt_B += 1
    if abs(cnt_A - cnt_B) == 1:
        return 'Y'
    else:
        return 'N'

if __name__ == "__main__":
    T = int(input())
    for case in range(1, T + 1):
        y_n = solution()
        print(f"Case #{case}: {y_n}")

C번

나무가 일자로 세워져 있는데 나무를 쓰러트려서 가장 긴 연속된 interval를 구하는 문제다.

두 나무를 쓰러트렸을 때 두 나무가 서로 겹치지않고 떨어지지도 않으면 연속된 interval이다.

N이 최대 800,000이므로 나무를 쓰러트리는 방향마다 모두 구하면 2^N가지 경우의 수가 있으므로 시간초과다.

이때 dp로 풀면 NlogN만에 풀 수 있다. 현재 위치가 p라고 하면

dp[i] = i에서의 왼쪽 방향으로의 최대 interval
나무를 오른쪽으로 쓰러트렸을 때 : dp[p + h] = max(dp[p + h], dp[p] + h)
나무를 왼쪽으로 쓰러트렸을 때 : dp[p] = max(dp[p], dp[p - h] + h)

p의 범위가 상당히 크므로 std::map을 사용해야한다.

#include <bits/stdc++.h>

using namespace std;
using pi = pair<long long, long long>;

long long solution() {
    int N; cin >> N;
    vector<pi> logs;
    for(int i = 0; i < N; i++) {
        long long p, h;
        cin >> p >> h;
        logs.emplace_back(p, h);
    }
    sort(logs.begin(), logs.end());

    map<long long, long long> dict;
    for(auto pi : logs) {
        long long p = pi.first, h = pi.second;

        auto right = dict.find(p);
        if(right == dict.end()){
            dict[p + h] = max(dict[p + h], h);
        } else {
            dict[p + h] = max(dict[p + h], dict[p] + h);
        }

        auto left = dict.find(p - h);
        if(left == dict.end()){
            dict[p] = max(dict[p], h);
        } else {
            dict[p] = max(dict[p], dict[p - h] + h);
        }
    }

    long long ans = 0LL;
    for(auto pi : dict) {
        ans = max(ans, pi.second);
    }

    return ans;
}

int main() {
    freopen("timber_input.txt", "r", stdin);
    freopen("timber_output.txt", "w", stdout);

    int T;
    cin >> T;
    for(int i = 1; i <= T; i++) {
        long long ans;
        ans = solution();
        cout << "Case #" << i << ": " << ans << '\n';
    }

    fclose(stdin);
    fclose(stdout);
}

한 문제만 맞으면 되기 때문에 C까지 풀었고 D1, D2는 풀지 않았다.

나중에 채점결과를 보니 B, C 둘 다 AC로 예선은 통과했다.