coci 2012/2013

#Contest 1

2. F7

 

각 플레이어를 점수 순으로 정렬 시켜 놓고 이분 탐색으로 해결하면 된다. 만약 index=h 인 사람이 우승 가능성이 있다면 그보다 점수가 높은 사람은 모두 우승가능성이 있기 때문이다.

 

4. boj 2792

이 문제 또한 마찬가지로 이분 탐색으로 해결할 수 있다.

질투심의 범위 $l$~$h$

질투심이 $mid=(l+h)/2$ 일 때 최대한 적은 사람들에게 나눠주려고 했을 때 얼마나 적은 사람에게 나눠줄 수 있는지 계산하자.

for(int i=0;i<M;i++){
	num+=(arr[i]+mid-1)/mid;
}

 

그럼에도 num이 N(사람수) 보다도 크면 질투심이 mid인 경우는 불가능한 경우이고 더 큰 질투심이 답이라는 뜻이다.

따라서 l=mid로 바꿔주면 된다. 아닌 경우에는 h=mid

 

5. SNAGA (BOJ 2793)

 

열심히 규칙을 찾았다. 

CASE 1. n이 홀수

 

n->2 이므로 strength(n)=2

 

CASE 2. n이 짝수

짝수의 경우는 두 가지 경우 중 하나이다.

(1) n -> $2^{i}$(2의 거듭제곱)->3->2

or

(2) n->(홀수)->2

언제 (1)의 경우이고 언제 (2)의 경우가 나오는지만 확인하면 된다.

 

proof.

만약 n->$2^{i}\times(홀수m)$이 가능하다면 n이 $2^{i}\times m$로 처음으로 안 나눠지는 것이고 그 뜻은 1 부터 $2^{i}\times m$사이의 모든 수로 나눠떨어진다는 뜻이다. 따라서 n이 $2^i$으로도 나눠 떨어질 것이고 m으로도 나눠떨어지므로 모순이다.

즉 (1)과 (2)의 경우밖에 없다.

 

(1)이 나오는 경우

lcm(i) = 1,2,...,(2^i-1) 의 숫자의 최소 공배수

로 정의를 할때

x= lcm(2)+2*lcm(2)*t (t는 음이 아닌 정수) 꼴의 수는 항상 2^2=4로 변한다.

마찬가지로

x=lcm(3)+2*lcm(3)*t 꼴의 수는 항상 2^3=8로 변한다.

...

x=lcm(5)+2*lcm(5)*t 꼴의 수는 2^5=32로 변한다.

주의 할 것은 lcm(5)=72201776446800 로 문제 조건을 안 벗어난다.

 

그외의 경우는 (2)이다.

각 경우를 카운트해서 계산하면 된다.

 

#Contest 2

4.  POPUST( BOJ 2786)

 

먼저 vector에 a,b의 값 정보와 순서정보를 pair로 저장해놓고 각각의 vector를 정렬해놓자.

k개의 음식의 주문 시 최소 금액은 둘 중 하나이다.

(1) 가장 저렴한 k-1개의 b와 그것들과 안 겹치는 순서 중 가장 저렴한 a

(2) 가장 저렴한 k개의 b와 그 순서에 해당하는 a-b 중 최솟값의 합

 

먼저 구현이 쉬운 (2)부터 보자

하나씩 b가 추가될 때마다 그 전까지의 a-b의 최솟값과 새로 추가된 a-b를 비교해서 더 작은 것을 취해주면 된다.

 

(1)의 구현은 다음과 같다.

가장 처음에는 a중 가장 저렴한 것을 선택하고 순서 정보를 저장하고 있는다.

저렴한 순서로 b를 추가할 때마다 만약 a의 순서정보와 안 겹친다면 그대로 합을 계산한다. 하지만 만약 겹친다면 정렬된 a상에서 더 큰 값을 하나씩 확인하면서 만약 k-1개의 b의 순서정보에 포함이 안 되어있으면 그 a를 선택하자.

포함이 되어있나 안되어있나를 빠르게 확인하기 위해서 b를 추가할때마다 set<int>에 추가되는 b의 순서 정보를 넣어두면 된다.

 

아래 코드에서 min1 계산이 (1)의 구현 min2 계산이 (2)의 구현에 해당된다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<utility>
#include<string>
#include<string.h>
 
using namespace std;
 
