ATTACK — 2601 TV화질최적화 공략 우선순위

베이스라인(user.cpp 원본): 176398 개선풀이(improved/user.cpp): 176540 (+142) 채점: cd /home/hm/prj/expert-practice && ./run.sh 2601

0. 한눈에 보는 공략 로드맵

[0~3분] 합법성 0건  →  [3~10분] PRNG 예측 궤적  →  [10~30분] KKT+그리디 정제  →  [30분+] 2-swap/SA
   power≤380 확보        offset=860 수정            베이스라인 176398         176540+

1. 합법성 0건 달성 전략 (가장 빠른 기본점수) — 0~3분

1.1 세 가지 즉사 트리거 (ANATOMY §2 참조)

1.2 최소 안전 풀이 (틀만 잡는 용도)

void process(){
  int fp[20]; double fq[20]; int fm[20];
  feature_info(fp, fq, fm);
  int val[20] = {0,};            // ← 가장 안전: 전부 0
  // power = 0 (val²=0, switch=0)
  // sat = 0 → score = 0 (하지만 FAILED는 아님)
  for(int t=0; t<1000; t++) screen_control(val);
}

→ 점수 0이지만 합법. 여기서부터 점수를 올려 나간다.

1.3 안전 마진이 있는 실용 베이스라인

power = Σ power_i · val_i²/10000 이므로, 모든 val을 동일하게 k로 두면:

k² · Σpower_i / 10000 ≤ 380
→ k ≤ sqrt(380 · 10000 / Σpower_i)

• Σpower_i ∈ [200, 1600] (20개 × 10~80)이므로 통상 k ∈ [49, 138].
• val ≤ 100이므로 k = min(100, floor(위 값))로 두면 예산 안전 + 합법 보장.

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);

→ 균등 분배로 약 수만 점 획득, 0건 합법. 이것이 시험장 1차 목표.

2. SCORE 기여도 분해 → "가장 점수 많이 좌우하는 항"

2.1 점수 분해 (실측, tc=1 기준)

총 sat      ≈ 179,834   (1000스텝 합)
총 power    ≈ 379,790   (평균 379.79/스텝, 예산 380)
총 switch   ≈ 162.55    (0.16/스텝)   ← 거의 무시 가능
─────────────────────────
score       = sat − 0.01·power ≈ 179,834 − 3,798 = 176,036

2.2 민감도 분석

결론: sat 1점이 power 100점과 맞먹는다. power를 줄이는 것보다 sat를 늘리는 것이 100배 효율적. 단, 예산 380을 한 번이라도 넘으면 −1이므로 power는 "예산 꽉 채우되 1도 초과 금지"로 다루고, 나머지 모든 노력을 sat 극대화에 쏟아야 한다.

2.3 sat의 구조

sat(val, dist) = Σ_i α_i(dist) · val_i
α_i(dist) = 0.01 · quality_i · Σ_u 1/(|median_i − dist_u| + 1)

• α_i는 val에 무관, 거리 분포에만 의존 → 거리가 주어지면 sat은 val에 선형.
• quality_i가 클수록, median_i가 user 거리 중앙에 가까울수록 α_i가 큼.
• 따라서 α_i가 큰 feature에 val을 몰아주는 것이 유리 — 그것이 power 예산과 싸우는 유일한 축.

3. 시간 버짓 배분 → SA/탐색 설계

3.1 wall-time 제약: 사실상 무제한 (ANATOMY §4)

• main.cpp에 clock()/TIME_LIMIT 없음. 유일한 시간은 스텝 카운터 gCurrentTime.
• 실기기 SW Expert 런타임의 글로벌 타임아웃(보통 3초)만 피하면 됨.
• 스텝당 연산 예산: 수십만 회 여유. KKT 이분탐색(300회 × 20 feature)은 한 스텝에 ~6000 연산 → 1000스텝에 6M 연산, 0.1초 이내.

3.2 추천 시간 배분 (실기기 3초 가정)

[0.1초] feature_info + PRNG trajectory pre-sim (1000스텝 × 800 user)
[2.5초] 메인 루프: 스텝당 KKT 이분탐색 + greedy fill + 2-swap (총 1000스텝)
[0.3초] 여유 / SA 폴란드 (스텝당 2000회 random move × 1000)
[0.1초] 출력

3.3 SA vs 좌표하강 비교

• 이 문제는 스텝 내 20차원 정수 할당이고 sat이 선형이라 좌표하강(=그리디 + 2-swap)이 SA보다 훨씬 빠르고 안정적.
• 실험 결과: KKT + greedy fill + 2-swap만으로 176540. SA 추가는 거의 효과 없었음 (국소해가 이미 전역해에 근접).
• SA는 디버깅/특이 TC 용도로만 보관.

4. 그리디 초기해 + 국선 최적화 베이스라인 (실전 코드)

4.1 핵심 알고리즘 (improved/user.cpp 채택)

For each step t = 0..999:
  1. alpha[i] = computeAlpha(i, realUd[t])    ← 거리로부터 sat 선형계수
  2. KKT 연속해: val_i = 5000·α_i / (λ·power_i)    ← λ를 예산 380에 맞게 이분탐색
  3. 정수 반올림 → val_i ∈ {0..100}
  4. 예산 초과 시 α/Δpower 비율 최악 feature부터 −1 (greedy reduce)
  5. 예산 남으면 α/Δpower 비율 최고 feature에 +1 (greedy fill)
  6. 2-swap: (a−1, b+1) 로 sat 증가 가능하면 교환 (예산 유지)
  7. 안전 trim: 마지막으로 power>380이면 다시 −1

4.2 왜 lookahead(예측)는 별 효과가 없는가?

• switch cost가 총 162점(0.16/스텝)으로 sat 대비 1000배 작음.
• 미래 거리를 예측해 α를 평균내면 오히려 현재 α의 정밀도가 떨어져 sat 손실이 발생.
• 원본 user.cpp는 이 lookahead로 176398 → lookahead를 빼고 순수 per-step KKT로 176540 (+142).

시사점: 시험장에선 lookahead 복잡도를 버리고 per-step 최적화에 집중하는 것이 더 높은 점수. PRNG 예측 코드는 버그 위험만 키운다.

4.3 PRNG 예측이 유효한 유일한 경우

• 만약 switch cost 계수가 0.01이 아니라 1.0 이상이었다면, lookahead로 val의 궤적을 평탄화하는 것이 유의미했을 것.
• 현재 문제에선 PRNG 예측 코드를 작성할 시간에 KKT λ 이분탐색 정밀도와 2-swap 반복 횟수를 늘리는 것이 더 낫다.

5. 공략 우선순위 요약 (시간 대비 효과)

실전 권장: ★★★★★ + ★★★★까지만 구현해도 상위권. PRNG 예측/SA는 시간이 남을 때만.

6. 자주 하는 실수 (Anti-pattern)

1. screen_control을 1000회 미만 호출 → verify() 실패 → −1. 루프 카운터 반드시 t < 1000.
2. power 380.0001 → float 오차로 -1. 항상 BUDGET + 1e-9 마진.
3. val을 실수로 101로 → 즉사. 반올림 후 if(val[i]>100) val[i]=100 필수.
4. PRNG offset 861 사용 (user.cpp 원본 버그) → 예측 궤적 99.6% 오염. 정확한 값은 860.
5. lookahead α 블렌딩 비율 70/30 → per-step 최적에서 벗어남. lookahead는 쓰지 말 것.
6. SA를 메인으로 → 수렴 느리고 국소해. 좌표하강이 이 문제에선 우월.