W5 · GUIDE.md

자원분배 / KKT · 2601 TV화질최적화
W5_resource_alloc/GUIDE.md

GUIDE — 2601 TV화질최적화 통합 해설집

W5 resource-alloc 레인 · 자원 분배 / 예산 제약 파라미터 튜닝 / Lagrangian KKT 채점기: /home/hm/prj/expert-practice/problems/2601_TV화질최적화/main.cpp (217줄) 베이스라인 점수(user.cpp 원본): 176398 개선풀이(improved/user.cpp): 176540 (+142) 빌드/채점: cd /home/hm/prj/expert-practice && ./run.sh 2601

목차

  1. 문제 한 줄 요약
  2. 채점기 역공학 핵심 (ANATOMY 요약)
  3. 수학적 모델과 최적해 구조
  4. 공략 알고리즘 단계별 구현
  5. 개선 풀이(improved/user.cpp) 해설
  6. 디버그 키트 사용법
  7. 시험장 30분 실전 타임라인
  8. 자주 묻는 질문 / 함정
  9. 웹 참고문헌 및 유사 문제

1. 문제 한 줄 요약

1000개의 시간 스텝 동안, 20개의 TV 화질 feature에 0~100 정수 값을 매번 할당하라. 전력 예산 380을 넘기지 않으면서 사용자 만족도의 총합을 최대화하라.

  • 결정 변수: featureValue[0..19] ∈ {0,…,100}, 매 스텝 갱신
  • 목적: Σ_t (satisfaction_t − 0.01 × power_t) 최대화
  • 제약: 매 스텝 power_t ≤ 380, 값 범위 [0,100], screen_control 정확히 1000회 호출
  • 위반 시 즉시 −1 (TC 실패)

2. 채점기 역공학 핵심

상세는 ANATOMY.md 참조. 여기선 실전에 필요한 핵심만.

2.1 SCORE 방향: 최대화

// main.cpp:121
gTotalScore += sat - powerUsed * 0.01;
  • sat(만족도)는 더하고, power는 0.01곱해서 뺀다.
  • gTotalScore가 클수록 좋다.

2.2 즉사 트리거 3가지

트리거 코드 결과
power > 380 line 113 gTotalScore=1 → 1000회 미달 → verify -1
val ∉ [0,100] line 100 즉시 gTotalScore=-1
screen_control 호출 ≠ 1000 line 179 verify() → -1

단 1회 위반으로 TC 전체가 −1. 합법성 0건이 1차 목표.

2.3 PRNG: 완전 결정론적

