글쓴이 ·0개의 댓글

AB / D small을 풀었다.

반성할 점은 D small 짜는데 한시간 가량 걸린거랑 AB에서 뻘미스 한 것.

A에서의 뻘미스: s + e < x
올바른 코드: data[s] + data[e] < x

B에서의 뻘미스: A output 파일을 잘못 냈다.

여튼 티셔츠는 받았으니 나쁘지는 않음. C 풀이에 쓰이는 가로로 길 건너는(?) 테크닉이 종종 나오던데 이번 기회에 확실하게 알아둬야겠다.

글쓴이 ·0개의 댓글

아직 QR이 안 끝났으니 풀이는 안 쓰고 문제 스포랑 감상만 적는다.

A

A는 진짜 단순한 코딩 문제였다. 4 by 4 숫자 배치 두 개 주고 적절히 처리하는 문제였다.

B

B는 쿠키 클리커의 패러디 문제였다. 수학 약간 쓰는 문제였고, 증명 안 하고 감으로 풀었는데 small 맞길래 large도 그냥 냈다.

D

C를 넘기고 D를 먼저 풀었다.

D는 두 사람이 게임하는데 한 명은 게임의 원래 룰대로 최적으로 플레이하고, 다른 한 명은 속임수를 써서 플레이한다. 이 때, 속임수를 썼을 때랑 안 썼을 때 점수 차이를 출력하는 문제였다.

속임수를 안 쓸 때의 상대방의 최적 전략을 찾은 다음 속임수를 써서 상대방의 최적 전략을 이길 수 있는 또 다른 최적 전략을 찾아야 하는 형태로 문제가 한 단계 비틀어져 있어서 재밌었다.

C

C는 지뢰찾기 문제였다. R과 C, 지뢰 개수를 줄 때 단 한 번의 클릭으로 모든 칸을 열 수 있는 배치가 있다면 조건을 만족하는 임의의 배치를 출력하고, 없다면 Impossible을 출력하면 된다.

많이 풀어보지 않은 문제 스타일이었고, 안 풀어도 다음 라운드 진출이라 안 풀려고 했다가 밤중에 다시 들어와서 풀었다. 아이디어 하나가 있으니까 처리할 케이스가 확 줄어들어서 생각보다는 쉬웠는데 초기 접근이 너무 당황스러웠다. 다른 문제들은 딱 답을 찾기만 하면 되는데 ‘조건을 만족하는 임의의 해’를 찾는다는 문제 스타일이 생소했다.

종합 후기

QR치고 딱 적절했던 난이도였다고 생각한다. 작년에는 뻘짓하다가 티셔츠 못 받았는데 올해는 티셔츠 받아야지!

글쓴이 ·0개의 댓글
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
const int MAX = 100020;

struct report {
    int s, e;

    report() {}
    report(int s, int e) : s(s), e(e) {}

    bool operator < (const report &t) const {
        if(s == t.s) return e < t.e;
        return s < t.s;
    }
};

int n, m, k, yFull, nFull;
report yes[MAX], no[MAX];

void input(){
    scanf("%d%d%d", &n, &k, &m);

    int i;
    for(i = 0; i<m; i++){
        int ts, te, c;
        scanf("%d%d%d", &ts, &te, &c);

        //닌자가 없다는 보고는 no에, 있다는 보고는 yes에 저장
        if(c == 0) no[nFull++] = report(ts, te);
        else yes[yFull++] = report(ts, te);
    }
}

bool none[MAX];
int cnt, lFind[MAX], rFind[MAX];

