KOI 2013 고등부 전체 풀이

BOJ 8983 고등부 1번 사냥꾼 

문제 링크 : https://www.acmicpc.net/problem/8983

문제 태그

스위핑

문제 풀이

N개의 x축에 붙은 지점중 임의의 어떤 지점에 대해서 택시거리가 L이하만큼 떨어져 있는지 판별하는 문제. 당연히 하나를 관찰하면 지점은 다 x축에 있으므로 모든 지점에 대해서 떨어진 y거리는 고정이다. 
가장 중요한 관찰을 하자면 어떤 점에 대해서 가장 x값이 비슷한 지점과 거리가 가장 짧을 것이고 그 지점과 거리가 L보다 크면 당연히 나머지 지점에 대해서도 거리가 L보다 클 것이다. 따라서 그냥 가장 비슷한 x값을 찾는 문제. 
배열에서 가장 비슷한 값을 찾는 것은 그냥 정렬을 해놓고 lower_bound를 돌려도 되고, 혹은 정렬을 해놓고 sweeping을 해서 구할 수도 있다. 딱히 까다로울게 없었던 문제. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;

#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back

ll arr[1010101];
pii brr[1010101];

int main(){
	ll i,j,k,l,m,n;
	scanf("%lld %lld %lld",&n,&m,&k);
	for(i=1;i<=n;i++)
		scanf("%lld",&arr[i]);
	arr[0]=-1e18;
	arr[n+1]=1e18;
	for(i=1;i<=m;i++)
		scanf("%lld %lld",&brr[i].ff,&brr[i].ss);
	sort(arr+1,arr+1+n);
	sort(brr+1,brr+1+m);
	ll ans=0;
	ll fl=0;
	for(i=1;i<=m;i++){
		while(brr[i].ff>=arr[fl+1]) fl++;
		if((k>=abs(brr[i].ff-arr[fl])+brr[i].ss)||(k>=abs(brr[i].ff-arr[fl+1])+brr[i].ss)) ans++;
	}	
	printf("%lld",ans);
}

BOJ 8984 고등부 2번 막대기 

문제 링크 : https://www.acmicpc.net/problem/8984

문제 태그

DP

문제 풀이

일단 문제를 읽는 과정에서 딱 보자마자 이 문제는 DP문제라는 것을 생각할 수 있을정도였다.
조건 3개를 복습해보자. (1) 막대기들은 끝점을 제외하곤 서로 교차하지 않는다. (2) 세 개 이상의 막대기 끝이 한 점에서 만나지 않는다. (3) 모든 막대기는 연결되어 있다. 이 조건을 잘 읽고 생각해야 한다. 1번조건을 못봐서 푸는데 좀 많이 고생을 했다. 아무튼 오른쪽으로 쭉 지그재그로 되는 형태라는 것이다. 
DP를 풀기 위해서는 위치의 순서관계가 명확해야한다. A부분을 채우고 이 값을 이용해서 B부분을 채워나가는 것이다. 이때 한 쪽으로 쭉 지그재그 형태이기 때문에 각 점별로 순서관계가 명확하다는 것을 확인할 수 있다. 
UDP[i] 를 위쪽의 i번째 지점을 오른쪽 끝점으로 하는 최대 지그재그 선의 길이 라고 정의하고
DDP[i] 를 아래쪽의 i번째 지점을 오른쪽 끝점으로 하는 최대 지그재그 선의 길이 라고 정의한다.
그러면 선분들을 정렬시켜 놓고, DP식을 조금 더 생각해서 간단하게 문제를 해결할 수 있다. 

코드

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

struct lin{
    ll u,d,len;
};

ll udp[1010101];
ll ddp[1010101];

ll upoi[1010101];
ll dpoi[1010101];
lin arr[1010101];

bool sf(lin a,lin b){
    if(a.u!=b.u) return a.u<b.u;
    return a.d<b.d;
}

int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld %lld",&arr[i].u,&arr[i].d);
        arr[i].len=abs(arr[i].u-arr[i].d)+m;
        upoi[i]=arr[i].u;
        dpoi[i]=arr[i].d;
    }

    sort(upoi+1,upoi+1+n);
    sort(dpoi+1,dpoi+1+n);
    sort(arr+1,arr+1+n,sf);

    for(i=1;i<=n;i++){
        ll ux=lower_bound(upoi+1,upoi+1+n,arr[i].u)-upoi;
        ll dx=lower_bound(dpoi+1,dpoi+1+n,arr[i].d)-dpoi;

        ll uval=udp[ux];
        ll dval=ddp[dx];

        udp[ux]=max(uval,dval+arr[i].len);
        ddp[dx]=max(dval,uval+arr[i].len);
    }

    ll ans=0;
    for(i=1;i<=n;i++)
        ans=max({ans,udp[i],ddp[i]});
    printf("%lld",ans);
}

BOJ 8986 고등부 3번 전봇대

문제 링크 : https://www.acmicpc.net/problem/8986

문제 태그

수학, 삼분탐색.

문제 풀이

 일단 문제를 보자마자 파라메트릭 서치를 생각했었다. 최적의 상황을 생각하는게 아니라 전봇대 간의 거리를 고정시켜 놓고 이때 움직여야 하는 거리를 구하는 것은 쉽기 때문이다. f(x)를 전봇대간 거리가 x일때 움직여야 하는 최소거리라고 하자. x에 대한 f(x)값은 그냥 조금만 생각하면 순서대로 위치시켜야 하기 때문에 $O(N)$에 구할 수 있다는 것을 알 수 있다.  이때 f(x)에 대한 관찰을 해보면 아래로 볼록한 형태이기 때문에 삼분탐색을 쓰면 이 문제를 해결할 수 있다. 
 혹은 이 문제를 보고 바로 직관적으로 너무 간격이 커도 안되고 작아도 안되네 -> 정답에 근접해질수록 횟수가 계속 줄어들겠네 -> 삼분탐색을 써야겠다. 와 같은 사고의 흐름으로 바로 풀이에 도달 할 수 있다. 
 삼분탐색을 들어만 보고 한 번도 구현은 안해봤지만, 이분탐색을 좀만 해봤으면 무리없이 구현해낼 수 있는 수준이다.  

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;

#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back

ll arr[1010101];
ll n;

ll fun(ll x){
	ll ret=0;
	for(ll i=0;i<n;i++){
		ret+=abs(arr[i]-i*x);
	}
	return ret;
}
int main(){
	ll i,j,k,l,m;
	scanf("%lld",&n);
	for(i=0;i<n;i++)
		scanf("%lld",&arr[i]);
	ll lo=0;
	ll hi=1e9;
	while(lo+10<hi){
		ll mid1=(lo+lo+hi)/3;
		ll mid2=(lo+hi+hi)/3;

		if(fun(mid1)<fun(mid2)) hi=mid2;
		else lo=mid1;
	}
	ll ans=1e18;
	for(i=lo;i<=hi;i++)
		ans=min(ans,fun(i));
	printf("%lld",ans);
}

BOJ 8987 고등부 4번 수족관 3

문제 링크 : https://www.acmicpc.net/problem/8987

문제 태그

Segment Tree or DNC?

문제 풀이

풀이 준비중...