티스토리 뷰

이 라운드의 B번 문제가 올해 IOI에 제한만 높여서 나왔다고 해서 Div 1에 virtual participate 해봤습니다. B와 C를 해결했고, A는 풀지 못했으며, F는 트리 DP 같아 보였지만, 식을 세우지 못했습니다. https://codeforces.com/contest/995

Div 1B/Div 2D Suit and Tie

앞에 있는 수 부터 차례로 그리디하게 매칭해주면 됩니다. 시간 복잡도는 $O(N^2)$이 됩니다.

이 방법의 정당성은 쉽게 증명할 수 있는데, 불필요한 swap 연산이 포함되어 있지 않음을 보이면 됩니다.

적당한 자료구조를 사용하면 $O(N \log N)$으로 시간 복잡도를 낮출 수 있습니다.

 

아래는 제 C++ 구현입니다.

 

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

int N;
int A[200];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    int M = 2*N;
    for (int i=0; i<M; i++) cin >> A[i];
    int ans = 0;
    for (int i=0; i<M; i++){
        if (A[i] == 0) continue;
        for (int j=i+1; j<M; j++){
            if (A[j]) ans++;
            if (A[j] == A[i]){
                ans--;
                A[j] = 0; A[i] = 0;
                break;
            }
        }
    }
    cout << ans << endl;
}

 

Div 1C/2E Leaving The Bar

벡터 $v_1, v_2, \cdots, v_N$이 주어지는데, 각각의 $i$에 대해 $|v_i| \le 10^6$ 입니다. 이 때, $|\sum c_i v_i| \le 1.5 \times 10^6$이 되도록 하는 $c_i \in \{ \pm 1 \}$를 찾는 문제입니다. ($N \le 10^5$)

 

먼저, $N \le 2$일 때는 쉽습니다. 그 외의 경우에는 다음의 정리의 증명을 구현하면 $c_i$를 $O(N^2)$ 시간에 찾을 수 있습니다.

 

Theorem. $N \ge 3$ 일 때, 문제의 조건을 만족하는 $c_i$를 찾을 수 있다.

 

proof sketch) 재귀적으로 문제를 해결합시다. $\pm v_i$들을 모두 좌표평면에 표시합시다. 그러면 어떤 두 벡터의 사잇각은 $\pi/3$ 이하가 됩니다. 이 두 벡터를 택한 후, 하나에서 다른 하나를 빼서 새로운 벡터를 만듭시다. 새로운 벡터의 크기는 여전히 $10^6$ 이하입니다. 이제 앞에서 택한 두 벡터를 새로운 벡터로 바꾸면 문제의 조건을 만족하는 $N-1$개의 벡터가 됩니다. 이 과정을 계속 반복하면 됩니다.

 

그러나 이 풀이를 $O(N \log N)$으로 떨어뜨리는 방법을 떠올리지 못해서 랜덤과 그리디로 AC를 받았습니다.

 

아래는 제 C++ 구현입니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int N;
lld X[100000], Y[100000];
int ans[100000];
int A[100000];
 
inline lld sq(lld x){
    return x*x;
}
inline lld sz(lld x, lld y){
    return sq(x)+sq(y);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(42);
    cin >> N;
    for (int i=0; i<N; i++) A[i] = i;
    for (int i=0; i<N; i++) cin >> X[i] >> Y[i];
    random_shuffle(A, A+N);
    reverse(A, A+N);
    random_shuffle(A, A+N);
    lld SX = X[A[0]], SY = Y[A[0]];
    ans[A[0]] = 1;
    for (int j=1; j<N; j++){
        int i = A[j];
        if (sz(SX+X[i], SY+Y[i]) < sz(SX-X[i], SY-Y[i])){
            SX += X[i], SY += Y[i];
            ans[i] = 1;
        }
        else{
            SX -= X[i], SY -= Y[i];
            ans[i] = -1;
        }
    }
    for (int i=0; i<N; i++) cout << ans[i] << ' ';
    cout << endl;
}

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

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
Educational Codeforces Round 55 후기  (0) 2018.12.01
댓글
댓글쓰기 폼
공지사항
Total
19,595
Today
1
Yesterday
100