13072. 병사관리

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 1차 코드배틀)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

풀이에 실패하였다.
- 예제 입출력 기준 4_/25개만 정답.
- 시간 초과.
Indexed Priority Queue를 이용하여 풀이를 시도하였다.
군인의 수를 $S$_soldier, 팀의 수를 $T$_team로 정의한다.
각 팀은 Indexed Priority Queue로 이루어져 있다.
Indexed Priority Queue는 하나의 Heap과 Index배열로 이루어져 있다.
- Heap: 각 원소가 key, value 속성을 가지며, Heap 상태를 유지하는 배열이다.
- Index배열: 각 원소의 Heap 상에서의 위치를 key로 임의접근하여 가져오는 것이 가능한 배열이다.
Heap을 이루는 원소들의 key는 군인의 mID, value는 군인의 평판 우선순위를 나타낸다.
각 군인이 속한 팀을 $O(1)$에 구하기 위해 군인 별 소속 팀을 기록하는 배열을 선언하여 사용하였다.
평판 우선순위는 공용체를 사용하여 비교한다. 하나의 int에서 비트 필드를 이용해 mScore과 mID를 모두 표현한다.
- 앞 8개 비트는 mScore를 나타낸다.
- 나머지 24개 비트는 mID를 나타낸다.
하나의 테스트케이스에 대한 시간복잡도는 약 $O(10^5 \times S \log{S})$¹ 이다.² (일부 계수와 상수항을 무시)
- init()은 $O(T)$에 모든 팀의 큐를 초기화한다.
- hire()은 $O(1)$에 지정된 팀의 큐를 찾고, $O(\log{S})$에 새로운 원소를 삽입한다.
- fire()은 $O(1)$에 지정된 군인이 속한 팀의 큐를 찾고, $O(1)$에 우선순위 큐 안에서 해당 군인의 위치를 특정한 후, $O(\log{S})$에 해당 원소를 제거한다.
- updateSoldier()는 $O(1)$에 지정된 군인이 속한 팀의 큐를 찾고, $O(1)$에 우선순위 큐 안에서 해당 군인의 위치를 특정한 후, 값을 수정한 뒤, $O(\log{S})$에 힙을 재정렬한다.
- updateTeam()은 지정된 팀의 모든 원소 값을 수정한 후, $O(S\log{S})$에 힙을 재정렬한다.
- bestSoldier()은 $O(1)$에 지정된 팀(우선순위 큐)의 top 원소를 가져와 그 key를 반환한다.
우수 풀이자 발표를 보면, 풀이에 성공하신 대다수 분들께서는 Doubly-linked list를 사용하셨다. 그 이유로는 bestSoldier()의 호출 횟수가 $100$회 이하 이므로 $O(S)$에 풀이해도 된다는 것과, mScore 별로 linked list를 나누어 구현하면 updateTeam()을 $O(1)$에 수행할 수 있다는 것이다. 여기에 추가로 군인의 mID를 통해 각 군인 노드 포인터에 임의 접근 가능한 배열을 선언하여 사용할 경우 $O(1)$에 추가/제거/수정할 군인에 접근할 수 있다. 따라서 linked list의 insert, remove 작업에 해당하는 hire()과 fire(), 그리고 insert+remove 작업에 해당하는 updateSoldier()를 모두 $O(1)$에 수행 할 수 있게 된다.

사용자 코드 (solution.cpp):

#include <vector>

#define MIN_MID 1
#define MAX_MID 100000
#define MIN_MTEAM 1
#define MAX_MTEAM 5
#define MIN_MSCORE 1
#define MAX_MSCORE 5

using namespace std;

struct indexed_heap_element
{
    int index;
    int value;
};

struct indexed_heap
{
    int size;
    struct indexed_heap_element heap[MAX_MID+1];
    int indices[MAX_MID+1];
};

void heap_swap(struct indexed_heap *ih, int index1, int index2)
{
    struct indexed_heap_element tmp = ih->heap[index1];
    ih->heap[index1] = ih->heap[index2];
    ih->heap[index2] = tmp;
    ih->indices[ih->heap[index1].index] = index1;
    ih->indices[ih->heap[index2].index] = index2;
}

