GCPC 2020 팀연습

• F : Flip Flow (10분 AC)
• A : Adolescent Architecture / K : Knightly Knowledge (45 / 85분 AC, 각 1WA)
• C : Confined Catching (67분 AC)
• I : Impressive Integers (103분 AC, 4 WA)
• D : Decorative Dominoes (142분 AC)
• G : Gravity Grid (160분 AC, 3 WA)
• B : Bookshelf Building (175분 AC, 3 WA)
• M : Mixtape Management (199분 AC)
• L : Lexicographical Lecturing (209분 AC)
• Review

멤버가 조금씩 바뀌면서 지난 3년간 UCPC, ICPC, HashCode 등을 함께해온 팀 Little Piplup으로 이번에는 다시 제가 참여하게 되었습니다.

이 팀은 2019년 저와 Coffeetea, DHDroid로 시작해서 PS 공부도 같이 하고, 많은 대회를 뛰면서 나름 행복 PS 해온 팀입니다. 2020년에는 Hashcode를 기점으로 저랑 그전까지 같이 연습셋을 많이 돌았던 Dlwocks31이 들어와서 4명이 되었습니다.

Hashcode는 4인팀이지만, UCPC와 ICPC는 3인 1팀입니다. 또한, ICPC의 경우 휴학생이 본선에 진출할수 없다는 규정이 있는데 이 팀은 저를 제외한 3명이 모두 휴학생 (병특 중)이라 2020 ICPC에서는 자연스럽게 제가 다른 팀을 찾아 나가고 3명이서 Army Piplup 을 구성해서 나갈 수 있었고, 2020 UCPC는 dlwocks31이 다른 팀원들이랑 출전했었습니다. 2021 UCPC는… 2명 2명을 가르고 한명씩을 더 영입했는데, 저랑 dlwocks31쪽은 어리석은 실수로 대회를 치르지 못했었습니다.

이번에는 dlwocks31이 딱히 PS에 더이상 동기가 많이 떨어졌다는 식으로 기회를 양보하기도 했고, 저는 다른 팀원들을 모으더라도 서울대에서 본선을 진출하기는 쉽지 않겠다는 판단이 들어서 행복 PS를 위해 이 팀 그대로 나가기로 했습니다. 무엇보다 같이 문제를 풀고 팀연습하는 과정을 즐길 수 있는 팀이라서 그렇기도 합니다.

ICPC는 순수하게 PS를 즐기러 나가지만 (본선 진출권도 없으므로) 그래도 이왕 모인거 팀연습이나 한두번 하자는 생각으로 GCPC 2020 셋을 돌았습니다.

GCPC는 비교적 쉬운 리저널로, 원래 5시간 셋이지만 예선만 나갈거기도 하고 저희한테 시간이 많이 없어서 3.5시간으로 잡고 돌았습니다. 풀만한 문제는 다 푼듯 합니다.

DHdroid가 ABCD, 제가 EFGHI, Coffeetea가 JKLM을 읽자고 생각했지만 커뮤니케이션 미스로 Coffeetea가 I부터 읽었고 M은 아무도 잡지 않았습니다. ㅋㅋㅋㅋ

F : Flip Flow (10분 AC)

Solve : Gratus907 Code : Gratus907
재밌게도 GCPC는 문제제목이 문제 번호를 따라갑니다.

모래시계를 뒤집으면서 남은 모래의 양을 확인하는 문제인데, 전체 시간 $t$가 작아서 그대로 시뮬레이션 할 수 있습니다. 10분에 AC.

A : Adolescent Architecture / K : Knightly Knowledge (45 / 85분 AC, 각 1WA)

각각 DHDroid / Coffeetea가 잡았습니다.

E는 딱 보기에도 어려웠고, G는 귀찮은 구현이 필요해 보였습니다. H는 너무 문제가 길어서 걸러버렸고… ‘컴퓨터가 남으면’ G를 짜겠다고 말했는데, DHdroid와 Coffeetea가 A, K가 쉽다고 주장했으므로 컴퓨터를 제가 잡고있는건 좋은 전략이 아니라고 생각했습니다.

다만 둘다 구현을 그렇게 빠르게 쳐내지는 못했습니다. 저는 두 문제 다 읽지 않았지만 각각 2000, 2500바이트의 코딩이 필요했던 것으로 보아 뇌절도 있었지만 근본적으로 구현난이도가 좀 있었던것 같습니다.

저는 양쪽 다 구현에 참여하지 않았고, 둘다 구상이 끝나고 구현만 남은 상태였기 때문에, DHDroid가 A번을 코딩할 때는 Coffeetea랑 같이 I번을, Coffeetea가 K번을 코딩하는 동안 DHDroid랑 같이 C, D를 풀 수 있었습니다. Coffeetea가 K번의 구현에서 상당히 많이 고전했기 때문에, 버그를 찾기 위해 코드를 따로 보면서 (실전에서는 코드 출력에 해당하는 선택입니다) 저한테 중간에 컴퓨터를 넘겨서 I번을 (몇번의 디버깅 끝에) 성공했습니다.

