티스토리 뷰

Round #578에서 레이팅이 18 떨어져서 이번에 Div. 2를 쳤다. 놀랍게도 레이팅이 정확히 18 올라서 원래대로 돌아왔다.

사소한 오류 때문에 D를 8번 내서 맞았다는 것이 너무나도 뼈아팠다.

대회 시작 후 1시간 만에 AC 받을 문제를 2시간 가까이 붙들고 있어서 E번을 볼 시간이 없었다.

해결한 문제에 대한 풀이를 작성하도록 하겠다. 링크: https://codeforces.com/contest/1206

Div 2A Choose Two Numbers

총 $O(NM)$개의 $(a_i, b_j)$ 쌍을 직접 확인하면서 $a_i + b_j \in A \cup B$인지 체크해주면 된다. 이대로 구현하면 $O(NM(N+M))$이고, $A$와 $B$의 원소들의 크기가 작음을 이용하면 $O(NM)$에도 해결할 수 있다. 더 빠른 방법은 잘 모르겠다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int N, M;
int A[201], B[201];
int S[505];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    cin >> M;
    for (int j=0; j<M; j++) cin >> B[j];
    for (int i=0; i<N; i++) S[A[i]] = 1;
    for (int i=0; i<M; i++) S[B[i]] = 1;
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            if (S[A[i]+B[j]] == 0){
                cout << A[i] << ' ' << B[j] <<endl;
                return 0;
            }
        }
    }
}

Div 2B Make Product Equal One

일단, 모든 수를 $-1$과 $1$ 중 가까운 것으로 만든다. (0제외) 그 이후에는 $-1$의 갯수와 $0$이 있는지의 여부를 따져주면 된다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int N;
int A[100005];
int nzr;
 
lld ans;
int sgn = 1;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> A[i];
        if (A[i] == 0){
            nzr++;
            continue;
        }
        if (A[i] > 0){
            ans += A[i]-1;
            continue;
        }
        ans += -1-(A[i]);
        sgn *= -1;
        continue;
    }
    if (sgn == 1){
        cout << ans+nzr << endl;
        return 0;
    }
    if (nzr > 0){
        cout << ans+nzr << endl;
        return 0;
    }
    cout << ans+2 << endl;
}

Div 1A/Div 2C Almost Equal

예제 입력에 주어진 $n=3$인 경우에 대한 답이 너무 큰 힌트이다. $n$이 짝수이면 안됨은 쉽게 확인할 수 있고, $n=3$인 경우에 대한 답을 쉽게 일반화할 수 있기까지 하다!

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int N;
 
int A[200005];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    if (N%2 == 0){
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    A[0] = 1, A[N]=2;
    int idx = N;
    int num = 2;
    while (num <= N){
        idx++;
        idx %= (2*N);
        A[idx] = 2*num-1;
        idx += N;
        idx %= (2*N);
        A[idx] = 2*num;
        num++;
    }
    for (int i=0; i<2*N; i++) cout << A[i] << ' ';
    cout << endl;
}

Div 1B/Div 2D Shortest Cycle

일단, $a_i$ 중 0인 것들은 제거해도 문제의 답에 영향을 미치지 않는다. 이들을 모두 제거하고 생각하자. (참고로 나는 이 전처리를 했다고 생각했지만, 알고보니 안했어서 7번의 부가적인 제출이 있었다.)

먼저, cycle의 최소 길이는 3이다. 길이가 3인 cycle이 있을 충분조건중 하나를 생각해보면, 어떤 $p$와 서로 다른 $i, j, k$가 존재해 $2^p \& a_i > 0$, $2^p \& a_j > 0$, $2^p \& a_k > 0$을 만족시키는 상황이다. 이러한 조건을 만족하는 경우가 있는지 확인하는 것은 $O(64 \cdot N)$에 가능하다.

위 조건을 만족하지 않는다고 하자. 그러면, 각각의 $p$에 대해 $2^p \& a_i > 0$을 만족하는 $i$는 최대 2개 존재한다. 입력이 64비트 정수 변수 범위로 주어지므로, $p$의 값으로 가능한건 대략 64개 정도이고, 따라서 $N \le 128$이 된다. ($\because$ 전처리를 통해 $a_i = 0$인 것들은 이미 제거함)

이제, $O(N^3)$ 정도의 시간에 shortest cycle을 찾아주면 된다. 이는 각각의 $i = 1, 2, \cdots, N$에 대해 정점 $i$에서 시작하는 BFS를 돌려주면 된다. 각 단계마다 걸리는 시간은 $O(N^2)$이고, 총 $O(N^3)$의 시간에 문제를 해결할 수 있다.

아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int N;
lld p[61];
lld A[100005];
 
const int INF = 10000000;
 
int v;
 
vector<int> adj[1000];
queue<int> que;
int dist[1000];
bool vis[1000];
int par[1000];
 
int solve(){
    int ans = INF;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            dist[j] = INF+5;
            vis[j] = 0;
            par[j] = -1;
        }
        dist[i] = 0;
        que.push(i);
        vis[i] = 1;
        while (!que.empty()){
            int u = que.front();
            que.pop();
            for (int w : adj[u]){
                if (w == par[u]) continue;
                if (!vis[w]){
                    vis[w] = 1;
                    par[w] = u;
                    dist[w] = dist[u]+1;
                    que.push(w);
                }
                else {
                    ans = min(ans, dist[u]+dist[w]+1);
                }
            }
        }
    }
    return ans;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    p[0] = 1LL;
    for (int i=1; i<=60; i++){
        p[i] = p[i-1] * 2LL;
    }
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    for (int j=0; j<61; j++){
        for (int i=0; i<N; i++){
            if (A[i] & p[j]) v++;
        }
        if (v >= 3){
            cout << 3 << endl;
            return 0;
        }
        v = 0;
    }
    sort(A, A+N);
    reverse(A, A+N);
    for (int i=0; i<N; i++){
        if (A[i] == 0){
            N = i;
            break;
        }
    }
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            if (i == j) continue;
            if (A[i] & A[j]){
                adj[i].push_back(j);
            }
        }
    }
    int ans = solve();
    if (ans == INF){
        cout << -1 << endl;
    }
    else cout << ans << endl;
}

 

P.S. PS 잘하고 싶어요

'정보과학 > Codeforces' 카테고리의 다른 글

Educational Codeforces Round 71  (1) 2019.08.23
Codeforces Round #580  (1) 2019.08.19
Codeforces Round #578  (0) 2019.08.12
Codeforces Round #492  (0) 2019.08.06
Codeforces Round #576  (0) 2019.08.04
Codeforces Round 526 (Div 2) 후기  (0) 2018.12.11
댓글
댓글쓰기 폼
공지사항
Total
20,231
Today
24
Yesterday
25