Codeforces Round #576 (Div. 1)

https://codeforces.com/contest/1198/standings/participant/26799422#p26799422

 

A - array의 distinct value한테만 비트를 배정해야 한다는 걸 못봐서 한번, 바이너리서치하는 배열을 정렬 안해서(..) 한번 틀리고 그걸 발견 못해서 B 풀고 와서 좀 더 직관적인 좌표압축? 코드를 짜서 맞았다.

 

B - 온라인으로 풀면 레이지 세그를 써서 2번 쿼리를 레이지하게 뿌리면 된다. Div1B에겐 오버킬이였고, 정해는 오프라인으로 1번 쿼리들마다 앞으로 올 2번 쿼리의 값의 최댓값으로 바꿔쓰는 식. 너무 복잡하게 생각한 듯 하다. 나중의 2번 쿼리가 앞에 있는 어떠한 1번 쿼리든지 덮어씌울 수 있는 포텐셜이 있다! 식으로 접근하면 이런 풀이에 도달할 수 있는듯 하다.

 

C - 대회 중엔 열심히 노드에 색칠을 했다. 그러나 이분그래프도 아닌데 뭐가 나올리가.. 왠지 문제 제한에서부터 한 방식이 안 되면 다른 건 될 거 같은 느낌이 들었으나, 노드 개수와 에지 개수가 같아도 다른 방식으로 처리해야 하는 케이스를 계속 찾아서 너무 혼란스러웠다. 결국 대회 끝까지 별다른 아이디어를 내지 못했다.

 

정해는 대회에서 해멘 게 무색할 만큼 매우 매우 깔끔하다. 구사과님의 코드를 참고했다. https://codeforces.com/contest/1198/submission/57999919

우선 그리디하게 에지를 고른다. n개 이상 골랐으면 성공이고, 그러지 못했으면 골라진 에지 옆에 있지 않은 노드들을 고르면 된다. 이 노드들은 그리디 과정상 에지로 연결되어 있을 수 없다!

어.. 모르겠다. 우선 "한 방법이 안 되면 뭔가 다른 방법이 당연히 되는 방식이 있을 것이다" 생각은 들었었는데, 왜 저 풀이에 도달할 수 없었을까? 여기서도 너무 복잡하게 생각한 게 아닌가 싶다. 에지를 고를 때 그래프에서 dfs비스무리 한 걸 해서 최대한 많이 골라내는 걸 대회 중에 생각했었는데, 사실 그리디로, 그냥 에지를 랜덤한 순서로 보면서 넣을 수 있을 때 넣어도 충분했던 거니까. 아니면 생각을 좀 바꿔서, 에지를 하나 고르는 것을 노드 두개를 고르는 것이라고 생각하고, 에지 n개를 고르면 노드 n개가 남는다! 이런 걸 관찰했으면 좀 더 정해에 가깝지 않았을까?

 

 

D - dp[x1][y1][x2][y2] = ...

저기까진 감을 잡았는데 점화식을 어떻게 세워야할지 애를 먹었다. 아직 업솔빙을 안해서 뭐라 확신하면서 말하긴 힘든데 수직으로 (x2-x1)번, 수평으로 (y2-y1)번 자르면 되는 것 같다. 음.. 뭔가 계속 더 잘게 쪼개거나 충분히 general하지 않게 쪼개는 식으로 생각을 했는데, dp에 대한 이해가 부족한 듯 하다.