void init(){
    //보고들을 좌표 순으로 정렬
    sort(yes, yes+yFull);
    sort(no, no+nFull);

    int i, now;

    //닌자가 있다는 보고들을 정리. yes 배열을 스택으로 사용한다.
    now = 1;
    for(i = 1; i<yFull; i++){
        /*
        (s1, e1) (s2, e2)일 때 s1 <= s2 && e2 <= e1이면
        첫 번쨰 보고를 삭제하고 두 번째 보고만 삽입
        */
        while(yFull && yes[now-1].e >= yes[i].e)
            now--;
        yes[now++] = yes[i];
    }
    yFull = now;

    //닌자가 없다는 보고들을 정리
    cnt = n;
    int j = 1;
    for(i = 0; i<nFull; i++){
        if(j < no[i].s) j = no[i].s;
        for(; j <= no[i].e; j++){
            //닌자가 확실히 없는 덤불은 none 배열에 체크
            none[j] = 1;
            cnt--;
        }
    }
    //루프가 끝나면 cnt는 '닌자가 있을 가능성이 있는 덤불의 수'가 된다.

    /*
    lFind[i]는 번호가 i 이하인 덤불 중
    '닌자가 있을 가능성이 있는 덤불' 중 가장 번호가 큰 덤불의 번호
    */
    for(i = 1; i<=n; i++){
        if(!none[i]) lFind[i] = i;
        else lFind[i] = lFind[i-1];
    }

    /*
    rFind[i]는 번호가 i 이상인 덤불 중
    '닌자가 있을 가능성이 있는 덤불' 중 가장 번호가 작은 덤불의 번호
    */
    for(i = n; i>=1; i--){
        if(!none[i]) rFind[i] = i;
        else rFind[i] = rFind[i+1];
    }
}

int left[MAX], lFull, right[MAX], rFull;
vector < int > res;

void solve(){
    int i;
    //'닌자가 숨어있을 가능성이 있는 덤불'이 k개와 일치한다면 k개 전부가 답.
    if(cnt == k){
        for(i = 1; i<=n; i++)
            if(lFind[i] == i)
                res.push_back(i);
    } else {
        int last;

        /*
        k개보다 많다면, 탐욕 알고리즘을 사용해 '보고를 만족하는 최소의 닌자 수'를 구한다.

        닌자들을 놓을 수 있는 가장 오른쪽 칸에 놓아서 채우는 경우, 가장 왼쪽 칸에 놓아서 채우는 경우를 구한다.
        조금 생각해보면 오른쪽에서부터 채울 때와 왼쪽에서 채울 때의 닌자 수가 같다는 것을 알 수 있다. (lFull == rFull)

        닌자들을 최소로 사용하여 채울 때 i번째 닌자가 있을 수 있는 가장 왼쪽 좌표가 left[i], 가장 오른쪽 좌표가 right[i]이다.
        */
        last = 0;
        for(i = 0; i<yFull; i++){
            if(last < yes[i].s){
                left[lFull++] = lFind[yes[i].e];
                last = lFind[yes[i].e];
            }
        }

        last = n+1;
        for(i = yFull-1; i>=0; i--){
            if(last > yes[i].e){
                right[rFull++] = rFind[yes[i].s];
                last = rFind[yes[i].s];
            }
        }

        //닌자를 최소로 사용했을 때 k명인 경우
        if(lFull == k){
            for(i = 0; i<lFull; i++){
                /*
                k명의 닌자 중 존재할 수 있는 가장 왼쪽 좌표와 가장 오른쪽 좌표가 같은 닌자는 위치가 고정되므로 답이 된다.
                그렇지 않은 닌자들은 최소 좌표와 최대 좌표 중 다른 칸에 존재할 수 있는 가능성이 있기 때문에 답이 될 수 없다.
                */
                if(left[i] == right[rFull-1-i]){
                    res.push_back(left[i]);
                }
            }
        //닌자를 최소로 사용했을 때 k명보다 작은 경우 (보고를 만족하는 배치가 존재하기 때문에 k보다 클 수는 없다.)
        } else {
            for(i = 0; i<yFull; i++){
                /*
                닌자를 발견했다는 보고에 대해, 보고 범위 이내에 '닌자가 숨어 있을 가능성이 있는 덤불'이 하나인 경우만 답이 된다.

                그렇지 않은 덤불들은 닌자가 숨어 있을 가능성이 있는 덤불 중
                그 덤불의 바로 왼쪽 덤불과 바로 오른쪽 덤불을 대체해서 선택하면
                그 덤불을 선택하지 않고도 모든 보고를 만족시킬 수 있다.

                이 경우 닌자의 총 인원 수가 증가할수도 있지만, 현재 닌자 수가 k보다 작기 때문에 상관 없다.
                */
                if(lFind[lFind[yes[i].e]-1] < yes[i].s)
                    res.push_back(lFind[yes[i].e]);
            }
        }
    }

    //정답을 출력한다.
    if(res.empty()) puts("-1");
    else {
        for(i = 0; i<res.size(); i++)
            printf("%d\n", res[i]);
    }
}

int main(){
    input();

    init();
    solve();

    return 0;
}

APIO 2012 경비병(Guard) 코드 및 주석입니다.