PS 일지 (1)

마지막 수정 시각: 2022-12-25 13:15:14

적당한 난이도의 문제들을 골라서 풀었다.

BOJ 13553

\( l <= i < j <= r \) 이면서 \( abs(A_i - A_j) <= K \) 인 쌍 개수를 구하면 된다. \(K\) 값은 쿼리에 무관하게 고정.

요상하게 문제를 착각해서 단순한 sqrt decomposition으로 풀 수 있다고 생각했는데, 그렇게는 안 됐다. Mo's algorithm + 구간 수 개수를 segment tree로 관리하면 \(O(QsqrtNlogN)\) 시간에 문제를 해결할 수 있다. Mo로 풀리는게 너무 명확한데 괜히 이상하게 돌아가려고 한 것 같다. 간단하게 풀 수 있는 방법이 생각났고, 그게 돈다 + 구현이 빠르다 하면 좀 오버킬 같아도 그냥 그걸로 푸는게 좋은 거 같다.

BOJ 21759

문제를 잘못 이해하는 바람에 너무 삽질을 했다. 어떤 두 서브트리를 고를 건데, 서브 트리는 서로 겹치면 안 되고, 고른 두 서브트리의 정점 가중치 합이 최대가 되게 하고 싶다.

이 때 각 서브트리는 그 밑에 적절히 리프들을 더 붙여서 해당 서브트리의 가중치 합을 더 높일 수 있으면 무조건 걔들도 다 선택해야 한다. 이 조건을 빼먹어서 이상하게 풀었다가 한참 고생했다.

문제 자체는 적절히 필요한 값들 전처리하면 풀 수 있고 풀이 자체의 유도는 어렵지 않았는데, 처음에 삽질한 거 때문에 기존 코드에서 계속 고치면서 문제를 풀다가 너무 틀린 제출을 많이 했다. 중간에 풀이가 잘못됐다는걸 알았으면, 그냥 기존 코드를 엎고 풀이에 쓰이는 변수와 내용을 명확히 한 다음 다시 처음부터 짜는게 차라리 나은 것 같다.

BOJ 2123

많이 풀어본 그리디인데 너무 헤맸다. 오래돼서 까먹은 것 같다...

인접한 두 위치 \(i\)번과 \(i+1\)번에 대해서 위험도 값을 생각해보자. 이 둘을 서로 교환해도 나머지 위치에서는 위험도 값이 전혀 변화하지 않는다.

이 때 \(\sum_{k=i+1}^n{W_i} - S_i\) 와 \(\sum_{k=i+2}^n{W_i} - S_{i+1}\) 을 비교해보면, 둘을 교환할 경우 서로 \(W_i + S_i - (W_{i+1} + S_{i+1})\) 만큼의 값 변화가 생긴다는 것을 알 수 있다(한쪽 증가, 한쪽 감소). 즉, 가장 위험도 값이 큰 원소에 대해 그 원소보다 \(W_i + S_i\) 값이 더 큰 원소가 인접하게 오른쪽에 붙어 있다면, 이 둘을 서로 교환해주면 답이 감소하게 된다. 이 과정을 반복하다보면, 결국 \(W_i + S_i\) 값이 가장 큰 원소가 맨 앞으로 와야함을 알 수 있다.

따라서 이 방식대로 정렬해서 위험도를 구하면 문제를 해결할 수 있다.

BOJ 13555

이전에 똑같은 문제를 풀어본 적이 있어서 그거 코드를 살짝 고쳐서 제출했다(K 제한이 커서 불안해가지고 세그 -> 펜윅만 바꿈). 각각의 \(dp(k, i)\)를 \(i\)번째 위치에서 끝나면서 길이가 \(k\)인 LIS 개수라고 정의하면, \(k\)개의 세그먼트트리를 두고 이를 이용해서 \(O(NKlogN)\) 시간에 문제를 풀 수 있다.

BOJ 2825

수를 비트마스크 형태로 바꾸면 \(O(2^{20}+N)\) 시간에 문제를 풀 수 있다. 비슷한 유형을 많이 풀어봐서 좀 쉽게 풀었다.

BOJ 15713

