PS 일지 (4)

마지막 수정 시각: 2023-02-05 09:35:03

오랜만에 코드포스 참가를 하고(unofficial이긴 했지만), prompt412 토요일 연습을 하고, Hello Boj 2023 대회를 치고 왔다.

Codeforces Round #843 (Div. 2)

엄청 오랜만에 코드포스 대회를 돌았다. Div2라 좀 긴장감 없이 치긴 했는데, 확실히 요새 쉬운 문제들 나오는 유형이 내가 잘 못 푸는 스타일로 바뀌었구나 싶은 기분이 들었다. 전체적인 퍼포먼스는 나쁘지 않았는데, 오히려 쉬운 AB번에서 애를 먹었다. E까지 풀고 나서 잘 시간이 되어서 F는 문제도 안 읽고 잤다. 나중에 다시 풀어봐야하나 싶긴 하다.

A. Gardener and the Capybaras

맨 첫 글자와 맨 끝 글자로 케이스워크를 할 수 있다. 첫 글자 = 끝 글자인 경우, 항상 나머지 글자들로 중간 문자열을 구성하면 답이 된다. 그렇지 않은 경우, 중간에 'a'인 위치가 있다면 그 위치를 중간 문자열로 잡고 나머지를 앞, 뒤 문자열로 잡으면 된다. 이것도 아니라면, 문자열이 항상 abbbbb..b 거나 bbbb...ba 거나 둘 중 하나인데, 어느 경우든 맨 첫글자, 맨 끝글자를 제외한 나머지로 중간 문자열을 구성하면 답이 된다.

B. Gardener and the Array

일단 \(f(a) = f(b)\)를 가정하는 경우가 존재한다고 생각해보자. 이 경우, \(a\)와 \(b\)를 모두 선택한 것을 \(x\), 거기서 아무거나 원소 하나를 제거한 \(y\)를 생각하면 \(f(x) = f(y)\)로 성립하게 된다. 이걸 확장해서 생각해보면, 위에서 이야기한 \(x\)에 배열에 속하는 다른 모든 원소를 전부 다 추가해서 선택해도 답은 똑같아진다.

즉, 어떤 원소가 포함하는 모든 비트에 대해 그 비트를 포함하는 다른 원소가 존재하는 경우 답은 yes고, 아니라면 no다. 이러한 검사는 처음 입력을 받으면서 각 비트를 포함하는 개수를 계산해두면 선형 시간에 해결할 수 있다.

C. Interesting Sequence

연속한 수들을 & 연산하는걸로는 맨 끝 비트들을 순서대로 0으로 만드는 것 밖에 할 수 없다. 따라서, \(n\)과 \(x\)의 맨 앞 비트들이 전부 일치하고, 뒤쪽 일부 영역에서 \(x\)는 전부 0인게 만족할 때만 가능하다. 또, \(n\)과 \(x\)가 일치하는 영역의 맨 끝 부분이 \(11\)로 끝나는 경우에도 불가능하다(carry 때문에 두 영역이 동시에 0이 되기 때문). 따라서, 이를 만족하는지 여부를 체크한 다음 그게 아니라면 맨 끝에서 \(1111...11\)이 될때까지 전부 &한게 답이 된다.

D. Friendly Spiders

각 수를 하나의 정점으로 생각하고, 또 각 수가 가질 수 있는 소인수들도 정점으로 생각해보자. 각 수와 그 수가 갖고 있는 소인수끼리 간선을 연결하고, 그 수가 갖고 있는 소인수들 끼리도 간선을 연결한다. 이렇게 그래프를 구성하면 문제에서 주어진 조건대로 왔다갔다하는 경우를 모델링할 수 있다. 따라서 이 그래프 위에서 BFS를 통해 두 수 사이의 최단거리를 구해주면 그게 답이 되고, 역추적은 각 간선마다 그 간선에 연관된 수의 인덱스를 같이 기록해주면 쉽게 처리할 수 있다. \(N\)의 소인수의 개수는 많아야 \(O(logN)\)개 이므로, 그래프의 간선 개수는 대략 \(O(Nlog^2N)\)개가 되어 충분히 시간 안에 동작하게 된다.

