NYPC 2022 Round 1 후기

1. [연습문제] 레이스 기록 검증

NYPC 2021 예선에 출제된 문제입니다.

 

2. [연습문제] 페인트 칠하기

NYPC 2021 예선에 출제된 문제입니다.

 

3. 인류의 적 모기 퇴치

물풍선을 터뜨릴 곳을 정한 후, 퇴치할 수 있는 모기 수를 계산하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, M;
ll A[55][55];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M;
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; j <= N; j++){
            cin >> A[i][j];
        }
    }
    ll r = 0;
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; j <= N; j++){
            ll s = 0;
            for(ll k = -M; k <= M; k++){
                if(j + k < 1 || j + k > N) continue;
                s += A[i][j + k];
            }
            for(ll k = -M; k <= M; k++){
                if(i + k < 1 || i + k > N) continue;
                s += A[i + k][j];
            }
            s -= A[i][j];
            r = max(r, s);
            s = 0;
            for(ll k = -M; k <= M; k++){
                if(i + k < 1 || i + k > N || j + k < 1 || j + k > N) continue;
                s += A[i + k][j + k];
            }
            for(ll k = -M; k <= M; k++){
                if(i - k < 1 || i - k > N || j + k < 1 || j + k > N) continue;
                s += A[i - k][j + k];
            }
            s -= A[i][j];
            r = max(r, s);
        }
    }
    cout << r;
}

 

 

4. 카트라이더 보드게임

그래프를 만든 후 DP로 얻을 수 있는 루찌의 최댓값을 계산하고 역추적을 하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, X;
ll P[70];
ll D[70][1005];
pair<ll, ll> path[70][1005];
vector<ll> G[75][8];
vector<pair<ll, ll>> T[75];
void add_edge(ll u, ll v){
    G[v][1].push_back(u);
}
void make_graph(){
    for(ll i = 1; i <= 39; i++) add_edge(i, i + 1);
    add_edge(12, 17);
    add_edge(32, 37);
    add_edge(39, 41);
    add_edge(41, 42);
    add_edge(42, 43);
    add_edge(43, 40);
    add_edge(40, 44);
    for(ll i = 44; i <= 50; i++) add_edge(i, i + 1);
    add_edge(49, 56);
    add_edge(49, 52);
    for(ll i = 56; i <= 58; i++) add_edge(i, i + 1);
    for(ll i = 52; i <= 54; i++) add_edge(i, i + 1);
    add_edge(55, 51);
    add_edge(59, 51);
    add_edge(51, 60);
    for(ll i = 60; i <= 63; i++) add_edge(i, i + 1);
    add_edge(64, 1);
    for(ll j = 2; j <= 6; j++){
        for(ll i = 1; i <= 64; i++){
            for(auto u : G[i][1]){
                for(auto v : G[u][j - 1]){
                    G[i][j].push_back(v);
                }
            }
        }
    }
    for(ll i = 1; i <= 64; i++){
        for(ll j = 1; j <= 6; j++){
            for(auto k : G[i][j]){
                T[i].push_back({k, j});
            }
        }
    }
}
void chmax(ll x, ll y, ll a, ll d){
    if(D[x][y] < D[a][y - 1] + P[x]){
        D[x][y] = D[a][y - 1] + P[x];
        path[x][y] = {a, d};
    }
}
void track(ll u, ll d){
    if(d <= 0) return;
    pair<ll, ll> p = path[u][d];
    track(p.first, d - 1);
    cout << "Moved from " << p.first << " to " << u << " (dice = " << p.second << ", lucci = " << P[u] << ")\n";
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    P[8] = P[17] = P[20] = P[31] = P[37] = P[39] = P[44] = P[49] = P[60] = P[63] = 1;
    P[2] = P[6] = P[10] = P[19] = P[23] = P[25] = P[27] = P[43] = 2;
    P[13] = P[33] = P[41] = P[52] = P[53] = P[54] = 3;
    P[55] = P[64] = 5;

    make_graph();
    cin >> N >> X;
    fill(D[0], D[69] + 1005, -1e18);
    D[1][0] = 0;
    for(ll j = 1; j <= N; j++){
        for(ll i = 1; i <= 64; i++){
            for(auto k : T[i]){
                chmax(i, j, k.first, k.second);
            }
        }
    }
    cout << D[X][N] << '\n';
    track(X, N);
}

 

5. 뒤집기