typedef pair<long long,int>  P;
int n;
vector<P> b;
vector<P> a;
vector<P> ab;
long long bsum[500000];
//min1의 a선택 위치 저장
int ch1=0;
set<int> s;
//a_i-b_i의 최솟값 위치 저장
int ch2;
 
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        long long x,y;
        scanf("%lld %lld",&x,&y);
        a.push_back(P(x,i));
        b.push_back(P(y,i));
        ab.push_back(P(x-y,i));
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    bsum[0]=b[0].first;
    for(int i=1;i<n;i++){
        bsum[i]=bsum[i-1]+b[i].first;
    }
    //k번째 줄
    cout<<a[ch1].first<<'\n';
    ch2=b[0].second;
    for(int k=2;k<=n;k++){
        //b_0~b_k-2와 나머지 중에 a 
        long long min1;
        //덮이면
        s.insert(b[k-2].second);
        if(b[k-2].second==a[ch1].second){
            while(s.count(a[ch1].second)){
                ch1++;
            }
        }
        min1=bsum[k-2]+a[ch1].first;
        //b_0~b_k-1와 그 사이에 a_i-b_i
        long long min2;
        int p=b[k-1].second;
        if(ab[ch2].first>ab[p].first) ch2=p;
        min2=bsum[k-1]+ab[ch2].first;
        printf("%lld\n",min(min1,min2));
    }
    return 0;
}

 

5. INFORMACIJE (BOJ 2787)

 

풀이를 보고 이분 매칭임을 알게 되었다. 처음 구현하는 거라 이분 매칭을 공부할 수 있었다.

집합 A에는 숫자를 집합 B에는 위치를 만들어 놓자. 둘 다 1~n

이 떄 숫자 i가 위치 j로 들어 갈 수 있다면 선을 연결할 것이다.

선은 이렇게 연결하자.

(1) 1 x y v

(v+1) ~n은 x~y 위치에 있을 수 없다. 선을 지우자.

v는 x~y 외의 위치에는 있을 수 없다. 선을 지우자.

 

(2) 2 x y v

1 ~ (v-1)은 x~y 위치에 있을 수 없다. 선을 지우자.

v는 x~y외의 위치에는 있을 수 없다. 선을 지우자.

 

이렇게 연결 정보가 정리가 되면 이분 매칭을 구현하면 된다.

구현 할 때 모두 연결 되는 경우가 있으면 출력하고 그런 경우가 없으면 -1출력

 

#Contest 3

4. boj 3079

이분탐색으로 풀 수 있는데 답의 최댓값이 10^18까지 나올 수 있음에 주의하자

 

#Contest 4

4. RAZLIKA (BOJ 3988)

먼저 입력된 수열을 정렬하자.(수열 A)

이때 숫자를 하나씩 지우는데 M+m이 가능한 작으려면 만약 A의 맨 왼쪽이나 맨 오른쪽에서 지워야한다.

 

만약 A의 양끝이 아닌 가운데 어느 한 수를 지운다고 생각하자. M은 그대로이고, m은 감소하지는 않는다.

 

즉, 맨 왼쪽에서 x개의 수를 지우고 맨 오른쪽에서 K-x개의 수를 지워야한다.

세그먼트 트리를 이용해서 윗 문장과 같이 K개의 숫자를 지웠을 때 m의 값을 O(logN) 으로 찾을 수 있기 때문에

x=0~K 까지 탐색을 하더라도 시간복잡도는 O(NlogN)이다.

 

5. DLAKAVAC (BOJ 3989)

처음 독감에 걸린 사람 번호 집합을 D라 하자.

둘째 날에 독감에 걸린 사람 번호 집합은 D*D이다.(*는 각 집합에 속한 원소끼리 모두 서로서로 곱하는 기호)

셋째 날에 독감에 걸린 사람 번호 집합은 D*D*D

...

K번째 날에 독감에 걸린 사람 번호 집합은 D^K

K승 연산은 분할 정복으로 O(logK)시간복잡도로 가능하다.

 

#Contest 5

4. HIPERCIJEVI (BOJ 5214)

 

bfs문제이다. 매우 오래 고민했고 재밌는 문제였다.

핵심은 역도 정점으로 두고 하이퍼튜브도 정점으로 둬야 한다.

1~n 정점을 역으로 두고

(n+1)~(n+m)정점을 하이퍼튜브로 두고

역이 하이퍼튜브에 속해있으면 두 정점간에 연결을 하는 방식이다.

그럼 두 역 사이 이동을 간선 두개를 통해(하이퍼튜브를 타고) 이동하는 듯한 형태로 바꿀 수 있다.

이렇게 연결을 하고 난 후 bfs로 탐색해주면 된다.

 

#Contest 6

3. DOBRI (BOJ 5624)

수열 A[5000]

핵심은 x+y+z=A[i] 를 x+y=A[i]-z 로 바꿔서 푸는 법이다.

set을 활용하는 문제이지만 i번째 수 앞에 있는 수 세개의 합을 모두 저장하다 보면 당연히 시간 초과가 난다.

그래서 i번째 앞에 있는 수 중 두 개의 합을 저장하는 set<int> s2를 만들어 놓고

j=0 ~ i 까지 돌면서 s2의 원소에 A[i]-A[j]가 존재하는지 확인해주면 시간 내에 풀 수 있다.