2021 SCPC Round 2 후기

후기

1번은 보자마자 풀진 못했지만 30분 내에 해결했다. 2번은 처음 볼 때 문제를 약간 잘못 봐서 잘못된 풀이를 생각해냈고 약간 뿌듯했다. 하지만 코드를 짜면서 뭔가 잘못됨을 느꼈고 결국 못 풀었다. 3번은 아예 아무것도 생각나지 않았고 전탐색으로 부분점수라도 긁으려 했지만 그것도 시간 초과가 났다.

1. 원 안의 점

문제 설명

원의 반지름이 주어지고 원의 내부에 있는 격자점을 구하는 문제다.

풀이

r = 3인 원

위의 그림과 같이 원 내부 격자점의 개수 = 초록점 + 4 * (검은 점 한 세트)이다.
이때 초록점은 (r - 1) * 4 + 1로 구할 수 있다.
그렇다면 검은 점의 개수만 빠르게 구하면 되는데 이때는 이분 탐색 이용했다.
원 내부의 점 좌표를 (x, y) 라 할 때 x^2 + y ^2 < r^2인 성질을 이용하여 x좌표를 고정시켜두고 y의 최댓값을 이분 탐색으로 구했다.

코드

#include <iostream>

using namespace std;
using ll = long long;

void solve() {
    ll R; cin >> R;
    ll ans = (R - 1) * 4 + 1;
    ll pcnt = 0;
    for (ll i = 1; i < R; i++) {
        ll l = 1, r = R;
        while (l + 1 < r) {
            ll mid = (l + r) / 2;
            if (i * i + mid * mid < R * R) l = mid;
            else r = mid;
        }
        pcnt += l;
    }
    ans += pcnt * 4;
    cout << ans << endl;
}

int main() {
    ll t; cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << endl;
        solve();
    }
    return 0;
}

2. 직8각형

문제 설명

8개의 점의 좌표와 k가 주어졌을 때 위의 그림과 같은 모양을 만들기 위해 점을 움직이는 최솟값을 구하는 문제이다.
문제를 보고 떠올린 것은 비트 마스크를 하며 dp를 돌리는 것이다. dp[사용된 모서리 점 상태][사용한 움직이는 점 상태]로 정의하고 dp를 돌릴 생각을 했다. 하지만 그렇게 풀이하기 위해서 직8각형의 위치가 고정되야하지만 빠른 시간 내에 직8각형을 고정시키는 방법을 찾지 못했다. 대회가 끝나고 풀이를 봤는데 풀이가 완전히 틀렸다.

나중에 내 시행착오를 볼 수 있도록 코드를 첨부하겠다.

틀린 코드

int dpf(int ver, int dot) {
    int &ret = dp[ver][dot];
    if (ret != 1e9) return ret;
    if (ver + 1 == 1 << 8 && dot + 1 == 1 << 8) return 0;

    for (int i = 0; i < 8; i++) if (!(ver & (1 << i))) {
        for (int j = 0; j < 8; j++) if (!(dot & (1 << j))) {
            ret = min(ret, dpf(ver | (1 << i), dot | (1 << j)) + dist(vertex[i], arr[j]));
        }
    }
    
    return ret;
}