문제 풀이 의식의 흐름 ( JOI 18, Worst reporter )

https://oj.uz/problem/view/JOI18_worst_reporter3

[05-27,14:00] D_i는 주기를 가진다.

[05-27,14:56] 1번째 사람은 무조건 D_1의 배수에 위치.

[05-27,14:58] 수정, 1번째 사람은 무조건 (D_1의 배수)-1에 위치.

[05-27,15:20] 각 학생의 규칙을 찾음

[05-27,17:16] 구현 시작

[05-27,17:40] 구현 귀찮아서 때려치고 내일로 미룸

[05-28,17:38] 구현 재시작

[05-28,17:50] 구현 완료, AC ( 100점! )

풀이

말했다시피 각 학생은 규칙을 가진다.

규칙은 몇번 해보면 알겠지만, 각 학생마다 주기가 

임이 됨을 알 수 있다. 몇번 노가다하면 나온다. 여기까진 굉장히 빨리 찾았는데.. 각 쿼리를 처리하는 방법을 몰라서 망했다

각 쿼리를 처리하는 방법은 다음과 같다.

일단, 시간 T초일 때 각 학생의 위치는 우리는 O(1)에 알 수 있다. 그 이유는, 우리는 주기를 알 고 있기 때문이다!

M번째 학생의 위치는

이 된다는 것을 알 수 있다.

그리고, 제일 중요한건 뛸 때 각 학생은 무조건 (그 이전 학생 위치) -1로 뛴다

이가 의미하는것은, 항상 학생들의 좌표는 단조 감소한다는 점이다.

따라서, 우리는 이분탐색을 할 수 있다.

이분탐색 시 조심할 점은 학생들의 좌표는 단조 증가가 아니라 단조 감소이므로, 우리가 찾고자 하는 좌표의 값이 크면 인덱스의 값은 작아지고, 반대로 좌표의 값이 작으면 인덱스의 값은 커진다는 점이다.

이를 고려하여 [L,R]을 [L,INF) - [R+1,INF)로 하여서 이분탐색을 실행하면 뚝!딱!

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[600000];
int n;
int bef(int t,int k)
{
    int l=0,r=n+1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(-mid+t/a[mid]*a[mid]>=k) l=mid+1;
        else r=mid;
    }
    return r;
}
int main()
{
    int q; scanf("%d %d",&n,&q);
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]=((a[i]-1)/a[i-1]+1)*a[i-1];
    }
    while(q--)
    {
        int t,i,j; scanf("%d %d %d",&t,&i,&j);
        printf("%d\n",bef(t,i)-bef(t,j+1));
    }
}