// main.cpp:189-191
for(int tc = 1; tc <= TC_CASE; tc++){   // TC_CASE=1
    gSeed = tc;                          // gSeed = 1
    init();
  • LCG: gSeed = gSeed*25214903917 + 11, 30비트 추출.
  • 시드 1에서 시작 → 전체 1000스텝의 spotDistance/userDistance 궤적을 100% 복제 가능.
  • init에서 860회 소비(feature 20×3 + user 800), 이후 매 스텝 (t%10==0?1:0)+800회 소비.

⭐ 원본 user.cpp의 버그: advanceSeed(shadowSeed, 861)이 잘못됨. 정확한 오프셋은 860. 861을 쓰면 예측 궤적이 800,800개 셀 중 797,990개(99.6%) 오염.

2.4 시간 제한: 사실상 무제한

  • main.cpp에 clock()/TIME_LIMIT 없음.
  • 유일한 시간은 스텝 카운터 gCurrentTime (0→999).
  • 실기기 글로벌 타임아웃(보통 3초)만 피하면 됨. 스텝당 수만 회 연산 가능.

2.5 API (내가 호출할 수 있는 것)

void feature_info(int power[], double quality[], int median[]);  // 정적 정보
void user_info(int userDistance[]);                                // 현재 거리
long long satisfaction(int featureValue[]);                        // 만족도(※ 함정: clamp 없음)
void screen_control(int featureValue[]);                           // ★ 유일한 액션

함정: 외부 satisfaction()은 거리 clamp가 없고, 실제 SCORE용 user_satisfaction()은 clamp가 있다. 자체 평가 함수에는 clamp를 넣어야 정확.

3. 수학적 모델과 최적해 구조

3.1 스텝별 최적화 문제

매 스텝 t에서 풀어야 할 문제:

최대화  sat_t(val) = Σ_i α_i(dist_t) · val_i

제약    power_t(val, prev) = Σ_i [ power_i · val_i²/10000 + 0.01·|val_i − prev_i| ] ≤ 380
        0 ≤ val_i ≤ 100, val_i ∈ ℤ

여기서 α_i(dist) = 0.01 · quality_i · Σ_u 1/(|median_i − dist_u| + 1) (거리가 주어지면 상수).

3.2 왜 이 문제는 'water-filling'인가

  • sat은 val에 선형, power는 val에 이차.
  • 이는 정보이론의 고전 문제 water-filling(Boyd & Vandenberghe Convex Optimization Example 5.2)과 동일 구조.
  • 연속 완화 해(KKT 조건):
val_i = 5000 · α_i / (λ · power_i)

여기서 λ는 Lagrange 승수. Σ power_i val_i²/10000 = 380이 되도록 λ를 이분 탐색. - α_i가 크고 power_i가 작을수록 val_i가 크다 → '물이 낮은 곳(효율 좋은 채널)으로 찬다'.

3.3 정수화 손실과 보정

KKT 연속해를 반올림하면 정수 val이 되지만: 1. 예산이 380을 초과할 수 있음 → α/Δpower 비율 최악 feature부터 −1 (greedy reduce) 2. 예산이 남을 수 있음 → α/Δpower 비율 최고 feature에 +1 (greedy fill) 3. 같은 power로 더 큰 sat을 얻는 자리 교환 → 2-swap

3.4 시간 결합(switching cost)의 영향

  • 0.01·|val_i − prev_i|가 인접 스텝을 결합.
  • 실측: switch cost 총합 ≈ 162 / 1000스텝 = 0.16/스텝.
  • sat 대비 1000배 작음 → 사실상 독립 per-step 최적화로 전역 최적에 근접.
  • 따라서 복잡한 lookahead/MPC는 불필요 (오히려 해침, ATTACK §4.2).

4. 공략 알고리즘 단계별 구현

4.1 1단계: 합법성 확보 (val=0 또는 균등 k)

void process(){
  int fp[20]; double fq[20]; int fm[20];
  feature_info(fp, fq, fm);
  int sumP = 0; for(int i=0;i<20;i++) sumP += fp[i];
  int k = (int)sqrt(380.0*10000.0/sumP);
  if(k>100) k=100; if(k<0) k=0;
  int val[20]; for(int i=0;i<20;i++) val[i]=k;
  for(int t=0; t<1000; t++) screen_control(val);
}

→ 균등 분배. 수만 점 획득 + 합법. 시험장 3분 컷.

4.2 2단계: per-step KKT λ 이분 탐색

// 매 스텝:
double alpha[20]; for(int i=0;i<20;i++) alpha[i] = computeAlpha(i, userDist);
int val[20]; for(int i=0;i<20;i++) val[i]=100;
if(totalPower(val,prev) <= 380.0) goto submit;   // 예산 남으면 전부 100

// λ 이분 탐색
double lo=1e-15, hi=1e3;
for(int it=0; it<300; it++){
  double mid = (lo+hi)*0.5;
  for(int i=0;i<20;i++){
    double v = 5000.0*alpha[i]/(mid*fp[i]);
    val[i] = (int)(min(max(v,0.0),100.0) + 0.5);
  }
  if(totalPower(val,prev) > 380.0) lo=mid; else hi=mid;
}
// hi(예산 이하 쪽)로 최종 val
for(int i=0;i<20;i++){
  double v = 5000.0*alpha[i]/(hi*fp[i]);
  val[i] = (int)(min(max(v,0.0),100.0) + 0.5);
}
submit:
screen_control(val);
for(int i=0;i<20;i++) prev[i]=val[i];

→ ~170,000점. 가장 큰 도약.

4.3 3단계: greedy reduce + greedy fill (예산 정밀 사용)

// 예산 초과 시: α/Δpower 최악부터 -1
while(totalPower(val,prev) > 380.0+1e-9){
  int bi=-1; double br=1e18;
  for(int i=0;i<20;i++){
    if(val[i]<=0) continue;
    double dP = powerDelta(val,prev,i,-1);   // -1 했을 때 power 변화
    double dS = -alpha[i];                    // sat 변화
    double r = dS/dP;                          // 비효율(작을수록 먼저 깎음)
    if(r<br){ br=r; bi=i; }
  }
  if(bi<0) break;
  val[bi]--;
}
// 예산 남으면: α/Δpower 최고부터 +1
bool prog=true;
while(prog){
  prog=false;
  int bi=-1; double br=-1;
  for(int i=0;i<20;i++){
    if(val[i]>=100) continue;
    double dP = powerDelta(val,prev,i,+1);
    if(dP<=1e-15) continue;
    double r = alpha[i]/dP;
    if(r>br){ br=r; bi=i; }
  }
  if(bi>=0){
    val[bi]++;
    if(totalPower(val,prev) > 380.0+1e-9){ val[bi]--; break; }
    prog=true;
  }
}

→ ~176,000점.

// (a-1, b+1) 또는 (a+1, b-1)로 sat 증가 가능하면 교환
bool improved=true;
while(improved){
  improved=false;
  for(int a=0;a<20 && !improved;a++){
    for(int b=0;b<20;b++){
      if(a==b||val[a]<=0||val[b]>=100) continue;
      double dP = powerDelta(val,prev,a,-1)+powerDelta(val,prev,b,+1);
      double dS = -alpha[a]+alpha[b];
      if(dS>1e-12 && totalPower(val,prev)+dP<=380.0+1e-9){
        val[a]--; val[b]++; improved=true; break;
      }
    }
  }
}

→ 176,540점 (최종).

5. 개선 풀이(improved/user.cpp) 해설

파일: improved/user.cpp

5.1 베이스라인 대비 변경점

항목 원본 user.cpp improved 효과
PRNG offset advanceSeed(861) 860 (또는 미사용) 예측 궤적 정확화
lookahead 블렌딩 70% cur + 30% future 제거 (per-step만) +142점
swap 로직 조건부 양방향(a-1,b+1 / a+1,b-1) +수 점
안전 마진 없음 BUDGET+1e-9 float 위험 제거

5.2 핵심 통찰

lookahead가 오히려 점수를 깎는다. switch cost가 sat 대비 1000배 작아, 미래 α를 섞으면 현재 α의 정밀도만 떨어뜨린다. 원본의 PRNG 예측 1000줄은 사실상 무의미. per-step KKT + greedy + 2-swap이 이 문제의 정답이다.

5.3 빌드 및 검증

cd /home/hm/expert_research/W5_resource_alloc
DIR=/tmp/verify_2601; mkdir -p $DIR
cp /home/hm/prj/expert-practice/problems/2601_TV화질최적화/main.cpp $DIR/main.cpp
cp improved/user.cpp $DIR/user.cpp
g++ -O2 -w -std=c++17 -o $DIR/run $DIR/main.cpp $DIR/user.cpp && $DIR/run
# 예상 출력: TC 1: Score = 176540

6. 디버그 키트 사용법

파일: debug_snippet.cpp · 해설: DEBUG_KIT.md

6.1 user.cpp에 통합 (3줄)

#include "debug_snippet.cpp"   // 상단
// ...
void process(){
  dbg_init();
  feature_info(fp,fq,fm);
  user_info(ud0);
  dbg_input_stats(fp,fq,fm,ud0);     // 1회: 입력 통계
  // ...
  for(int t=0;t<1000;t++){
    // val 계산 ...
    dbg_step(t, val, prev, alpha, powerOf(val,prev));  // 매 스텝
    screen_control(val);
  }
  dbg_summary(/*finalScore*/);       // 루프 후: SCORE 분해
}

6.2 출력 예시 (실측)

=== INPUT STATS ===
Features: 20, Users: 800
power: sum=894 min=12 max=80
quality: sum=29.63 min=0.10 max=2.37
  [HINT] quality 편차 큼 → 소수 feature 집중 효과적

[t=   0] power=379.99/380 (100.00%) sat=104.437 switch=12.540
[t= 700] power=380.00/380 (100.00%) sat=322.540 switch=0.070

=== SCORE BREAKDOWN ===
Sum Satisfaction: 180340.24 (avg 180.34/step)
Sum Power       : 379989.47 (avg 379.99/step)
  └ switch cost : 180.46
Power Slack     : 10.53 total (0.01/step)

=== CONSTRAINT CHECK ===
screen_control calls: 1000/1000 OK
power>380 violations: 0 OK
out-of-range val    : 0 OK

=== DIAGNOSTIC HINTS ===
  [HINT] local-search + < 10 → 이미 최적 근처

6.3 의사결정표

관찰 다음 액션
Power Slack > 50 greedy fill 패스 ↑, λ 정밀도 ↑
Power Slack < 1 안전 마진 0.5 추가
OVERBUDGET > 0 λ upper ↑, trim 보수화
switch > 1000 val 평활화 / lookahead(윈도 3)
local-search + < 10 SA 또는 다른 초기 λ

7. 시험장 30분 실전 타임라인

[0:00~0:03] main.cpp 읽기 → SCORE 방향, power 380 제약, PRNG 결정론적 파악
[0:03~0:06] 합법성 확보 (val=균등 k) → 수만 점 기본 보장
[0:06~0:15] per-step KKT λ 이분탐색 구현 → ~170,000점
[0:15~0:22] greedy reduce + greedy fill 추가 → ~176,000점
[0:22~0:28] 2-swap local search → ~176,540점
[0:28~0:30] 안전 마진 점검 + dbg_summary() 1회 출력 → 제출

시간이 남으면 (30분+): - SA 폴란드 (스텝당 2000회 random ±1 move, 전부 sat↑이면 accept) - 3-swap, 4-swap 확장 - 여러 초기 λ에서 시작해 최적 선택 - 단, lookahead/PRNG 예측은 이 문제에서 역효과 → 시도하지 말 것

8. 자주 묻는 질문 / 함정

Q1. 왜 power가 380.0001만 넘어도 -1인가? A. main.cpp:113의 powerUsed > POWER_BUDGET가 단정문이기 때문. float 오차라도 즉사. 반드시 BUDGET+1e-9 마진.

Q2. screen_control을 999번만 호출하면? A. verify()(line 179)가 gCurrentTime != 1000 체크 → -1. 루프는 t < 1000로 정확히.

Q3. lookahead가 왜 점수를 깎나요? A. switch cost(0.16/스텝)가 sat(180/스텝)의 1/1000. 미래 α를 블렌딩하면 현재 α의 정밀도만 떨어져 per-step 최적에서 벗어남. 실측: lookahead 제거 시 +142점.

Q4. PRNG를 예측해야 하나요? A. 이 문제에선 아니오. switch cost가 작아 예측이 도움 안 됨. 단, 정확한 오프셋은 860이고 원본 user.cpp의 861은 버그.

Q5. val_i가 100을 넘으면? A. line 100에서 즉시 -1. KKT 직후 반드시 if(val[i]>100) val[i]=100.

Q6. SA를 써야 하나요? A. 이 문제에선 좌표하강(KKT+greedy+2-swap)이 SA보다 우월. SA는 sat이 선형이라 국소해가 거의 전역해. 실험 결과 SA 추가 효과 < 5점.

Q7. 여러 TC에 대비하려면? A. main.cpp의 TC_CASE가 1로 고정되어 있으므로 실제는 단일 TC. 다만 시드가 바뀌면 α 분포가 달라지므로, KKT λ 범위를 넓게([1e-15, 1e3]) 잡고 greedy fill을 충분히 돌리면 강건.

9. 웹 참고문헌 및 유사 문제

9.1 이론 (Lagrangian / water-filling)

9.2 알고리즘 (greedy marginal allocation)

9.3 휴리스틱 최적화 대회 (AHC / TopCoder Marathon)

9.4 본 문제와 가장 유사한 클래식 문제

산출물 인덱스

파일 내용
ANATOMY.md 채점기 7단계 해체 (최우선)
ATTACK.md 공략 우선순위와 시간 배분
DEBUG_KIT.md 개선 힌트 출력 설계
debug_snippet.cpp 복붙 가능 디버그 함수
improved/user.cpp 개선 풀이 (176540, +142)
GUIDE.md 본 문서 (통합 해설집)