Zero One Algorithm Contest 2024 Open Contest

https://www.acmicpc.net/contest/view/1393

 

 

한양대 에리카 오픈 콘테스트 문제 풀이를 정리해보자 한다.

(대회 참여하고 싶은데 주말에 시간이 안 된다,,)

 

A - 당구 좀 치자 제발

 간단한 사칙연산 문제.

입력값 들어오면 계산해주면 된다.

#include <iostream>
#include <string>
#define ll long long
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n; cin >> n;
    ll ans = 0, t = 0;
    
    for(int i = 0;i<n;i++){
        ll k; cin >> k;
        
        t = k == 0 ? t - 1 : t + 1;
        ans += t;
    }
    cout << ans;
    return 0;
}

 

 

B - 정민이의 수열 제조법

 이 문제의 핵심은 두 연산, 한 정수를 제곱하거나, 두 정수를 곱하는 연산을 통해 구할 수 없는 수가 무엇이 있는지 찾는 것이다.

이것을 생각하면 소수들이 이 두 연산으로 구할 수 없음을 알 수 있을 것이다.

소수는 어떤 수의 제곱으로도 나올 수 없고, 두 수의 곱으로도 나올 수 없기 때문이다.

 

이제 n의 값이 5000000이기에 에라토스네의 체로 소수를 구한 뒤, 1~n까지의 구간이라 할 때 누적합을 통해

미리 계산을 해놓고 쿼리가 들어오면 값을 구하면 된다.

 

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

ll ans[5000001];
ll arr[5000001];
int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    

    for(int i = 2;i<=sqrt(n);i++){
        if(arr[i])
            continue;
        for(int j = i *i; j<=n;j+=i){
            arr[j] = 1;
        }
    }
    
    for(int i = 1;i<=n;i++){
        if(!arr[i]){
            ans[i] = 1;
        }
    }
    
    for(int i = 1;i<=n;i++){
        ans[i] += ans[i - 1];
    }
    
    
    
    for(int i = 0;i<m;i++){
        int a,b; cin >> a >> b;
        cout << ans[b] - ans[a - 1] << "\n";
    }
    return 0;
}

 

 

C - 동까뚱뽭 게임

이 게임에서 중요한 부분은 동우가 선공을 가져간다는 것과 동점일 경우 혁준이가 이긴다는 것, 마지막으로 리프 노드로 이동하면 게임이 끝난다는 부분이다.

이것을 보았을 때 혁준이가 이기는 경우는 동점을 만드는 경우 밖에 없다.

그렇기에 리프노드에서 시작하면 혁준이가 이길 것이고, 리프노드의 부모 노드에서 시작하면 동우가 이긴다.

그리고 부모노드의 부모노드는 다시 혁준이 이기는 노드이다.

그렇기에 DFS를 통해서 탐색하면서 리프노드를 체크하면 될 것이다.

 

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

