7월 24일 PS 일기

팀연습을 했습니다.

팀원: 나 (gs20036), ComPhyPark, annyeong1

UCPC 팀 그대로 도는 첫 팀연습이었습니다. 셋은 2024-2025 NEERC를 돌았습니다.

시작 (0분~50분)

제가 ABCD를, ComPhyPark이 EFGH를, annyeong1이 IJKLM을 잡았습니다.

 

A번은 꽤나 자명해 보여서 짰다가 1틀을 했습니다. 풀이는 굳이 안 적도록 하겠습니다. 제 체감 난이도는 S5~S4였습니다.

 

3분에 A번 AC를 받았고, 그 사이 ComPhyPark이 F번 풀이를 내고 6분에 F번 AC를 받았습니다.

그 사이 annyeong1이 J번 풀이를 내고 10분에 J번 AC를 받았습니다.

 

저는 B를 잡고 보다가 유기했습니다. solved.ac 기준 D1이었어서 결과론적으로 옳은 판단이었습니다.

그 사이 annyeong1이 28분에 I번 AC를 받았습니다.

ComPhyPark이 G번 풀이를 내고 넘겨받아서 코드를 짜기 시작했습니다.

 

저는 C,D도 유기하고 솔브가 나온 다른 문제들 중 H번을 잡았습니다.

ComPhyPark이 G번에 2틀을 받고 코드를 ^프린트^ 해서 디버깅하기 시작했습니다.

annyeong1이 K번 풀이를 내서 짜기 시작했습니다.

H번 풀이를 내고 큐에 넣었습니다. 현재 큐: K - G - H

원판의 처음 위치를 a[i], 나중 위치를 b[i]라 합시다.

n을 a[n] != b[n]인 최대의 n으로 설정합시다.

 

x[i]를 "i개의 원판을 1번 -> 2번 기둥으로 옮기는 데 걸리는 최소 이동 횟수",

y[i]를 "i개의 원판을 1번 -> 3번 기둥으로 옮기는 데 걸리는 최소 이동 횟수"

라 정의하면 x[i]와 y[i]에 관한 점화식을 세울 수 있습니다. O(n)에 x[n], y[n]까지 구할 수 있습니다.

 

f(i,j)를 "맨 위부터 i개의 원판을 초기 상태에서 모두 j번 기둥으로 옮기는 최소 이동 횟수",

g(i,j)를 "맨 위부터 i개의 원판을 j번 기둥에서 모두 나중 상태로 옮기는 최소 이동 횟수"

라 정의합니다. f(i,j), g(i,j)에 대한 점화식은 x[i], y[i]를 이용하면 쉽게 세울 수 있습니다.

 

이제 n-1개의 원판을 한 그룹으로 두고, 맨 밑에 원판을 한 그룹으로 둬서 f(n-1,j), g(n-1,j)를 적당히 버무려 주면 답이 나옵니다.

 

체감 난이도는 G3이었습니다. 변형 하노이 탑 문제를 예전에 파본 적이 있었어서 이런 류의 점화식을 유도하는 게 자명했습니다. 기여할 때에는 통상적으로 저 점화식을 유도하는 난이도를 고려해서 P4를 줬던 걸로 기억합니다.

초반 (50분~2:00)

annyeong1이 51분에 K번 AC를 받았습니다.

ComPhyPark이 52분에 G번 AC를 받았습니다. solved.ac 기준 P1이었는데 자칭 플래조무사 답게 순식간에 풀어낸 모습입니다.

제가 1:01분에 H번 AC를 받았습니다. 30~40위권에서 순식간에 한 자릿수로 순위가 올라갔습니다.

 

annyeong1이 M번을 잡고, 제가 L번을 잡고, ComPhyPark이 D번을 잡았습니다.

제가 D번을 잡았을 때 매개변수 탐색을 박고 미지수 n개짜리 연립방정식을 풀면 된다는 아이디어를 냈는데 그 아이디어를 확장시킨 모양입니다.

 

annyeong1이 1:44분에 M번 AC를 받았습니다. 그리고 C번을 잡았습니다.

ComPhyPark은 "-2진법"이라는 해괴한 개념으로 D번을 풀고 있었고, 저는 L번 풀이를 식정리 하고 있었습니다.

 

이 시점에 5~7등이었습니다.

중반 (2:00~3:00)

L번 풀이가 나와서 구현을 먼저 시작했습니다.