겹치지 않는 두 구간의 합의 최댓값을 구하는 문제입니다. 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[1000005];
ll D[1000005], E[1000005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N;
    for(ll i = 1; i <= N; i++){
        cin >> A[i];
    }
    for(ll i = 1; i <= N; i++){
        D[i] = max(D[i - 1], 0LL) + A[i];
    }
    for(ll i = N; i >= 1; i--){
        E[i] = max(E[i + 1], 0LL) + A[i];
    }
    for(ll i = 2; i <= N; i++){
        D[i] = max(D[i - 1], D[i]);
    }
    for(ll i = N - 1; i >= 1; i--){
        E[i] = max(E[i + 1], E[i]);
    }
    ll r = D[N];
    for(ll i = 1; i <= N; i++){
        r = max(r, D[i] + E[i + 1]);
    }
    cout << r;
}

 

6. 카트 제작

카트바디 $k$, 핸들, 바퀴를 조합했을 때 가능한 모든 성능의 값을 배열 $X_k$, 카트바디, 엔진, 부스터를 조합했을 때 가능한 모든 성능의 값을 배열을 $Y_k$라 하면 모든 $k$에 대해 $X_k + Y_k$중 $S$와 가장 가까운 값을 이분탐색으로 구하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
ll N, M, K;
vector<pair<ll, ll>> A[605];
map<string, ll> Num;
string Inv[605];
ll Bonus[605][605];
vector<tuple<ll, ll, ll, ll>> X[605], Y[605];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N;
    for(ll i = 1; i <= N; i++){
        string T, S; ll v; cin >> T >> S >> v;
        Num[S] = i; Inv[i] = S;
        if(T == "Body") A[1].push_back({i, v});
        if(T == "Handle") A[2].push_back({i, v});
        if(T == "Wheel") A[3].push_back({i, v});
        if(T == "Engine") A[4].push_back({i, v});
        if(T == "Booster") A[5].push_back({i, v});
    }
    cin >> M;
    for(ll i = 1; i <= M; i++){
        string S, T; ll v; cin >> S >> T >> v;
        Bonus[Num[S]][Num[T]] = Bonus[Num[T]][Num[S]] = v;
    }
    for(auto i : A[1]){
        for(auto j : A[2]){
            for(auto k : A[3]){
                X[i.x].push_back(make_tuple(i.y + j.y + k.y + Bonus[i.x][j.x] + Bonus[j.x][k.x] + Bonus[k.x][i.x], i.x, j.x, k.x));
            }
        }
    }
    for(auto i : A[1]){
        for(auto j : A[4]){
            for(auto k : A[5]){
                Y[i.x].push_back(make_tuple(j.y + k.y + Bonus[i.x][j.x] + Bonus[j.x][k.x] + Bonus[k.x][i.x], i.x, j.x, k.x));
            }
        }
    }
    cin >> K;
    ll mn = 1e18, rx = -1, ry = -1, rz = -1;
    for(ll i = 0; i < 605; i++){
        sort(X[i].begin(), X[i].end());
        sort(Y[i].begin(), Y[i].end());
        if(X[i].empty() || Y[i].empty()) continue;
        for(ll j = 0; j < X[i].size(); j++){
            ll v = K - get<0>(X[i][j]);
            ll idx = lower_bound(Y[i].begin(), Y[i].end(), make_tuple(v, -1, -1, -1)) - Y[i].begin();
            if(abs(get<0>(X[i][j]) + get<0>(Y[i][idx]) - K) < mn){
                mn = abs(get<0>(X[i][j]) + get<0>(Y[i][idx]) - K), rx = i, ry = j, rz = idx;
            }
            if(idx >= 1 && abs(get<0>(X[i][j]) + get<0>(Y[i][idx - 1]) - K) < mn){
                mn = abs(get<0>(X[i][j]) + get<0>(Y[i][idx - 1]) - K), rx = i, ry = j, rz = idx - 1;
            }
        }
    }
    cout << Inv[get<1>(X[rx][ry])] << '\n' << Inv[get<2>(X[rx][ry])] << '\n' << Inv[get<3>(X[rx][ry])] << '\n' << Inv[get<2>(Y[rx][rz])] << '\n' << Inv[get<3>(Y[rx][rz])];
}

 

7. 달팽이