void heap_heapify_up(struct indexed_heap *ih, int index)
{
    while (index > 0) {
        int parent = (index-1) >> 1;
        if (ih->heap[index].value < ih->heap[parent].value) {
            break;
        }
        heap_swap(ih, index, parent);
        ih->indices[ih->heap[index].index] = index;
        ih->indices[ih->heap[parent].index] = parent;
        index = parent;
    }
}

void heap_heapify_down(struct indexed_heap *ih, int index)
{
    while (index < ih->size) {
        int left = (index << 1) + 1;
        int right = (index << 1) + 2;
        if (right < ih->size && ih->heap[right].value > ih->heap[left].value && ih->heap[right].value > ih->heap[index].value) {
            heap_swap(ih, index, right);
            index = right;
            continue;
        }
        if (left < ih->size && ih->heap[left].value > ih->heap[index].value) {
            heap_swap(ih, index, left);
            index = left;
            continue;
        }
        break;
    }
}

void heap_push(struct indexed_heap *ih, int index, int value)
{
    ih->heap[ih->size].index = index;
    ih->heap[ih->size].value = value;
    ih->indices[index] = ih->size;
    ih->size++;
    heap_heapify_up(ih, ih->size-1);
}

struct indexed_heap_element heap_pop(struct indexed_heap *ih)
{
    struct indexed_heap_element retval = ih->heap[0];
    heap_swap(ih, 0, ih->size-1);
    ih->size--;
    heap_heapify_down(ih, 0);
    return retval;
}

struct indexed_heap_element heap_top(struct indexed_heap *ih)
{
    return ih->heap[0];
}

struct indexed_heap_element heap_find(struct indexed_heap *ih, int index)
{
    return ih->heap[ih->indices[index]];
}

void heap_update(struct indexed_heap *ih, int index, int value)
{
    ih->heap[ih->indices[index]].value = value;
    heap_heapify_up(ih, ih->indices[index]);
    heap_heapify_down(ih, ih->indices[index]);
}

void heap_remove(struct indexed_heap *ih, int index)
{
    heap_swap(ih, 0, ih->indices[index]);
    heap_pop(ih);
}

int teamLookUpTable[MAX_MID+1];
struct indexed_heap teams[MAX_MTEAM+1];

union soldier_rank {
    struct soldier_rank_details {
        int id : 24;
        int score : 8;
    } details;
    int value;
};

int bound(int x, int min, int max)
{
    if (x > max) return max;
    if (x < min) return min;
    return x;
}

void init()
{
    for (int mTeam = MIN_MTEAM; mTeam <= MAX_MTEAM; mTeam++) {
        teams[mTeam].size = 0;
    }
}

void hire(int mID, int mTeam, int mScore)
{
    union soldier_rank rank;
    rank.details.id = mID;
    rank.details.score = mScore;

    heap_push(&teams[mTeam], mID, rank.value);
    teamLookUpTable[mID] = mTeam;
}

void fire(int mID)
{
    heap_remove(&teams[teamLookUpTable[mID]], mID);
}

void updateSoldier(int mID, int mScore)
{
    heap_update(&teams[teamLookUpTable[mID]], mID, mScore);
}

void updateTeam(int mTeam, int mChangeScore)
{
    union soldier_rank rank;
    for (int i = 0; i < teams[mTeam].size; i++) {
        rank.value = teams[mTeam].heap[i].value;
        rank.details.score = bound(rank.details.score + mChangeScore, MIN_MSCORE, MAX_MSCORE);
        teams[mTeam].heap[i].value = rank.value;
    }
    for (int i = 0; i < teams[mTeam].size; i++) {
        heap_heapify_up(&teams[mTeam], i);
        heap_heapify_down(&teams[mTeam], i);
    }
}

int bestSoldier(int mTeam)
{
    return heap_top(&teams[mTeam]).index;
}

$O(T+10^{5}\log{S}+10^{5}\log{S}+10^{5}\log{S}+10^{5}S\log{S}+10^{2})$ 에서 근사하여 계산함. ↩
$S \leq 10^5$이므로, 최악의 경우 약 $O(10^{10} \cdot 17)$의 시간이 소요될 것이다. 일반적으로 $O(10^8)$일 때 1초가 소요된다고 알려져 있으므로, 한 테스트케이스 당 약 $1700$ 초 ($\approx 30$분) 소요 될 가능성이 있다. ↩