Overview

• 휴리스틱한 문제가 많았다. 플 중위 두 개를 풀었지만 플 하위 세 문제를 못 풀었다. 그중 두 문제는 내가 쉽게 풀 수 있었던 문제였다. 끝까지 집중하자.
• H에서 간선이 항상 n개인 조건을 못 봤다. 문제를 잘 읽자.

Takeaway

• 이번 대회에서 새로 배운 테크닉:

  • 점들이 uniform하게 분포되어있으면 최근접 거리 upper bound가 존재한다.
  • x좌표 정렬해놓고 브루트포싱을 해도 돌 수 있다.
  • 가장 가까운 두 점 쌍은 x인접 / y인접이 아닐 수 있다.
  • 정해: (x/d, y/d, z/d) 버킷으로 나누고, 인접한 버킷의 모든 쌍을 검사하는 식으로 해보자.
  • 제자리로 돌아오는 dp 점화식의 경우, 점화식을 나누어 세워보자.
  • 마지막으로 어떤 행동을 했을 때를 기준으로 점화식 세우기.
  • 수열에서 uniform random하게 수를 골랐을 때, 누적 최댓값 증가가 일어나는 횟수는 logN.

• 내가 저지른 실수:

  • k ≤ 4까지 주어지는 문제에서 항상 k = 4라고 생각하여 분기 처리를 하지 않음
  • k = 0 (아무 연산도 하지 않았을 때의 초기 답)을 간과함
  • 최솟값이 1인줄 알았는데 0이었음.
  • 두 단계로 이루어진 dfs에서 multiset 초기화를 안 해줌.

• 다음에 비슷한 문제를 만나면 할 행동:

  • 유니폼 랜덤의 경우, 날먹할 수 있는 방법을 찾자.
  • 밋 인더 미들은 중간 조건을 잘 찾아서 set 등을 쓰자.

Problems

A - Adjusted Average

• n개의 수 중 k개를 빼서 평균이 x와 가장 가까워지도록 하기.
• 전형적인 mitm, set을 쓰자.

B - Bellevue

• 보자마자 모노톤 체인을 구했으나, 어차피 최대 각도를 구하면 그게 답이 됨을 알 수 있다.
• 어차피 답은 컨헐의 제일 가파른 경사이기 때문.

C - Crashing Competition Computer

• 상태가 돌아오는 기댓값 유형이다.

1. 셋 돌 때는 dp(i, j): 마지막으로 저장 누른 게 i번째일 때, i번째 문자부터 끝까지 타이핑하는 데까지 걸리는 시간의 기댓값으로 뒀는데, 그럼 상태 전이가 잘 안 된다
2. dp(i): i번째 문자까지 타이핑하는 데 걸리는 기대 시간이라 두자.
3. 마지막 저장버튼을 누른 시점을 기준으로 점화식을 세운다.
4. dp(i) = min ( min_j (dp(j) + t + f(i-j)), f(i))
5. 이때 f(i): i개의 문자를 저장버튼 없이 쭉 타이핑할 때 걸리는 시간 기댓값
6. f(i) = f(i-1) + 1 + p(r + f(i))
7. DP 식 세울때 '마지막으로 ~~한 시점'을 기준으로 세우는 짓을 많이 하는 것 같다

D - Dividing DNA

• 자명한 그리디 + 인터랙티브, 쫄지 말자.

E - Equalising Audio

• 그냥 구현문제

F - Failing Flagship

• 그냥 구현문제

G - Grinding Gravel

• 언젠간 업솔빙 예정

H - House Numbering

• 관찰 여러개 해서 슈웃 (unicycle, 트리 조건)
• 재귀 함수에서 multiset 초기화를 해 주자.

I - Imperfect Imperial Units

• 제한이 작아서 그래프 만들고 매 쿼리마다 그래프 탐색 해도 됨. long double을 쓰자.

J - Jagged Skyline

• 그냥그냥 랜덤 인터랙티브.
• 할 수 있는 게 많이 없으면 간단한 랜덤 풀이를 내보자.
• 최솟값(0) 잘못 써서 1틀, progressive하게 업데이트해주지 않아서 1틀

K - Kiosk Construction

• 그냥저냥 역방향 bfs

L - Lowest Latency

• x좌표 정렬 후 인접한 100개 쌍 확인 (브루트포스)
• uniform random하면 두 인접 쌍 간 최소 거리같은 걸 크게 잡을 수 있기 때문.