앞-> 뒤로 안보고 뒤->앞으로 역방향으로 생각하면 세그먼트 트리를 이용해서 최적화할 수 있는 DP 식을 구할 수 있다. 이 DP식을 구현하면 맞는데, \(y=0\)에 트램펄린이 없을 때 처리를 이상하게 해놓고 이걸 눈치채지 못해서 좀 많이 헤맸다. 요즘 뭔가 이런 코너 케이스 잡는 능력이 너무 떨어졌는데 이런거 좀 더 구체적으로 잘 생각하는 연습을 해야할 것 같다.

BOJ 17403

반복해서 convex hull을 구하면 그게 답이라는 걸 대충 눈치밥으로 때려맞출 수 있다(엄밀한 증명은 잘 모르겠다). 그래서 그냥 그거 구현해서 품.

BOJ 10891

DFS Tree를 구하고 각 정점을 커버하는 back edge 개수가 항상 1개 이하인지 보면 된다. 최근에 dfs tree를 쓰는 문제를 많이 고민해봐서 좀 쉽게 풀었다.

BOJ 16976

전형적인 PBS 문제. 꼭 PBS로 안 풀어도 되지만, PBS가 구현이 편하고 익숙해서 그걸로 풀었다. 오랜만에 PBS 구현하는 거였는데 안 헤매고 한 번에 잘 짜서 만족.

BOJ 24043

XOR Basis로 푸는 문제. 이게 안 익숙해서 좀 고생했다. XOR Basis를 그냥 템플릿에 있는걸 갖다 썼는데, 이게 사전순 최소 XOR Basis를 구하는게 아니었고 이것때문에 많이 헤맴. 구현 방식이 하나만 있는게 아니라는 걸 좀 염두에 둘 필요가 있다고 느꼈다.

BOJ 24042

많이 풀어본 유형의 다익스트라 문제여서 풀이는 빨리 생각했다. 각 정점에 도착한 시간을 기준으로 주기 \(M\)을 이용해 각 간선의 가중치 값을 구할 수 있다.

근데 이상한데서 오버플로우 실수를 해서.. 이런 실수를 예전에 많이 안 했었는데 최근에 좀 많이 는 것 같아서 걱정.

BOJ 24271

풀이 방향은 빨리 잡았는데 내가 제일 까다로워하는 유형의 구현이어서 많이 애먹었다. 구간 범위 자체를 \(XOR\) 해도 잘리는 범위가 비트 단위로 나눠서 생각하면 항상 연속한 두 구간의 형태가 된다는 것을 알 수 있다. 이를 이용해서 세그먼트 트리 구현과 비슷한 식으로 처리해주면 풀 수 있다. 좀 더 쉽게 구현하는 방법이 없나 싶은 생각이 들기는 하는데..

NWERC 2020

연습한다고 생각하고 3시간 제한으로 NWERC 2020 셋을 그냥 돌았는데, 대차게 망했다. 문제 수가 너무 많아서 일단 1인 3시간 연습 셋으로 적합하지 않았던 것도 있는 것 같지만, 그냥 너무 시간 관리도 못하고 문제 파악도 잘못하고 여러가지로 총체적 난국인 기분. 3시간동안 브론즈 2개 실버 1개 플래 1개 밖에 못 풀었다.. 플래티넘 하위권 3개를 합쳐서 최소한 6개는 풀었어야했을 것 같은데..

일단

1. 난이도가 D4 인 어려운 문제를 문제 잘못 읽고 잘못 파악해서 이걸 붙잡고 1시간 가까이 날림

2. 인터랙티브 문제에서 맞는 풀이를 구해놓고도 쿼리 날리는걸 잘못하고 있었다는걸 눈치 못채서(공백을 넣어야하는데 안넣고 쿼리를 했다..) 1시간동안 못 풀고 결국 연습 시간 끝나고 발견

3. 풀이 방향성은 맞게 찾은 문제에서 잘못된 가정을 하나 세우고 그걸 눈치 못채서 또 시간 날림

으로 세가지 요인이 있었다. 이렇게 망하기도 쉽지 않겠다 싶을 정도로 말려서.. 구현이고 풀이고 다 잘 안 된다는 기분. 시간 제한을 걸어놓고 빡빡하게 푸는 연습을 좀 더 해야할 것 같다.

연습중에 푼 문제.

농 위키