Atcoder Beginner Contest 190 풀이

Rated User 중에 올솔한 사람이 500명이나 되는 라운드였다.

아마 E, F가 전형적인 문제여서 그런 듯 하다.

라운드 링크

A - Very Very Primitive Game

일일이 시뮬레이션을 돌려도 되고 조건문 써서 수식으로 풀어도 된다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int a, b, c; cin >> a >> b >> c;
    if(c == 0) {
        if(a > b) cout << "Takahashi" << '\n';
        else cout << "Aoki" << '\n';
    }
    else {
        if(b > a) cout << "Aoki" << '\n';
        else cout << "Takahashi" << '\n';
    }
    return 0;
}

B - Magic 3

$X_i \lt S$, $Y_i \gt D$를 만족하는 $(X_i, Y_i)$가 하나라도 있다면 Yes를 출력하자.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N, S, D; 
    cin >> N >> S >> D;
    for(int i=0;i<N;++i) {
        int x, y; cin >> x >> y;
        if(x >= S || y <= D) continue;
        cout << "Yes" << '\n';
        return 0;
    }
    cout << "No" << '\n';
    return 0;
}

C - Bowls and Dishses

접시에 공이 놓여있는 가짓수가 $2^K$이기 때문에 전부 시도해봐도 시간 안에 들어온다. 시간복잡도는 $O(M2^K)$

#include<bits/stdc++.h>
using namespace std;
int N, M, K;
vector<pair<int,int>> act, cond;
int cnt[101];
bool good[100];
int ans;
void dfs(int idx) {
    if(idx == K) {
        int t = 0;
        for(int i=0;i<M;++i) {
            t += cnt[cond[i].first] > 0 && cnt[cond[i].second] > 0;
        }
        ans = max(ans, t);
        return ;
    }
    cnt[act[idx].first]++;
    dfs(idx+1);
    cnt[act[idx].first]--;
    cnt[act[idx].second]++;
    dfs(idx+1);
    cnt[act[idx].second]--;
}

int main() {
    cin >> N >> M;
    for(int i=0;i<M;++i) {
        int u, v; cin >> u >> v;
        cond.emplace_back(u, v);
    }
    cin >> K;
    for(int i=0;i<K;++i) {
        int u, v; cin >> u >> v;
        act.emplace_back(u, v);
    }
    dfs(0);
    cout << ans << '\n';
    return 0;
}

D - Staircase Sequences

공차가 1인 등차수열 중에서 총 수열의 합이 $N$인 등차수열의 갯수를 구해야 한다. 일단 공차가 1인 등차수열이 A부터 시작해서 B에서 끝난다고 생각하자. 그러면 길이는 (B-A+1)이 되고 그 합은 $\frac{(A+B)(B-A+1)}{2}$이다.

이 값이 $N$이어야 하며, 다시 써보면 $(A+B)(B-A+1)=2N$이다.

$A+B = x, B-A+1 = y$로 놓으면 $A=\frac{x-y+1}{2}$, $B=\frac{x+y-1}{2}$다.

이 때, $2N$이 짝수이므로 $x, y$ 둘 중 하나는 짝수여야 한다. 그리고 $A,B$는 정수여야하므로 $x, y$의 홀짝이 달라야만 한다.

$xy=2N$이 되면서 $x, y$의 홀짝이 다른 경우의 수를 세주면 된다. $2N$의 약수를 전부 찾는데에 $O(\sqrt{N})$이 걸린다.

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

int main() {
    cin >> N;
    N <<= 1;
    int ans = 0;
    for(ll i=1;i*i<=N;++i) {
        if(N%i == 0) {
            ll x = i;
            ll y = N/i;
            if((x&1) ^ (y&1)) ans += 2;
        }
    }
    cout << ans << '\n';
}

E - Magical Ornament

$C_i$를 전부 지나는 최소 길이의 경로를 찾아야 한다. 만약 그런 경로가 있다면 $C_i$에서 출발해서 $C_j$에서 끝나는 형태의 경로가 될 것이다.

따라서, 모든 $C_i$, $C_j$ 사이의 최단경로를 구해준 다음에 $C_i$에서 출발해서 $C_j$로 끝나는 경로 중에서 모든 $C_k$를 지나는 최소 길이 경로를 찾아주면 된다.

일단 $C_i, C_j$ 사이의 최단 경로를 구하는 것은 BFS $K$번 하면 된다. 그리고 나서는 TSP 문제를 DP로 풀듯이 $dp(i, subset)$을 subset의 점들을 전부 지나면서 $C_i$에서 끝나는 최소 길이 경로의 길이로 놓으면 문제가 해결 된다.

시간복잡도는 $O(K^2 2^K + K(N+M))$

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N, M, K;
vector<vector<int>> G(200005);
int dp[17][1<<17];
vector<int> bfs(int src) {
    vector<int> dist(N+1, INF);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int nxt : G[cur]) {
            if(dist[nxt] != INF) continue;
            dist[nxt] = dist[cur] + 1;
            q.push(nxt);
        }
    }
    return dist;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0;i<M;++i) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin >> K;
    vector<int> c(K);
    for(int i=0;i<K;++i) cin >> c[i];
    vector<vector<int>> dist;
    for(int i=0;i<K;++i) dist.push_back(bfs(c[i]));
    for(int i=0;i<K;++i) for(int j=0;j<(1<<K);++j) dp[i][j] = INF;
    for(int i=0;i<K;++i) dp[i][1<<i] = 0;
    for(int i=1;i<(1<<K);++i) {
        for(int j=0;j<K;++j) {
            if(i&(1<<j)) continue;
            int mask = i | (1<<j);
            for(int k=0;k<K;++k) {
                if(i&(1<<k)) dp[j][mask] = min(dp[j][mask], dp[k][i] + dist[k][c[j]]);
            }
        }
    }
    int ans = INF;
    for(int i=0;i<K;++i) ans = min(ans, dp[i][(1<<K)-1]);
    if(ans == INF) ans = -1;
    else ++ans;
    cout << ans << '\n';
    return 0;
}

F - Shift and Inversions

처음 배열에서 inversion의 수를 구하자. 이건 머지소트를 변형하거나 세그트리를 이용하면 $O(NlogN)$에 구할 수 있다. 이 값을 $S$라고 하자.

shift가 한 번 일어나면 배열에서 제일 앞의 원소를 떼서 제일 뒤로 붙여주는 것으로 생각할 수 있다.

제일 앞의 원소가 $x$였다면 이 원소가 제일 끝으로 가면서 없어지는 inversion의 수는 $x$이고 새로 생기는 inversion의 수는 $N-1-x$가 될 것이다.

이를 각각 $S$에서 빼주고 더해주는 것을 진행하면 하나의 shift당 inversion의 수를 $O(1)$에 구할 수 있다. 따라서 총 시간복잡도는 $O(NlogN)$이 된다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
int N;
int a[300001];
int tree[300001];
int rev[300001];
int get(int idx) {
    int ret = 0;
    while(idx) {
        ret += tree[idx];
        idx -= idx & -idx;
    }
    return ret;
}

void update(int idx) {
    while(idx <= N) {
        tree[idx]++;
        idx += idx & -idx;
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=1;i<=N;++i) {
        cin >> a[i];
        ++a[i];
        rev[a[i]] = i;
    }
    ll ans = 0;
    for(int i=1;i<=N;++i) {
        ans += i-1 - get(rev[i]);
        update(rev[i]);
    }
    cout << ans << '\n';
    for(int i=1;i<N;++i) {
        ans -= a[i]-1;
        ans += N-a[i];
        cout << ans << '\n';
    }
    return 0;
}