Problem

사탕상자

Idea

leaf의 개수가 100만 이기에 메모리는 가능할 것같다.
만약 leaf개수가 천만이라면:
4000만 * 4byte (int) = 150mb 가 넘을 수 있기에 주의

query 구현은 kth 번째 수 찾기와 같다

int kth(node, s, e, kth) {
    if (s == e) {
        return s;
    }
    mid = (s + e) >> 1;

    if (tree[node * 2] >= kth) {
        return find(node * 2, s, mid, kth);        
    } else {
        return find(node * 2+1, mid+1, e, kth - tree[node * 2]);
    }
}

int query(kth) {
    return kth(1, 0, MAX, kth);
}

or

static int query(int val) {
    int s = 1;
    int e = MAX;
    int node = 1;

    int mid = (s + e) / 2;
    int left = 0;
    while (s != e) {
        left = tree[node * 2];
        mid = (s + e) / 2;
        if (left >= val) {
            node = node * 2;
            e = mid;
        } else {
            node = node * 2 + 1;
            val = val - left;
            s = mid + 1;
        }
    }
    return s;
}

Problem

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

Idea

구간의 최소값: 구간의 가장 뛰어난 등수 정의

1과목기준으로 정렬을 한번하게되면 2,3과목만 보면된다.

구간 은 1부터 정렬이 되어있으므로 2과목 등수자체를 표현하고, 구간 값을 3과목 등수로 표현한다

즉, 각 구간 index는 2과목 등수를 표현, 구간 value는 3과목 등수로 업데이트한다

2과목을 기준으로 1등~ 2과목 등수 쿼리를 해
query한 값(구간내 1,2번째 과목의 가장 뛰어난 등수)이 내 등수보다 크다면 나는 굉장한 학생이다

예) 1과목 정렬을 하면
1: 1, 2, 8
2: 2, 5, 5
3: 3, 3, 1

예에서 보면

TC 첫번째 학생은 각 과목을 1등,2등 8등 하였다. 1과목을 1등을 하였으므로 3과목 모두 좋은 점수를 받은 학생은 존재할 수 없기에 굉장한 학생이다

2번째에서 1 ~ 5 등수인것들 중 3번째 값보다 큰값 (가장 작은 등수)이 있는지 확인해본다. 있다면 내 등 수보다 큰 학생이 있으므로 나는 굉장한 학생이다

Problem

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

Idea

혼자하는 게임 두 더미에서 하나씩 뺀다 남은카드가 없을 때까지 진행 얻은 점수 합의 최대

f(left, right) 현재 left/right board에서의 최대값 리턴

max( f(left-1, right), board[right] + f(left, right-1) if left > right

or, f(left-1, right-1), board[right] + f(left, right-1) if left > right )

Problem

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

Idea

f(a, b) : “현재 a 번째 색상에 대한 검색할 차례이며, b 개의 색상을 인접하지 않도록 선택한 상태”

true면 마지막 색을 선택가능
f(1, 0, true): 0번 색상을 선택하지않고 1번색으로 이동, (마지막 색상 선택 가능)
f(2, 1, false): 0번 색상을 선택하고 2번색으로 이동, (마지막 색상 선택 불가)

f(1,0): f(2,0), f(3,1)

f(2,1): f(3,1), f(4,2)

위 정의는 f(3,1) 처럼 중복이 일어날 수 있어 중복 제거 필요

Related

• https://www.acmicpc.net/workbook/view/173

Problem

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

Idea

poster 너비를 구간트리로 표현해 poster를 붙일 시마다 이전 poster가 붙어있는지 쉽게 판단 가능하다.
업데이트 구간이 커 lazy처리가 필요하고, 너비가 10^8 이기에 좌표 압축이 필요하다.

좌표 압축

• 절대 너비구간이 상대적으로 몇번째로 (최대 N) 큰지 표현(중복제거) 1 40
  2 60
  8 100
  30 40
  80 100
  

order: 1 2 8 30 40 40 60 80 100 100
compressed:1 2 3 4 5 6 7 8

ordered = new int[N * 2];
compressed = new ArrayList<Integer>();

int cnt = 0;
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    int l = Integer.parseInt(st.nextToken());
    int r = Integer.parseInt(st.nextToken());

    map[i] = new Poster(l, r);
    ordered[cnt++] = l;
    ordered[cnt++] = r;
}
Arrays.sort(ordered);
int s = 0;
cnt = 0;
for (int i = 0; i < 2 * N; i++) {
    if (s != tmp[i]) {
        compressed.add(tmp[i]);
        s = tmp[i];
    }
}

Related

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