180줄을 짜고 나서 풀이가 틀렸단 사실을 깨달았습니다.

 

ComPhyPark이 2:36에 D번 AC를 받았습니다. D번 코드를 짜면서 C번 발상을 도와주고 제 L번 풀이를 개선시켜줬습니다. 이 정도 해야 IGM을 가나 봅니다.

일단 C번 풀이가 미완성이어서 제가 L번 풀이를 다시 가다듬고 구현을 시작했습니다.

 

이 시점에 10등플마단을 유지하고 있었습니다.

후반 (3:00~4:10)

L번 구현에서 막히는 점이 있어서 일단 ComPhyPark에게 C번 구현을 주고 L번 구현을 메모장에다 정리하고 있었습니다.

ComPhyPark이 C번 구현을 하는 동시에 제 L번 구현 말린 부분을 풀어줬습니다.

 

ComPhyPark이 3:47에 C번 AC를 받았습니다.

저는 수많은 찐빠를 낸 후에 4:08에 L번 AC를 받았습니다.

B번과 E번이 남았는데 둘 다 유의미한 발상이 없었던지라 L번 AC를 받고 연습을 끝냈습니다.

 

편의상 주어지는 문자열 w의 길이를 l이라 합시다.

"j번째 문자열"을 다음과 같이 정의합시다.

길이가 l+1인 이진 문자열 중 사전순으로 정렬했을 때 j번째에 나오는 것 (0-index)

 

dp[i][j][k]를 다음과 같이 정의합시다.

dp 테이블에는 아래 조건을 만족하는 이진 문자열의 개수를 저장할 겁니다.

i: 문자열의 길이입니다. 정확히는 (문자열의 길이-l)입니다.

j: j번째 문자열로 끝납니다.

k: 문자열이 포함하는 길이 l+1짜리 이진 문자열들의 인덱스를 비트마스킹 해준 값입니다.

dp 테이블을 채우는 시간을 계산해 보면 O(n * 2^l * (2^2^(l+1))) 정도가 나옵니다. 지금까지 봤던 시복 중에 가장 특이했습니다.

 

a[i][k] = dp[i][0][k] + ... + dp[i][2^(l+1)-1][k]로 정의합시다.

우리가 구하고 싶은 것은 a[n][i] * a[m][j]의 합인데, 이 때 i&j = 0, i와 j는 각각 w를 포함하는 길이가 l+1인 이진 문자열을 최소 1개 담고 있어야 합니다. ComPhyPark이 누적 합을 변형해서 위 작업을 O(2^l * 2^2^(l+1)) 정도에 할 수 있게 해 줬습니다. (b[n][k]를 k & i = i인 모든 i에 대해 a[n][i]의 합으로 정의하는 방법입니다.)

 

코너 케이스로 n = l or m = l인 경우가 있습니다. 처리하는 건 어렵지 않았습니다.

 

체감 난이도는 D5였습니다. 여담으로 코너 케이스를 안 고려했으면 TC 5에서 틀리고, mod를 처리하는걸 까먹으면 TC 25에서 틀립니다. 제가 그렇게 2틀을 먹었습니다.

결론

 

친추되어 있는 사람들 (사실 지금까지 셋을 돈 모든 한국팀) 사이에서 1등을 했습니다. 저와 annyeong1은 1인분씩 했고 ComPhyPark이 P1 4개를 대회 시간에 푸는 캐리를 했습니다.

 

개인적으로는 만족스러웠던 셋이었습니다. 우선 제가 목표로 하는 "플래 다 풀고 낮다이아 건드려보기"를 달성했습니다. 셋에 낮다이아가 없어서 플래 다 푼것에 만족합니다. 팀적으로도 서로 말린 부분 있으면 (특히 제 말린 부분을)풀어주고 컴 잡는 시간도 큐가 안 밀리게끔 잘 분배가 됐습니다. 제 개인역량이 UCPC 본선날 잘 터져주기만 하면 될 것 같습니다.

 

셋의 퀄리티도 좋았다고 평가합니다. 제가 잡은 문제들 한정으로는 구현이 ICPC 셋들 중 쉬운 편에 속했습니다. 가끔씩 보이는 "구현 복잡하게 꼬아놓고 난이도 올리기" 같은 문제가 없어 보입니다. 난이도 밸런스도 제 기준에는 challenging하면서 넘사벽은 아닌 난이도의 문제들이 많아서 좋았습니다.

 

UCPC 본선 리뷰로 돌아오겠습니다