블로그를 너무 방치해 둔 거 같아서 최근 풀었던 문제를 모아서 올려보기로 했다. BOJ 17474 수열과 쿼리 26 Segment Tree Beats 구현하면 된다. BOJ 1763 트리 색칠 이런 유형의 문제는 Best Vertex를 고른 다음, 그 부모와 합쳐주는 방식으로 해결하는 것이 전형적이다. 그 정점을 다음에 갈 수 있다면, 무조건 그 정점으로 가는 것이 이득이기 때문에 아예 부모 정점과 합치는 것이다. 이 문제도 마찬가지로 풀릴 것 같으니, 몇 가지 변수를 추가해서 해결해 보자. $X[i]$를 그 정점을 방문하고 나서 흐르는 시간의 양이라고 하고, $B[i]$를 그 정점을 방문하고 나서 얻는 추가적인 Cost라고 두자. Exchange Argument를 사용하면 $C[i] / X[i]$가 가..
내가 치르게 되는 마지막 APIO는 코로나19의 영향으로 인해 집에서 치르게 되었다. 이틀 동안 대회를 열어 두고, 각 나라의 참가자들이 자신이 원하는 시간에 참가 버튼을 누르면 5시간 타이머가 켜지고 5시간 동안 3문제를 푸는 대회를 치르는 timeframe 방식으로 진행되었다. 대회가 끝나도 각 문제에 대한 답안 제출 시각을 확인할 수 있어서, 이걸 보면서 타임라인별로 내 생각과 문제에 대한 내용을 정리해보려고 한다. 문제는 여기서 확인할 수 있다. A. 벽 칠하기 B. 자매 도시 C. 즐거운 행로 ~43:55 대회를 시작하기 전에, 나는 다음과 같은 전략들을 세우고 지키려고 노력했다. 대회가 시작하면 모든 문제를 정독하기 구현 시간을 제외했을 때, 모든 문제를 1시간 이상 고민하기 부분점수라도 빨리..
A. Incremental House of Pancakes 대소 관계가 한 번 바뀐 후에는 양쪽에서 번갈아가며 가져가면 된다는 사실을 관찰하고 나면, 대소 관계가 언제 처음 바뀌는지, 언제 끝나는지를 각각 이분탐색해서 문제를 해결할 수 있다. 급하게 짜느라 식이 꼬여서 자꾸 Off by one 에러가 생겼다. 결국 45분이 되어서야 첫 제출을 했고, 틀렸다. 두 번의 제출을 더 한 끝에 56분쯤에 AC를 받을 수 있었다. A에서 1시간이나 사용했기 때문에 여기서 멘탈이 좀 나갔다. 이런 유형의 문제에서 자꾸 말리는 경향이 있는데, 빨리 풀지는 못해도 AC는 한 번에 받을 수 있게 노력해야겠다. B. Security Update Hidden까지 풀려면 케이스 노가다를 많이 해야 할 것 같아서 Visible..