C : Confined Catching (67분 AC)

Solve : Gratus907, DHDroid
굉장히 재밌는 퍼즐틱한 문제였다고 생각합니다.
상하좌우로 움직일 수 있는 ‘말’ 이 나에게 2개, 상대에게 1개 주어집니다. $100 \times 100$ 그리드 안에서, 내가 두 말을 동시에 움직이면, 상대가 그걸 보고 도망칠 수 있습니다. 말 두 개를 잘 coordination해서, 상대 말을 ‘잡으면’ 이기는 게임입니다. 단, 600턴의 시간 제한이 있습니다.

처음에는 두 말이 이루는 직사각형을 좁히는 등 몇가지 아이디어를 생각했지만, 적절한 아이디어가 없어 고민하던 중에 제가 말 하나는 $x$좌표를 먼저 따라붙고, 말 하나는 $y$좌표를 먼저 따라붙는 아이디어를 제시했습니다. 상대가 어느쪽으로 도망치든 두 말 중 적어도 하나는 거리를 줄일 수 있음을 보장받기 때문에 (직선상의 경우가 예외가 되지만, 다음 턴에는 다시 줄일 수 있습니다) 어떻게 될 것 같았고, 잘 코너로 몰면 이길 수 있다고 생각했습니다.

DHDroid가 이걸 받고 잠깐 생각해보더니 ‘내 말 두 개와 벽이 이루는 직사각형이 줄어든다’ 는 논증으로 이 방법이 올바름을 증명했고, 제가 Coffeetea에게 잠깐 컴퓨터를 받아서 구현해서 맞았습니다.

I : Impressive Integers (103분 AC, 4 WA)

Solve : Coffeetea, Gratus907
요약하자면, 어떤 $n$이 주어졌을 때, 자연수 $a, b, c$를 골라서, 한 변의 길이가 $c$인 정삼각형을 한 변의 길이가 $a$ 와 $b$인 정삼각형들로 채우는데 정확히 $n$개를 쓰도록 할 수 있는지에 대한 문제입니다.

Coffeetea가 먼저 맨 위에 1개 또는 4개만 쓰고, 나머지를 잘 채워넣으면 될것같다는 간단하지만 문제를 바로 해결하는 아이디어를 던졌고, 제가 빈 로직을 채워넣어서 문제를 해결했습니다. $n$이 큰 짝수일 때는, 맨 위에 큰 삼각형 1개를 놓고, 아래를 한 변의 길이가 1인 삼각형 $n-1$개로 채울 수 있습니다. ($n-1$이 홀수이기 때문에, 위아래로 채워넣으면 됩니다) 반대로 $n$이 큰 홀수일 때는 맨 위에 삼각형 4개를 놓고, 아래를 한 변의 길이가 짝수인 삼각형 $n-4$개로 채워넣으면 됩니다. 이 방법으로 $n = 2, 3, 5$ 외에는 모든 경우를 해결할 수 있음을 보이면 됩니다.

구현에서 숫자를 off-by-one 에러 내서 무려 4번을 틀렸습니다. 흑흑…

D : Decorative Dominoes (142분 AC)

Solve : DHDroid, Gratus907 Code : Gratus907
재밌게 풀었습니다. 도미노에 숫자를 써넣되, 숫자가 2번 이상 중복되어서는 안 되고, 도미노칸 하나는 적어도 주변에 같은 숫자가 써있는 도미노가 하나 있어야 합니다.

문제를 이분 매칭으로 만들어 풀면 그렇게 어렵지는 않은데 구현이 상당히 귀찮습니다. DHDroid가 이분매칭의 대략적인 아이디어를 제시하고, 제가 정확히 어떻게 풀건지 좀 고민해보다가 풀었습니다. pair를 노드로 다시 인코딩한다던가 하는 구현의 잡다한 트릭들이 많이 들어간것 같습니다.

이때, 제가 구현하는 동안 DHDroid는 계속 L에 대한 아이디어를 제시하고 Coffeetea와 B를 해결했습니다. D와 L을 오가면서 저랑 DHdroid가 풀이를 둘다 거의 완성했었기 때문에, L번도 사실 시간이 충분하다면 코딩할 수 있었습니다.

G : Gravity Grid (160분 AC, 3 WA)

Solve : Gratus907 Code : Gratus907
단순 시뮬레이션 문제입니다. 중력이 작용하는 칸에서 열만 고르면서 틱택토를 하는데, $k$개를 한줄로 (가로, 세로, 대각선) 모으면 승리합니다.

가로 방향, 세로 방향, 대각선 방향의 DSU를 관리하면 어렵지 않습니다. 가로방향과 세로방향의 크기는 자명한데, 대각선방향은 대각선에 적절한 인덱스를 부여하여 $(h + w)$개의 DSU를 $\min(h, w)$개 칸을 갖도록 관리하면 잘 해볼 수 있습니다.

