head breaker (1) 구간 DP

ICPC 2019 서울 리저널 본선을 미러로 참가하고 난 후에, 미러에 같이 팀으로 참가했던 백진언(breakun)님이랑 같이 저녁을 먹으며 이런저런 이야기를 했었다. 어쩌다가 직장인 그랜드마스터(레드코더)를 목표로 같이 일요일에 모여서 꾸준히 공부하면 좋지 않을까 하는 것까지 이야기가 흘러갔고 이게 판이 커져서 head breaker(문제 풀다 뚝배기 깨지는 모임이라는 뜻)라는 모임이 되었다.

 

매주 모이면 너무 힘드니 2~3주마다 한 번씩 오프라인으로 모여서 아주 어려운 문제를 긴 시간을 들여 고민하는 종류의 모임을 하는 방향으로 정해졌고, 11월 17일 첫 모임을 가졌다. 귀찮아서 미루다보니 정리가 좀 늦어진 감이 있는데 아무튼 지금이라도 정리해둔다.

 

참가자: 남현욱(jwvg0425), 백진언(breakun), 윤창기(tamref)

일시: 2019년 11월 17일 일요일 오후 2시 ~ 7시

문제 셋:

- https://oj.uz/problem/view/OJUZ11_rail

- https://www.acmicpc.net/problem/14752

- SCPC 3회 예선 자석

- SCPC 5회 본선 기지국

- https://www.acmicpc.net/problem/17972

* BOJ 14752, 자석, 기지국 문제는 문제의 입력제한과 상관없이 O(NlogN) 풀이가 있으니 O(NlogN) 풀이로 풀어야 함

 

문제 셋은 구간 DP가 컨셉. koosaga님에게 추천받은 구간 DP 연습용 문제로 구성됐다. 나는 이 중 기지국 문제와 17972번은 못 풀고 자석까지 푸는 것으로 끝났다. 나머지 둘은 업솔빙해야 하는데.. 언제 하지.. 아래는 간단한 정리

 

OJUZ11_rail

O(N^2) DP식을 잘 세운 다음 그 DP식에서 DP(k, x) => DP(k+1,x) 가 어떻게 유도되는지(어느 부분의 값만 갱신해주면 되는지)를 잘 고민하면 O(NlogN)으로 최적화가 가능하다. 이 과정에서 세그트리 레이지가 필요한데 내가 이거 짜본지가 오래돼서 조금 애먹었다. 처음에 생각없이 로그제곱으로 짜고 나중에 최적화했다(별로 중요한 포인트는 아니었음)

BOJ 14752

원래 제한은 N = 10000이고 O(N^2) 풀이는 그렇게 어렵지 않은 문제. 이 문제도 식을 조금 변형해서 잘 정의하면 slope trick을 쓸 수 있는 문제가 된다. slope trick을 쓸 수 있는 형태로 변형하고 식을 유도하는 것 자체는 크게 어렵지 않다. slope trick을 쓰는 다른 문제랑 차이점은 딴 애들은 기울기를 +1하는데 얘는 값을 +1하는거라 관리하는 방법이 조금 다르다. 이 문제의 경우는 관리하는 값의 중간에서 삽입 삭제가 필요해서 나는 multiset을 이용했다. 아무튼 slope trick을 쓰면 O(NlogN)에 해결 가능. 약간 처리하기 짜증나는 예외케이스들이 있어서 여러번 맞왜틀을 시도한 다음에야 AC.

SCPC 3회 예선 자석

이 문제는 진짜 겨우겨우 풀었다.. 처음에 식 정의도 이상하게 했고 거기서 너무 오래 헤맸다. 처음에 어 이거 쉬운데? 했다가 내가 잘못 생각한 부분을 깨닫고 거기서 완전 멘탈이 나가버림. 한참을 정리한 끝에 결국 복잡하게 케이스를 나누고 각 케이스마다 따로따로 또 어렵고 까다로운 구현을 해서 맞추긴 했는데 너무 지저분하게 풀었다.

풀고 나서 breakun님과 이야기를 하면서 문제를 좀 더 단순화해서 풀 수 있다는 것을 깨달았다. 기지국 풀다가 중간에 이거 간단화하는 풀이 이야기하고 거기에 맞춰서 훨씬 심플한 풀이 구현해서 다시 AC 받은 후 종료.