E. The Human Equation

+, - 인 수들이 연속해있으면 전부 한 덩어리로 묶고 생각해도 된다. 이 상태에서, 항상 한번의 연산에서 항상 모든 그룹의 수를 하나씩 고르는게 이득이다. 이 과정을 반복할 건데, 어느 시점에서 그룹의 크기가 0이 되면 그 그룹 좌우에 있는 그룹들이 하나로 합쳐지게 된다. 따라서 그룹 크기를 기준으로 가장 작은것부터 방문하면서 0이 될때마다 연결리스트 등의 자료구조를 이용해 그룹을 합쳐주는걸 반복하면 \(O(nlogn)\) 시간에 해결할 수 있다. 풀이보다는 구현이 좀 까다로운 문제였다.

Prompt412 Round 180

간만에 8개를 다 풀었다. 전체적으로 내가 익숙한 유형의 문제들이 나와서 비교적 쉽게 푼 것 같다.

A. BOJ 25643

\(S_i\)의 앞 \(k\)글자와 \(S_{i+1}\)의 뒤 \(k\)글자가 일치하는지(혹은 그 반대인지)를 전부 체크해주면 된다. 각 문자열마다 \(O(M^2)\) 시간이면 비교를 할 수 있고, 전체 \(N\)개 문자열이므로 \(O(NM^2)\) 시간에 문제를 해결할 수 있다.

B. BOJ 1925

삼각형 판별 공식을 이용해서 열심히 구현하면 된다. 정말 싫어하는 스타일의 문제..

C. BOJ 13270

\(DP(N)\) 을 \(N\)명이 먹을 것을 준비했을 때 배달되는 최대 치킨 수 라고 정의하자. 각각의 피보나치 수를 \(f_1, f_2, f_3, \dots \) 라고 하면, \(f_i\) 세트를 사면 \(f_{i-1}\) 마리 치킨이 오므로 각각의 \(f_i\)에 대해 \(DP(N-f_i) + f_{i-1}\) 중 제일 큰 것을 골라주면 된다. 최솟값은 반대로 가장 작은 것. 검사해야하는 피보나치 수 개수가 그렇게 많지 않아(많아야 2~30개) 충분히 빠르게 동작한다.

D. BOJ 24524

\(T_i\)번 문자를 고르려면 \(T_1 \dots T_{i-1}\)번 문자까지 모든 문자를 골라야만 한다. 어떤 \(S\)의 어떤 \(i\)번 문자를 보는 시점에서, \(cnt_k\) 를 \(T_1 \dots T_k\)까지 전부 고른 경우의 수 라고 정의하자. 이렇게 하면 \(S_i\)번 문자를 골랐을 때 \(cnt_k\) 배열을 바로 갱신해줄 수 있으므로 전체 시간복잡도 \(O(N)\)에 문제를 풀 수 있다.

E. BOJ 23083

그림에 있는 걸 잘 보고 각 위치에서 다음 칸으로 갈 수 있는 \(dx, dy\) 배열을 만든 후 이 배열을 이용해서 DP를 풀면 된다.

F. BOJ 1242

현재 \(N\)명의 사람이 있고, 내가 \(M\)번 순서고, 마지막으로 죽은 사람이 \(x\)번이라고 하자. 항상 이 정의를 유지하면서 사람을 한명씩 제거해나간다는 느낌으로 접근한다.

\(x\)번 사람이 마지막으로 죽었으므로, 그 다음 죽는 사람은 \(x+K\)번 사람이다(맨 끝과 맨 처음이 연결되어있다고 치고). 만약 \(x+K\)가 \(M\)과 같다면, 내가 이번에 죽을 차례다.

\(x+K\)가 \(M\)보다 크다면, 나보다 뒤에 있는 사람이 죽으므로 \(N\)은 \(1\)감소하고 내 위치는 그대로 \(M\)번째가 된다.

\(x+K\)가 \(M\)보다 작다면, 나보다 앞에 있는 사람이 죽으므로 내 위치도 한칸 앞으로 당겨진다. 따라서 \(N, M\)이 모두 \(1\)씩 감소한다.

