9월 2-3주차 PS 정리

최적화 이론 과목의 과제와 소개원실 프로젝트에 시달리고 있다. 이번 학기는 소개원실에 내 생각과 무관하게 바쳐질 예정이었으므로 그러려니 하는 중. 하루에 한시간씩이라도 시간 내서 알고리즘 공부도 계속하려고 하는데 뭔가 잘 안 된다.

 

Rounds

SNUPC Division 2 : 7등 (3등상).
gratus907.com/122 에 포스팅했다. 좀더 침착하게 구현하는 연습이 필요하지만 대체로 실력만큼 했다고 생각한다.

 

Codeforces Round Edu95 : Unrated

A번과 B번에서 오류가 발생해서 라운드가 언레당했다. C까지 풀고 언레된걸 알고나니까 뭔가 앞에 A에서 날려먹은 시간때문에 그러지않아도 별로 하고싶지 않았던 터라 던졌다.

 

Codeforces Round 669 (Div2) : 665th. -12 (2038)

D번에서 Segment tree로 이상한거 하다가 틀렸는데 사실 아직 잘 모른다. 업솔빙 해야 하는데..

 

Problems

BOJ 17447, SNUPC 2018 라이언 동상 구하기

난이도 : SAC P5

직사각형 안에 가중치가 부여된 점들이 있다. 직사각형의 각 변들에서 점을 하나씩 골라 이것들을 이어서 더 작은 사각형을 만드는데 (네 귀퉁이에서 삼각형을 뜯어내어 남은 부분을 다시 사각형으로 만든다고 생각하면 된다) 포함된 가중치를 최대로 하기.

좌표의 범위가 상당히 작기 때문에, $O(n^3)$ 풀이도 충분히 가능하다. 잘라내는 네 부분 (좌상, 우상, 좌하, 우하) 에서, 가로의 $i$번과 세로의 $j$번을 잇는 직선을 잘라넀을때, 잘려나가는 삼각형 안의 가중치를 $O(n^3)$ 시간에 모두 찾을 수 있다 ($O(n^2)$개의 직선, $n$개씩의 점에 대한 CCW) 이제 좌우점을 하나씩 고정하고 나면, 위쪽 변을 돌면서 최대값을 찾고, 아래쪽 변을 돌면서 최댓값을 찾을 수 있다. 좌우를 고정하는데 $O(n^2)$ 개의 좌우 점 후보가 있고 각각에 대해 위아래를 $O(n)$에 돌아보면 된다.

 

BOJ 2820, COCI 2011/2012 자동차 공장 (원제목 PLACE)

난이도 : SAC P4

euler tour technique 을 연습하기 위한 문제. Euler tour technique란, 어떤 트리를 DFS order로 탐색하면서 정점들의 sequence를 기록하면, 그 sequence에서 어떤 노드 $x$를 루트로 하는 서브트리가 연속한 구간으로 나타난다는 사실을 이용하는 것이다. 이를 이용하여, 서브트리에 대한 연산을 구간에 대한 연산으로 바꾸어 풀 수 있으며, 구간에 대한 연산은 Lazy-propagating segment tree와 같은 연산으로 할 수 있다. 그대로 구현하면 된다.

BOJ 17522, ICPC Korea Preliminary 2019, Canal

난이도 : SAC P3

작년 ICPC때 맞는 알고리즘을 짜 놓고서도 투포인터 구현을 실수해서 틀렸던 뼈아픈 문제. 
gratus907.com/58 에서 설명한 알고리즘을 그대로 구현했다. 다만 이번에는 투포인터 구현을 조금 쉽게 하기 위해 deque를 이용해서 밀었는데, 앞으로도 이런 구현 방법이 상당히 유용할 것 같다. 투포인터를 while로 돌 때마다 평균 2~3번씩 WA를 받고 있는 것 같아서..