BOJ 26248번 - 겨울 숲의 수호자

26248번: 겨울 숲의 수호자

서론

기반이 되는 논문은 링크에서 찾아볼 수 있다.

논문의 pseudocode를 그대로 구현하면 WA를 받는다.

약간의 수정이 필요한데 이를 위해서는 논문의 내용을 어느 정도는 이해하고 있어야 한다.

수정된 pseudocode를 공개하면 난이도가 대폭 낮아지기에 몇 가지 팁만 언급하고자 한다.

참고로 나도 논문의 모든 내용을 완벽하게 이해한 것은 아니라서 잘못된 부분이 존재할 수 있다.

 

assert 도배하기

코드의 온갖 부분에 assert를 도배하자.

제출 시 AssertionFailed가 발생한다면 오류를 찾기 쉽다.

stress test를 돌리면서 동일한 AssertionFailed가 발생하는 TC를 찾으면 된다.

 

block의 정의

block의 정의는 논문의 Definition 2.2에 나와 있다.

job (0, p)와 (p, 2p)는 서로 다른 block에 속함에 유의하자.

 

SMPP-ELJTT

SMPP-ELJTT 알고리즘은 굳이 구현할 필요가 없다.

그냥 분할 정복하며 재귀적으로 해결하면 된다.

 

LDD rule

block의 분해 과정에서 LDD rule에 의하여 job을 선택하게 된다.

이때 due date가 동일하다면 release date가 늦는 것을 선택해야 한다.

간과하기 쉬운 부분이다.

 

t(V) 관리하기

t(V)를 필요할 때마다 계산할 수도 있지만 V가 비어 있으면 계산이 불가능해진다.

에디토리얼처럼 변수 T를 정의하고 t(V)를 관리하도록 하자.

V가 비게 되면 T의 값은 다음과 같이 갱신된다.

• 논문에서는 T를 second last block의 ending time으로 설정한다.
• 에디토리얼에서는 단순히 T에 0을 대입한다.
• 나의 구현에서는 기존 T에서 p를 뺀다.

어떤 방법이 정석인지는 나도 잘 모르겠다.

 

Re-index the jobs in U

논문에서는 매 순간 U에 속한 job들을 ERD rule에 의하여 정렬하라고 한다.

굳이 필요성을 못 느껴서 무시하였는데 정상 작동한다.

실제로 schedule하는 경우에만 정렬해주면 된다.

 

Δ 관리하기

기본적으로 job k에 대하여 Δ_k는 job k가 사용하게 된다.

예외적으로 job k가 optimal ending job인 경우에는 Δ_k를 다른 job들에게 양보해주어야 한다.

Δ_k를 공용 idle 구간으로 선언해주면 된다.

 

λ 갱신하기

기본적으로 job k에 대하여 λ_k는 일정하게 유지된다.

예외적으로 job k를 구간 [L - p, p]에 schedule하는 경우에는 λ_1..(k - 1)의 업데이트가 필요하다.

이 경우 Δ_k 전체가 공용 idle 구간으로 넘어가고 이는 곧 job 1..(k - 1)이 사용하게 된다.

결론적으로 sum(λ_1..(k - 1))이 len(Δ_k) = (p - λ_k)만큼 감소한다.

업데이트는 λ_(k - 1)부터 거꾸로 진행하면 된다.

 

이렇게 구현하였다면 Λ는 (L - T)보다 커질 수 없다.

따라서 min(Λ, L - T)는 항상 Λ이다.

 

나의 구현

다음과 같은 type alias를 정의하였다.

using ll = long long;

using blk = vector<job>;

using intv = pair<int, int>;

 

다음과 같은 구조체를 정의하였다.

struct job { int r, d, i };

struct ijob : job { int l, vector<intv> idle };

struct sch { int L, D, j };

 

다음과 같은 함수를 정의하였다.

vector<blk> decompose(blk &);

int get_r(blk &);

int get_t(blk &);

void solve(ijob &, list<intv> &, list<intv>::iterator &, int);

void solve(blk &);

 

끝

이 정도 팁이면 충분히 풀 수 있다고 생각한다.

다시는 루비 문제에 덤비지 않겠다고 다짐하며 끝