중간에 실수로, $h$와 $w$를 바꿔 썼는데 놀랍게도 WA가 아니라 MLE를 받았습니다. 어떤 원리로 MLE가 나는지는 파악하지 못한 채로, 벡터로 정수 900만 개를 allocate하는거 자체가 문제가 있는건가 하는 생각에 new int를 쓰는 등 삽질을 했지만 원인은 단순 실수였음을 한참 나중에 찾아냈습니다.

B : Bookshelf Building (175분 AC, 3 WA)

Solve : DHDroid, Coffeetea Code : DHDroid
읽어보지 않았지만 제가 G번 푸는 동안 둘이 잘 풀고 코딩했습니다.

M : Mixtape Management (199분 AC)

Solve : Coffeetea, Gratus907 쉬운 문제이지만 팀원간의 커뮤니케이션 실수로 아무도 읽지 않아서 버려진 문제입니다. 문제가 매우 길고 지문이 혼란스러운데, 숫자의 크기 정렬과 문자열로써의 정렬 간에 발생하는 차이에 대한 문제입니다.

이 숫자가 몇번째에 위치해야 하는지를 파악한 다음, 그 앞에는 모두 1들을, 자기 자신은 2를, 뒤에는 3들을 붙이면 됩니다. 이 말만으로는 전혀 무슨말인지 알 수가 없지만..

예제 4 2 6 1 5 7 3 을 보면, 1이 4번째이므로 1 1 1 2 3 3 3 으로 만듭니다. 이후에는, 2가 두번째이므로 11, 12, 13, 2 (이미 끝난 숫자는 건드리지 않습니다), 33, 33, 33으로 만들고… 이런식으로 1, 2, 3을 붙여서 만들면 됩니다.

예제에 대한 저희의 답은 1112 12 131312 2 33132 3313332 332 입니다. 20줄 내외의 코드로 해결가능합니다. ㅋㅋ! 199분 AC.

L : Lexicographical Lecturing (209분 AC)

Solve : DHDroid, Gratus907 Code : Gratus907 먼저 문제를 설명하자면, $n$ 개의 길이 $L$짜리 문자열이 주어지고, 이 문자열의 어떤 $[i, j]$ 구간들만을 이용하여 정렬한 결과가 원래의 정렬 결과와 같게 하는 최소 길이 $[i, j]$를 찾는 문제입니다.

Prefix에 관한 배열을 관리하는데, p[k][j] 는 현재 보는 $k$번 문자열과 그 앞 문자열의 $j$번째 문자를 비교한 결과를 저장합니다. 이때, 우리가 원하는 $[i, j]$는 이 $p$배열에서 다음과 같게 됩니다.

• $p$배열의 sub-matrix $[2, n] \times [i, j]$를 뽑았을 때, 모든 행에 leading 1이 있어야 합니다. $p$배열의 정의를 생각해보면, sub-matrix의 row가 1로 시작한다면 (첫번째 non-zero element가 1이라는 뜻) 정렬 결과가 올바르고, -1이라면 정렬 결과가 틀리며, 모든 element가 0이라면 비교가 불가능해서 판단할 수 없기 때문에 역시 올바르지 않습니다.
• 그러면, 이를 어떻게 파악할 것인지가 문제인데…
• 각 i, j마다, “내 뒤로 보이는 첫번째 +1”과 “내 뒤로 보이는 첫번째 -1” 의 위치를 저장합니다. 이제, 어떤 $[i, -]$ 구간이 올바르기 위해서는 $i$번 뒤로 나타나는 첫번째 1의 위치가 첫번째 -1보다 앞이어야 합니다.
• 이제, $i$로 시작하는 구간들 중, 적어도 모든 행이 leading 1을 갖도록 구간 끝점을 뒤로 밀어줘야 합니다.
• 각 $i$로 시작하는 구간들을 $O(n)$에 판단가능해서, $O(nL)$ 시간에 작동합니다.

이번 연습 하이라이트는, M번을 맞고 나서 시간이 11분 남아있었는데 제가 이걸 10분 만에 짜서 예제만 돌려보고 바로 내서 맞았다는 점입니다. ㅋㅋ!! 제가 구현을 못하는것은 구현이 느려서가 아니라 말렸을때 답이 없어서 그런거고, 사실 구현 속도는 그럭저럭 느리지 않은 것 같습니다.

Review

• 여전히 이 팀은 그냥 PS를 즐길 수 있게 해주는 원동력입니다. 세명의 장단점이 비교적 뚜렷하고 서로 보완적인 구성입니다.
• GCPC 셋 자체는 괜찮은데, 5시간이었다면 아마 남은 1시간 반동안 하나 잡고 풀기 쉽지 않았을 것 같습니다. 실제로 남은 문제들은 충격적인 난이도 (다이아 또는 ?) 를 가지고 있었습니다.
• 제가 구현에 묶여있는동안 두명이 J도 좀 풀어놨던데, 무슨 각도정렬 + 미친기하 + 단절점 문제였습니다. 결과적으로 솔루션은 거의 다 맞았던 것으로 기억하는데, 저는 24시간 줘도 그걸 구현할 자신이 없으므로 아마 어차피 AC를 받지는 못했을 것입니다.