BOJ 1637 날카로운 눈

문제

https://www.acmicpc.net/problem/1637

등차수열이 몇개 주어질 때, 그 수열에 나오는 수들 중 홀수번 등장하는 수를 찾는 문제였다.

 

풀이

이 문제는 종만북에 "캐나다 여행" 으로도 나오고, 2018년 여름학기 계절학교 문제에도 나온 문제이다.

언뜻 봐서는 파라마트릭 서치인지 알 수 없는 문제인데, 이제부터 딱히 어떻게 풀지 모르겠을 때 파라마트릭 서치를 사용하도록 하자.

 

문제는 간단한데, 홀수개 있는 정수를 어떻게 찾을까? 라는 문제에서, k라는 정수 이하의 정수의 개수를 세보자! 라는 문제로 바꿀 수 있다.

그럼 이걸로 어떻게 홀수개 있는 정수를 알아낼 수 있을까?

바로 누적합의 홀짝성을 이용하는 것이다.

x가 홀수개 있는 수라고 하자. x미만의 모든 수에 대해서는 다 짝수개 있으므로 x미만의 k는 결정함수의 값이 모두 짝수가 나올 것이다. 또한, x이상의 수에 대해서는 결정함수의 값이 홀수가 나올 것이다.

딱 이분탐색하기에 좋게 생긴것 같다.

나중에 k의 개수를 출력할 때도 누적합의 아이디어를 이용해서 f(k)-f(k-1) 하면 된다.

풀이는 간단하지만 생각 과정이 많이 어려운 문제였다.

 

시간 복잡도 : $O(N*32)$

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 20000;

struct Num{ ll a, b, c; };
int n;
Num arr[MAXN+10];

ll decide(ll num)
{
    int i;
    ll cnt=0;

    for(i=0; i<n; i++) if(arr[i].a<=num) cnt+=(min(arr[i].c, num)-arr[i].a)/arr[i].b+1;

    return cnt;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%lld%lld%lld", &arr[i].a, &arr[i].c, &arr[i].b);

    ll lo=-1, hi=1ll<<32;
    while(lo+1<hi)
    {
        ll mid=lo+hi>>1;
        if(decide(mid)%2) hi=mid;
        else lo=mid;
    }

    if(hi==1ll<<32) { printf("NOTHING\n"); return 0; }
    printf("%lld %lld", hi, decide(hi)-decide(hi-1));
    return 0;
}