후기

  • 실제 참가한 시험으로 4문제 풀면 너무 좋겠다 했는데 4문제를 풀어버렸다.
  • 첫 문제를 10분 안에 풀고 두 번째 문제에서 어떻게 접근할지 고민하다가 1시간대를 통과했다.
  • 망했다 했는데 남은 1시간 동안 빡집중해서 3문제를 풀어냈다.
  • 2번만 좀만 빨리 풀었다면 엄청 좋은 결과가 있을 뻔했다. 일단 엄청 만족스러운 라운드였다!

사진

A. Two Rival Students

문제 링크

  • 이 문제는 두 학생을 최대한 떨어뜨려야 한다.
  • 이 때 학생이 끝에 다달았는지 확인을 해야하는게 포인트이다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
int t, n, x, a, b;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d %d %d", &n, &x, &a, &b);
        if(a > b)swap(a, b);
        printf("%d\n", b - a + min(a - 1 + n - b, x));
    }
}

B. Magic Stick

문제 링크

  • 이 문제는 보자마자 최근에 풀었던 dp 문제가 떠올랐다!
  • 해일스톤 수열이라는 문제로 규칙만 다랐기에 dp 혹은 다른 방법으로 접근하려 했다.
  • 한시간을 고민하다 결국 포기… 그리고 부기 노트에 과정을 조금 끄적이다보니 x가 4 이상인 경우는 모든 수를 생성해낼 수 있다는 것을 알게 되었다.
  • 때문에 1, 2, 3에 대한 경우의 수만 처리해주면 되는 아주 간단한 문제였다… 이것만 빨리 깨달았어도ㅠㅠㅠㅠ

코드

#include <cstdio>
int t, x, y;
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &x, &y);
        if(x > 3)printf("YES\n");
        else if(x == 3 && y <= 3)printf("YES\n");
        else if(x == 2 && y <= 3)printf("YES\n");
        else if(x == 1 && y == 1)printf("YES\n");
        else printf("NO\n");
    }
        
}

C. Dominated Subarray

문제 링크

  • 이 문제는 2초가 주어지는데 tc 1000개에 n이 200000이다. 그러면 정답을 찾는데는 적어도 O(n)이하로 풀어내야한다.
  • 어떻게 반복문 한번만에 끝내버리지.. 하다가 방법이 떠올랐다.
  • 가장 최근에 나온 똑같은 수까지의 거리로 answer을 업데이트 할 것이다.
  • 때문에 a라는 수가 가장 최근에 언제 나왔는지를 arr[a]에 인덱스를 저장해주어 현재 인덱스와의 거리를 계산한다.
  • arr[a]가 -1이면 최근이 없다는 걸로 거리 계산은 생략한다.

코드

#include <cstdio>
#include <cstring>
int t, n, temp, arr[200001];
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        memset(arr, -1, sizeof(arr));
        int ans = 987654321;
        for(int i = 0; i < n; i++){
            scanf("%d", &temp);
            if(arr[temp] == -1)arr[temp] = i;
            else {
                if(ans > i - arr[temp] + 1)ans = i - arr[temp] + 1;
                arr[temp] = i;
            }
        }
        if(ans == 987654321)printf("-1\n");
        else printf("%d\n", ans);
    }
}

D. Yet Another Monster Killing Problem

문제 링크

  • 최후의 30분…으로 이 문제를 풀 수 있을지 의문이었다.
  • 이 문제도 n만에 풀 방법을 생각해냈다.
  • prefix sum을 이용해서 미리 하루에 싸울 수 있는 횟수당 최대 힘을 저장해 놓는다.
  • 그리고 나서 쭉 돌면서 하루에 최대한으로 싸울 수 있는 횟수로 진행하고 다음 인덱스로 넘어간다.
  • 이때 14번 케이스에서 시간 초과가 뜨는 걸 보고 ps 어레이를 초기화 해주는데 드는 시간을 줄이기로 했다.
  • It is guaranteed that the sum of $n+m$ over all test cases does not exceed $2⋅10^5$.
  • 위에 말을 참고해서 tm이라는 변수에 바로 이전 테스트 케이스까지 해서 사용한 어레이 index를 저장해놓고 이를 이용해서 어레이를 누적해서 사용했다.

코드

#include <cstdio>
int t, n, arr[200001], m, ps[200001], tm, p, s;
int main(){
    scanf("%d", &t);
    while(t--){
        //maxp은 최대힘
        int maxp = 0, ans = 1;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)scanf("%d", &arr[i]);
        scanf("%d", &m);

        //ps[i]는 하루에 i까지 상대할때 쓸 수 있는 최대힘
        for(int i = 0; i < m; i++){
            scanf("%d %d", &p, &s);
            if(p > ps[tm + s])ps[tm + s] = p;
            if(s > maxp)maxp = s;
        }

        //PREFIX SUM
        for(int i =  tm + maxp - 1; i >= tm; i --){
            if(ps[i] < ps[i + 1])ps[i] = ps[i + 1];
        }

        //하루 최대치를 찾는 중...
        int M = 0, cnt = 0;
        for(int i = 0; i < n; i++){
            cnt++;
            if(M < arr[i])M = arr[i];
            if(ps[tm + cnt] >= M)continue;
            else {
                if(cnt == 1){
                    ans = -1;
                    break;
                }
                cnt = 0, M = 0, i--;
                ans ++;
            }
        }
        printf("%d\n", ans);
        tm += maxp + 1;
    }
}

느낀점

  • 이것보다 쪼끔 더 잘한거 한번이면 블루인데….제바라아아라~~ㅋㅋㅋ