이 과정을 계속 시뮬레이션 해주면 최대 \(N\) 스텝 내에 내 차례가 도달하므로 \(O(N)\)시간에 문제를 해결할 수 있다.

G. BOJ 16726

1x2 블록을 최대한 많이 쓰는게 최선이고, 이걸 최대한 많이 쓰는 경우는 플로우로 구하는 방법이 잘 알려져 있다. 1x2 블록을 최대한 쓰고나면 나머지는 1x1 블록으로 채워주면 된다.

H. BOJ 3596

XXX를 채우는걸로 접근하면 좀 어려운 것 같다. 그것보다 한 스텝 앞에서 생각해보면, XX꼴 혹은 XOX 꼴을 만들어주면 무조건 상대가 그 다음에 이기므로 애초에 이런 형태를 만들 수 없다. 이 상태에 도달하면 그런디 수가 0인걸로 생각하자. 이러면 X를 놓을 때마다 좌우로 상태를 분할할 수 있고, 이미 X가 놓여있을 때 그 X 옆칸과 옆옆칸에는 X를 못 놓는다.

이 조건을 기반으로 생각해보자. \(DP(e, l, r)\)은 가운데 \(e\)개의 빈칸이 있고 그 빈칸의 왼쪽이 X면 \(l = 1\), 아니면 \(l=0\), \(r\)도 마찬가지로 오른쪽에 X가 있는지 여부를 기준으로 0인지 1인지 정해질 때의 게임상태에서 그런디 수가 몇인지 반환한다고 하자.

이러면 가운데 \(e\)개의 빈칸중 어딘가에 X를 놓으면 게임 상태를 독립적인 두개의 게임으로 분할할 수 있다. 이 때의 그런디수는 두 게임 상태를 해결했을 때의 그런디 수를 xor한 값과 같으므로, 모든 경우에 대해 각 그런디 수를 루프를 돌면서 구한 후 배열에서의 mex값으로 현 상태의 그런디 수를 구할 수 있다. 이걸 구해주면 그런디 수가 0이면 후공 승, 아니면 선공 승이므로 문제를 \(O(N^2logN)\) 시간에 해결할 수 있다. 유사한 유형의 게임 문제를 몇 번 풀어봐서 쉽게 접근했던 것 같다.

Hello, BOJ 2023

진짜 오랜만에 온사이트 대회에 참가했다. 그다지 잘 치진 못했지만(2solve 51등) 오프라인 대회에 간만에 참가했다는 사실 자체로 즐거웠다. C를 2시간 넘게 잡고 풀지 못하고 결국 종료됐는데(D는 문제 읽지도 않음).. 애드혹 문제를 좀 잘 풀고 싶은데 어떻게 해야 좋은지 모르겠다. 업솔빙할게 자꾸 쌓인다..

A. BOJ 27231

복잡하지만, 그냥 모든 경우의 수를 잘 구해서 brute force로 풀면 된다. 모든 자릿수가 0,1로 구성된 경우가 아니면 답은 많아야 2,30가지 내외. 모든 자릿수가 0,1로만 구성되어있으면 답이 무한히 많다.

B. BOJ 27232

연속한 \(K\)개의 수를 관리하자. 여기에 새로운 수 \(x\)가 추가되고, 기존에 있던 수중 \(x\)보다 큰 가장 작은 수를 \(a\), \(x\)보다 작은 가장 큰 수를 \(b\)라고 하자. 수 \(i\)가 있는 위치를 \(P_i\)라고 하면, 새로운 수 \(x\)가 추가되었을 때 거리값의 합은 \(abs(P_b - P_a)\)만큼 감소하고 \(abs(P_b - P_x) + abs(P_x - P_a)\) 만큼 증가한다. 기존에 있던 수가 빠질 때는 이와 반대로 동작.

이 논리를 이용하면 set을 이용해서 적절히 구현했을 때 각 수가 추가되고 제거되는 과정을 \(O(logK)\) 시간에 구현할 수 있다. 따라서 전체 시간복잡도 \(O(NlogK)\)에 문제를 풀 수 있다.