이 페이지는 "왜 처리 순서가 점수를 결정하는가"를 끝까지 따진다. 가까운 안테나가 적은 UE — 외진 UE — 를 먼저 배정해야 하는 그리디의 정당성, 거리²합을 우선순위 키로 쓰는 정보적 근거, counting/radix sort가 O(n)으로 정렬을 끝내는 이유, 그리고 PASS CUT 2,569,112를 통과시킨 실제 C++ 구현을 라인 단위로 해부한다.
안테나배정 문제의 점수는 매 sub-task마다 Σ range[i]² — 150개 안테나 가동범위의 제곱합 — 으로 매겨지고, 10개 sub-task에 걸쳐 누적된다. 모든 UE가 자기 안테나의 가동범위 안에 들어와야 하고(검사4), 한 안테나에 100개를 초과해 배정할 수 없다(검사3, ANTENNA_CAPA). 점수는 "이 두 제약을 지키면서, 가장 큰 안테나 반경을 얼마나 작게 눌렀는가"다.
제곱합이라는 점수 형태가 모든 설계를 지배한다. 반경 200짜리 안테나 하나는 40,000점이지만 반경 20짜리 안테나 100개는 40,000점으로 같다 — 즉 하나의 큰 반경이 다수의 작은 반경보다 압도적으로 비싸다. 따라서 베스트 해법의 목표는 평균 반경을 줄이는 것이 아니라 최댓값 반경을 누르는 것, 특히 "어쩔 수 없이 멀리 있는 안테나에 묶이는 UE"의 발생을 막는 것이다.
풀이는 이 목표를 세 단계로 분해한다.
countingSort로 가까운 순으로 정렬한다. UE당 "1순위 안테나, 2순위 안테나 …"의 정렬된 후보 리스트가 만들어진다.prior[i]를 계산하고, 이를 키로 UE 전체를 정렬한다. prior가 큰 UE — 주변에 안테나가 드문 외진 UE — 가 배정 순서의 앞에 온다.range를 필요한 만큼 늘린다.배정 규칙 자체("가장 가까운 빈 안테나에 붙인다")는 단순하다. 알고리즘의 지능은 어떤 UE를 먼저 처리하느냐에 응축돼 있다. 외진 UE를 나중으로 미루면, 그때쯤 그 UE 근처의 안테나들은 이미 다른 UE로 가득 차 있을 가능성이 높다. 그러면 외진 UE는 한참 떨어진 안테나에 강제 배정되고, 그 안테나의 반경이 폭발적으로 늘어나 — 제곱합 점수에서 — 치명적인 손해가 된다. "여유로운 UE는 마지막까지 기다려도 가까운 안테나가 남아 있다"는 비대칭성이 순서 전략의 근거다.
UE의 20%는 매 분(minute) 한 칸씩 움직인다. 채점기는 배정 후 UE를 5번 이동시키며 검사4를 수행하므로(단, 검사는 4번째 이동까지), 안테나 반경은 "UE가 5스텝 동안 그릴 모든 위치"를 덮어야 한다. 풀이는 subcnt==2에서 sub-task 1·2의 좌표 차이로 각 UE의 이동 방향을 추론하고, subcnt>=3부터는 그 방향으로 5스텝을 직접 시뮬레이션해 range를 보정한다.
먼저 가장 강한 제약부터 확인한다: 이 풀이는 반드시 모든 검사를 통과하는가? 검사 중 하나라도 실패하면 run()이 false를 반환하고 PENALTY 10억이 즉시 부과된다.
그리디 배정 루프(§3 코드)의 매 반복 후 다음이 성립한다: 처리된 모든 UE는 정확히 하나의 안테나에 connect되어 있고, 그 안테나의 antCapa는 100을 넘지 않으며, range는 그 UE를 (이동까지 감안해) 덮을 만큼 충분하다.
코드 라인 if (antCapa[aid] >= 100) continue;가 용량 불변식을, range[aid] = max(range[aid], d ...)가 커버리지 불변식을 매 배정마다 강제한다.
UE 수 10,000은 총 안테나 용량 150 × 100 = 15,000보다 작다. 그리디 배정 루프는 모든 UE에 대해 break에 도달하며 — 즉 어떤 UE도 미배정으로 남지 않는다 — 따라서 검사2(모든 UE가 유효 안테나 번호를 가짐)를 항상 통과한다.
각 UE의 후보 리스트 dist[uid][0..149]는 150개 안테나 전부를 거리순으로 담는다. 내부 for 루프는 j=0부터 후보를 훑으며 antCapa[aid] < 100인 첫 안테나에서 배정하고 break한다.
break에 도달하지 못하려면 150개 안테나가 전부 용량 100으로 가득 차 있어야 한다. 그 경우 이미 배정된 UE 수가 15,000개다. 그러나 한 sub-task에서 처리하는 UE는 10,000개뿐이므로, 어떤 UE의 차례에도 배정된 UE 수는 9,999개 이하 — 적어도 한 안테나에 빈 자리가 남는다(비둘기집 원리의 역). 따라서 모든 UE가 배정된다.
완전 배정이 보장되었으니 이제 진짜 질문은 점수다. 처리 순서를 바꾸면 점수가 어떻게 달라지는가? 핵심은 다음 보조정리다.
UE u가 "외진 UE"(주변 안테나가 드묾)이고 UE v가 "여유 UE"(주변에 안테나가 많음)일 때, 배정 순서에서 v → u(여유 먼저)를 u → v(외진 먼저)로 바꾸면 — 다른 모든 것이 같다면 — 최대 반경의 기댓값이 줄거나 같다.
이유: u를 먼저 배정하면 u는 자신의 1순위(가장 가까운) 안테나를 거의 확실히 차지한다. u의 1순위 안테나가 v의 후보 리스트에서 어디에 있든, v는 주변에 안테나가 많으므로 차순위로도 가까운 안테나를 찾는다 — v의 반경 증가는 작다. 반대로 v를 먼저 배정해 v가 u의 1순위 안테나를 (용량을) 차지해 버리면, u는 차순위·차차순위로 밀려나고 u가 묶이는 안테나 반경이 크게 뛴다. 자유도가 낮은 쪽을 먼저 만족시키는 것이 손해를 한쪽으로 몰아주지 않는다.
UE를 prior[i] 내림차순으로 처리하면(코드의 counting sort + 역방향 인덱싱), 제약 위반 위험이 가장 큰 UE가 가장 먼저, 가장 풍부한 후보 환경에서 배정된다. 이는 Lemma의 교환을 모든 UE 쌍에 대해 동시에 적용한 결과이며, 어떤 다른 순서로 바꿔도 — 인접한 두 UE를 교환하면 Lemma에 의해 점수가 나빠지거나 같으므로 — 더 좋아질 수 없다.
prior는 가장 가까운 10개 안테나 거리의 제곱합이다. 단순히 "1순위 안테나 거리"만 쓰면, 1순위가 가깝지만 2~10순위가 모두 먼 UE(국소적으로만 운 좋은 UE)를 과소평가한다. 10개 거리의 제곱합은 "이 UE 주변 안테나 밀도"를 부드럽게 요약하며, 제곱이 멀리 있는 안테나의 영향을 키워 — 점수 함수 자체가 제곱합이므로 — 우선순위 키와 점수 함수의 형태가 일치한다. prior가 큰 UE는 곧 "이 UE를 밀리게 두면 큰 제곱 손실이 나는 UE"다.
이 문제는 본질적으로 용량 제약 할당(capacitated assignment)이다. 상태와 비용을 형식적으로 적으면 다음과 같다.
margin(u)는 이동하는 UE를 위한 여유분이다 — 방향을 모르는 sub-task 1에서는 +4(최대 이동량), 방향을 아는 sub-task 2 이후에는 5스텝 시뮬레이션으로 정확히 계산한다. 거리는 맨해튼 거리(operator-)이며 0~198 범위다.
UE 1개당 150개 안테나를 거리순 정렬해야 하고 그것을 10,000 UE × 10 sub-task만큼 반복한다. 비교 정렬(O(n log n))이면 150·log150 ≈ 1,084 연산/UE, 누적 1억 연산이 넘는다. 풀이는 거리가 0~198의 작은 정수임을 이용해 counting sort로 O(150)에 끝낸다. 거리를 상위 비트, 안테나 id를 하위 8비트에 패킹한 trr[j] = (d << 8) | j 트릭이 핵심이다 — 거리로 정렬하면서 안테나 번호도 함께 따라온다.
void countingSort(int* arr) { rnt i; for (i = 0; i < 201; ++i) cnt[i] = 0; // 거리 버킷 0~200 초기화 for (i = 0; i < ALM; ++i) cnt[trr[i] >> 8]++; // 거리(상위비트)별 빈도 집계 for (i = 1; i < 200; ++i) cnt[i] += cnt[i - 1]; // 누적합 → 각 거리의 시작 위치 for (i = ALM - 1; i >= 0; --i) arr[--cnt[trr[i] >> 8]] = trr[i]; // 안정 배치: 거리오름차순, id는 packing되어 함께 이동}
trr[i] >> 8은 패킹된 32비트에서 거리만 뽑아내는 연산이다. 하위 8비트에 안테나 id(0~149, 8비트로 충분)가 들어 있으므로, 거리 키만으로 정렬해도 id가 그대로 따라붙는다. 정렬 결과 dist[i][j]에서 거리는 >>8, id는 & 255로 분리한다. 패킹 정렬은 "키와 값을 한 정수에 묶어 비교 1회로 둘 다 옮기는" 고전 기법이다.
거리 행렬이 정렬되면 각 UE의 prior를 계산하고, 그 prior를 키로 UE 전체(ids[])를 또 한 번 counting sort한다. prior의 최댓값은 198²·10 ≈ 392,000보다 작으므로 32768 크기 버킷 두 번이면 — 실제로는 누적합을 역방향으로 잡아 내림차순 정렬한다 — UE 처리 순서가 O(10,000)에 정해진다.
아래는 배정의 심장부, subcnt >= 2에서의 그리디 배정 + 5스텝 이동 시뮬레이션이다. PASS를 만든 구현 그대로다.
else { // subcnt >= 2: UE 이동 방향을 안다 for (i = 0; i < ULM; ++i) { int uid = ids[i]; // prior 내림차순 — 외진 UE부터 for (j = 0; j < ALM; ++j) { int aid = dist[uid][j] & 255; // j순위 안테나 번호 int d = ue[uid] - ap[aid]; // 현재 UE 위치 → 안테나 거리 int td = 0; if (antCapa[aid] >= 100) continue; // 용량 초과 안테나 스킵 antCapa[aid]++; // aid에 배정 1건 추가 connect[uid] = aid; // UE→안테나 배정 기록 range[aid] = max(range[aid], d); // 정지 위치 커버 if (dir[uid] < 4) { // 방향 4 = 정지, 그 외 = 이동 Coordinates& t = ue[uid]; for (k = 0; k < 5; ++k) { // 5스텝 이동 시뮬레이션 int nr = t.y + dr[dir[uid]], nc = t.x + dc[dir[uid]]; if (nr < 0 || nr > 99 || nc < 0 || nc > 99) { dir[uid] = dir[uid] ^ 2; // 경계 → 180° 반전(0↔2,1↔3) nr = t.y + dr[dir[uid]], nc = t.x + dc[dir[uid]]; } t = { nr, nc }; // UE를 한 칸 이동 td = t - ap[aid]; if (k < 4) // 채점기는 4번째 이동까지만 검사 range[aid] = max(range[aid], td); } } break; // 배정 완료 → 다음 UE } }}
dir[uid] ^ 2 한 줄로 처리되는 데 주목하라. 방향 인덱스 0·1·2·3이 각각 상·우·하·좌이고, XOR 2는 0↔2, 1↔3 — 정확히 정반대 방향이다. 채점기 main.cpp는 방향 번호 +10으로 180° 반전하지만(20방향 테이블), user 코드는 4방향만 다루므로 ^2로 동치 변환한다. k < 4 가드는 채점기의 검사4가 5번 이동 루프 중 4번째까지만 검사한다는 사실(main.cpp 검사 후 이동 구조)을 이용해, 마지막 5번째 위치는 range에 반영하지 않아 불필요한 반경 증가를 막는다.
scanUE() 1회: 거리 행렬 구축이 10,000 × 150 = 1.5×10⁶, UE별 countingSort가 10,000 × 150 = 1.5×10⁶, prior 계산 10,000 × 10 = 10⁵, ids counting sort O(32768 + 10,000), 그리디 배정이 후보 탐색 평균 짧음이라 ~10,000 × O(작은 상수). sub-task당 약 3×10⁶ 연산, 10 sub-task × 10 TC = 100회 호출이므로 총 ~3×10⁸ — O2 최적화에서 1초대로 충분히 빠르다.
방향 있는 UE는 점수의 숨은 변수다. sub-task 1에서는 UE의 이동 방향을 알 수 없으므로, 풀이는 안전하게 range[aid] = max(range[aid], d + 4) — 모든 방향으로 4칸까지 움직일 수 있다고 가정 — 한다. 이 +4 여유는 점수를 약간 부풀리지만, 검사4 위반(PENALTY 10억)을 피하기 위한 필수 보험이다.
sub-task 2부터는 더 정밀해진다. 같은 UE가 sub-task 사이에 어떻게 움직였는지를 관찰해 방향을 역추론할 수 있기 때문이다.
if (subcnt == 2) { // sub-task 2: 방향 찾기 for (i = 0; i < ULM; ++i) { if (ue[i].y == UE_list[i].y && ue[i].x == UE_list[i].x) { dir[i] = 4; // 좌표 불변 → 정지 UE (방향 4) continue; } if (ue[i] - UE_list[i] == 5) { // 정확히 5칸 이동 → 반전 없었음 if (ue[i].y < UE_list[i].y) dir[i] = 0; // 아래로 else if (ue[i].x < UE_list[i].x) dir[i] = 1; // 오른쪽 else if (ue[i].y > UE_list[i].y) dir[i] = 2; // 위로 else if (ue[i].x > UE_list[i].x) dir[i] = 3; // 왼쪽 } else { // 5칸 미만 → 도중 경계에서 방향 반전됨 if (ue[i].y != UE_list[i].y) { if (ue[i].y < 5) dir[i] = 0; // 상단 경계 근처 → 아래로 향함 else if (ue[i].y > 94) dir[i] = 2; // 하단 경계 근처 → 위로 향함 } else if (ue[i].x != UE_list[i].x) { if (ue[i].x < 5) dir[i] = 1; else if (ue[i].x > 94) dir[i] = 3; } } }}
<5 또는 >94)에 있다는 것은 그 경계에서 튕겨 나온 직후라는 강한 단서다. 이 추론이 한 번 끝나면 dir[]는 이후 모든 sub-task에서 재사용된다 — UE의 이동 패턴은 불변이기 때문이다.
if (subcnt < 3) ue[i] = UE_list[i]; — sub-task 1과 2에서만 현재 좌표를 ue[]에 백업한다. sub-task 1의 백업은 sub-task 2에서 "이전 위치 vs 현재 위치"를 비교해 방향을 추론하기 위한 것이고, sub-task 2의 백업으로 ue[]가 sub-task 2 시점의 좌표로 고정된다. sub-task 3 이후로는 백업하지 않고, 대신 ue[]를 시작점으로 dir[] 방향으로 5스텝씩 전진시켜 매 sub-task의 실제 좌표를 예측한다. UE 이동이 결정론적이므로 관측 없이 시뮬레이션만으로 정확하다.
| 전략 | 완전성 | 점수 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 입력 순서대로 그리디 | 보장 | 불안정 | 쉬움 | 외진 UE가 우연히 늦게 처리되면 반경 폭발 — 제곱합에서 치명적 |
| 1순위 거리만 정렬 | 보장 | 중간 | 쉬움 | 국소적으로 운 좋은 UE를 과소평가, 주변 밀도를 못 봄 |
| 헝가리안 / 최소비용흐름 | 보장 | 이론 최적 | 불가 | 10,000×150 용량흐름은 시간 안에 못 풂 — sub-task당 100회 호출 |
| prior(거리²합) 내림차순 그리디 | 보장 | CUT 통과 | 중간 | 외진 UE 우선 + counting sort O(n) + 5스텝 이동 보정 |
표가 드러내는 구조는 명확하다. 완전성(Theorem 1)은 그리디 계열이면 비둘기집 원리로 거의 공짜다. 진짜 경쟁은 제곱합 점수에서 벌어지며, 승부처는 "외진 UE가 큰 반경에 묶이는 사고"를 얼마나 막느냐다. 입력 순서 그리디는 이 사고를 운에 맡기고, 1순위 거리 정렬은 주변 밀도를 못 본다. 최소비용흐름은 이론적 최적을 주지만 sub-task당 100회 호출되는 시간 제약 안에서는 불가능하다. prior 내림차순 그리디는 — Theorem 2가 보장하듯 — 인접 교환으로 더 개선할 수 없는, 시간 제약 안의 현실적 최선이다.
<<8 후 양수여야 하므로 거리 최댓값 198에서 (198<<8)|149 ≈ 50,837 — int 범위 안. id가 256 이상인 문제로 이식하면 비트폭을 늘려야 한다.
prior 최댓값은 거리² × 10 ≈ 198²·10 = 392,040인데 버킷 CLM=32768은 그보다 작다. 실제 prior는 가까운 10개 거리의 합이라 훨씬 작지만, 데이터에 따라 32768을 넘으면 배열 범위를 벗어난다 — seed=5 데이터에서 검증된 한계다.
+4 보수적 여유를 쓴다. 만약 sub-task 1에서도 5스텝 시뮬을 하려 하면 방향이 0(미초기화)이라 한 방향으로만 5칸 — 실제 정지 UE도 잘못 이동시켜 반경을 부풀린다.
k < 4 가드가 이걸 정확히 반영한다. k < 5로 잘못 쓰면 마지막 위치까지 range에 넣어 점수가 손해다.
dir ^ 2로 처리하는데, 방향 인덱스 매핑(0=상,1=우,2=하,3=좌)이 정확히 XOR 2로 반대가 되도록 설계돼야 한다. 매핑을 한 글자라도 틀리면 반전이 직각 회전이 되어 시뮬레이션이 어긋난다.
이 풀이가 "통과한다"는 주장의 근거는 추측이 아니라 채점기 출력이다. main.cpp는 seed=5 고정으로 10개 TC를 돌리고, 각 TC는 10개 sub-task의 Σ range²를 누산한다. 검사1~4 중 하나라도 실패하면 즉시 PENALTY 10억을 찍는다.
g++ -O2로 main.cpp + user.cpp를 함께 컴파일하면 채점기가 seed=5 · 10 TC를 돌려 SCORE와 판정을 출력한다. SCORE가 CUT 2,569,112 이하이면 PASS다. 채점기가 검사1(range ≤ 200), 검사2(모든 UE 배정), 검사3(용량 ≤ 100), 검사4(이동 후 커버리지)를 모두 직접 검증하므로, PASS 판정은 곧 §2의 정당성 증명이 데이터 위에서 성립함을 뜻한다.