이분탐색을 이용하여 $A, B$의 좌표를 구한 후, 정사각형인지 판별하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N;
ll S(ll A){
    if(A <= 0) return 0;
    else if(A % 2 == 0) return (A / 2) * (A / 2 + 1);
    else return (A / 2 + 1) * (A / 2 + 1);
}
pair<ll, ll> f(ll A){
    ll M, B, L, R, add;
    if(A <= 4 * N - 4){
        M = N, B = A, add = 0;
    } else if(N % 2 == 0){
        L = 1, R = N / 2 - 1;
        while(L <= R){
            ll m = (L + R) / 2;
            if(A > 4 * (S(N - 1) - S(2 * m - 3))) R = m - 1;
            else L = m + 1;
        }
        M = 2 * L - 2, B = A - 4 * (S(N - 1) - S(2 * L - 3));
        add = N / 2 - L + 1;
    } else {
        L = 1, R = (N - 1) / 2 - 1;
        while(L <= R){
            ll m = (L + R) / 2;
            if(A > 4 * (S(N - 1) - S(2 * m - 2))) R = m - 1;
            else L = m + 1;
        }
        M = 2 * L - 1, B = A - 4 * (S(N - 1) - S(2 * L - 2));
        add = N / 2 - L + 1;
    }
    pair<ll, ll> P;
    if(B <= M - 1) P = {1, B};
    else if(B <= M * 2 - 2) P = {B - (M - 1), M};
    else if(B <= M * 3 - 3) P = {M, M + 1 - (B - (2 * M - 2))};
    else P = {M + 1 - (B - (3 * M - 3)), 1};
    return {P.first + add, P.second + add};
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    ll T; cin >> T;
    while(T--){
        ll A, B; cin >> N >> A >> B;
        pair<ll, ll> P = f(A), Q = f(B);
        cout << (abs(P.first - Q.first) == abs(P.second - Q.second) ? "YES\n" : "NO\n");
    }
}

 

8. 바텐더

풀이 준비 중

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N;
ll A[100005];
const ll M = 5;

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N;
    for(ll i = 1; i <= N; i++){
        cin >> A[i];
    }
    sort(A + 1, A + N + 1);
    ll r = 1e18;
    for(ll t = 0; t <= 8; t++){
        ll LY = 0, LZ = 0, S = 0;
        for(ll i = 1; i <= N; i++){
            ll d = A[N] - A[i] + t;
            LY += d / 2, LZ += d / 4;
            S += d;
        }
        vector<ll> X;
        for(ll i = S / 2 - M; i <= S / 2 + M; i++){
            X.push_back(i);
        }
        for(ll i = S / 3 - M; i <= S / 3 + M; i++){
            X.push_back(i);
        }
        for(ll i = S / 5 - M; i <= S / 5 + M; i++){
            X.push_back(i);
        }
        for(ll i = S / 7 - M; i <= S / 7 + M; i++){
            X.push_back(i);
        }
        for(ll i = (S - 4 * LZ) / 3 - M; i <= (S - 4 * LZ) / 3 + M; i++){
            X.push_back(i);
        }
        for(ll i = S - 2 * LY - M; i <= S - 2 * LY + M; i++){
            X.push_back(i);
        }
        for(ll i = S - M; i <= S + M; i++){
            X.push_back(i);
        }
        X.push_back(0);
        for(auto a : X){
            for(auto b : X){
                for(auto c : X){
                    if(a < 0 || b < 0 || c < 0 || a + 2 * b + 4 * c != S || b + 2 * c > LY || c > LZ) continue;
                    r = min(r, max({3 * (a - 1) + 1, 3 * (b - 1) + 2, 3 * (c - 1) + 3}));
                }
            }
        }
    }
    cout << r;
}

 

9. MBTI 궁합을 이용한 조 구성

MBTI가 같은 두 학생을 한 조를 이루게 하는 것이 항상 최적임을 증명할 수 있습니다.

이를 반복하면 최대 $2^4 = 16$명의 학생이 남게 되고 비트 DP로 성향 차이 점수의 합의 최솟값을 계산하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll tc, N, A, B, C, D;
string S[505];
vector<string> V;
map<string, ll> mp;
ll dist(string X, string Y){
    ll r = 0;
    if(X[0] != Y[0]) r += A;
    if(X[1] != Y[1]) r += B;
    if(X[2] != Y[2]) r += C;
    if(X[3] != Y[3]) r += D;
    return r;
}
ll dp[1 << 17];
ll f(ll bit){
    if(bit == 0) return 0;
    if(dp[bit] != -1) return dp[bit];
    ll r = 1e18;
    for(ll i = 0; i < V.size(); i++){
        for(ll j = i + 1; j < V.size(); j++){
            if((bit & (1 << i)) && (bit & (1 << j))){
                r = min(r, f(bit - (1 << i) - (1 << j)) + dist(V[i], V[j]));
            }
        }
    }
    return dp[bit] = r;
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> tc;
    while(tc--){
        V.clear(); mp.clear(); fill(dp, dp + (1 << 17), -1);
        cin >> N >> A >> B >> C >> D;
        for(ll i = 1; i <= N; i++){
            cin >> S[i]; mp[S[i]]++;
        }
        for(auto i : mp){
            if(i.second % 2 == 1){
                V.push_back(i.first);
            }
        }
        if(V.empty()){
            cout << "0\n";
        } else { 
            cout << f((1 << V.size()) - 1) << '\n';
        }
    }
}

 

10. 드리프트 주행

풀이 준비 중