bool typed[100001];
int INF = 1e9;
bool visi[100001];
vector<vector<int>> edge(100001);
bool DFS(int n){
    visi[n] = true;
    bool check = false;
    for(int k : edge[n]){
        if(visi[k])
            continue;
            
        if(!DFS(k)){
            check = true;
        }
    }
    typed[n] = check;
    return check;
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for(int i = 0;i<n - 1;i++){
        int u, v; cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    
    DFS(1);
    
    for(int i = 1;i<=n;i++){
        if(!typed[i])
            cout << "uppercut\n";
        else
            cout << "donggggas\n";
    }
    return 0;
}

 

 

D - 랜덤 넘버 추측하기

각 i번의 인덱스는  $\sum _{p=1}^i{p}_i$로 계산할 수 있다.

그리고 i번이 당첨되면 가중치가 0으로 만들고 다른 값에다가도 업데이트를 해주어야 한다.즉, 구간합 구하기가 되는 것이다.이러한 연산을 딸깍으로 가능케 하는 자료구조가 세그트리이다.

 

#include <iostream>
#include <vector>
#include <cmath>
#define pii pair<int, int>
using namespace std;

long long arr[1000001];
long long* tree;

long long init(int start, int end, int node) {
    if (start == end) return tree[node] = arr[start];
    int mid = (start + end) / 2;

    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

long long sum(int start, int end, int node, int left, int right) {
    if (left > end || right < start) return 0;
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

void update(int start, int end, int node, int idx, long long dif) {
    if (idx > end || idx < start) return;

    tree[node] += dif;
    if (start == end) return;
    int mid = (start + end) / 2;

    update(start, mid, node * 2, idx, dif);
    update(mid + 1, end, node * 2 + 1, idx, dif);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m, k; cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> arr[i];
    int height = ceil(log2(n));
    tree = new long long[1 << (height + 1)];

    init(0, n - 1, 1);

    for (int i = 0; i < m; i++) {
        int k; cin >> k;

        cout << sum(0, n - 1, 1, 0, k -1) << " ";
        long long diff = -arr[k - 1];
        arr[k - 1] = 0;
        update(0, n - 1, 1, k - 1, diff);

    }
}

(딸깍!)

 

 

E - 파괴왕 뚱뽭

텔레포트를 했을 경우와 하지 않았을 경우로 나눠서 다익스트라를 진행해주면 된다.

즉, dist[텔레포트 사용횟수][x좌표][y좌표] 형식으로 진행주면 된다.

그리고 쿼리가 들어오면 dist[t_i][x][y]를 확인하며 p 이하인지 체크해주면 된다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <tuple>
#define pii pair<int, int>
#define ll long long
using namespace std;

ll maps[101][101];
map<pii, pii> mp;
int n, m, t;
ll dist[101][101][101];

int next_x[4] = { 1, -1, 0, 0 };
int next_y[4] = { 0, 0, 1, -1 };

ll INF = 1e18;

void Dekkers() {
    priority_queue<tuple<ll, int, pair<int, int>>, vector<tuple<ll, int, pair<int, int>> >, greater<tuple<ll, int, pair<int, int>> >> pq;

    pq.push({ 0,0,{0, 0} });

    for (int i = 0; i <= t; i++) dist[i][0][0] = 0;

    while (!pq.empty()) {
        tuple<ll, int, pair<int, int>> tp = pq.top();
        auto [d, t1, point] = tp;
        pq.pop();

        for (int i = 0; i < 4; i++) {
            int nextx = point.first + next_x[i];
            int nexty = point.second + next_y[i];


            if (nextx < 0 || nexty < 0 || nextx >= n || nexty >= m)
                continue;
            
            if (dist[t1][nextx][nexty] > maps[nextx][nexty] + d) {
                dist[t1][nextx][nexty] = maps[nextx][nexty] + d;
                pq.push({ dist[t1][nextx][nexty] , t1, {nextx, nexty} });
            }
        }

        if (mp.count(point)) {
            if (t1 >= t)
                continue;
            pii teleport = mp[point];

            if (dist[t1 + 1][teleport.first][teleport.second] > d) {
                dist[t1 + 1][teleport.first][teleport.second] = d;
                pq.push({ d , t1 + 1, teleport });
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int k, q; cin >> n >> m >> k >> t >> q;

    fill_n(&dist[0][0][0], 101 * 101 * 101, INF);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maps[i][j];
        }
    }

    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        x1--; x2--; y1--; y2--;
        mp[{x1, y1}] = { x2, y2 };
    }

    Dekkers();

    for (int i = 0; i < q; i++) {
        int p, x, y; cin >> p >> x >> y;
        x--; y--;
        bool check = false;
        for (int i = 0; i <= t; i++) {
            if (dist[i][x][y] == INF)
                continue;
            if (p >= dist[i][x][y]) {
                cout << 1 << "\n";
                check = true;
                break;
            }
        }

        if (!check)
            cout << 0 << "\n";
    }
}

 

H - GLCCDM

최대공약수가 A이고 최소공배수가 B인 수열을 구하는 문제이다.

즉, 수열의 속한 수는 A의 배수이고, B의 약수여야 한다.

그래야 A와 B가 만족하기 때문이다.

 

그렇기에 수열에서 최솟값을 A, 최댓값을 B로 잡고, 구간 [A, B]의 값 중에  i % A == 0을 만족하고,  B % i를 만족하는 i가 k - 2개로 존재한다면 정답이다.

 

마지막으로 k가 2일 때 A가 B의 약수인지를 확인해주면 된다.

 

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int A, B ,K; cin >> A >> B >> K;
    vector<int> ans;
    for(int i = A + 1;i<= B - 1;i++){
        if(i % A == 0 && B % i == 0){
            ans.push_back(i);
        }
        
        if(ans.size() == K - 2)
            break;
    }
    
    if(K == 2){
        if(B % A == 0){
            cout << A << " " << B;
        }
        else{
            cout << -1;
        }
        return 0;
    }
    
    if(ans.size() < K - 2)
        cout << -1;
    else{
        cout << A << " ";
        for(int t : ans) cout << t << " ";
        cout << B;
    }
    return 0;
}