Codeforces Good Bye 2025

2025년 목표가 오렌지 가기였던 게 떠올라서 연말에 부랴부랴 코포 쳤습니다. BOJ 말고 다른 하위 콘텐츠도 만들어 보고 할 겸 해서 기록합니다.

타임라인

A (00:01)

사람 엄청 많아서 m1.codeforces.com으로 도망갈 준비하고 있었는데 문제가 잘 열려서 좀 신기했습니다. (채점 큐가 안 빠질 거란 생각은 왜 안 했을까요)

A번 문제를 읽었습니다. 대충 읽어보니까 Y를 지울 수 없을 때 문자열을 한 글자로 줄일 수 있는지 묻는 거 같았습니다. 그대로 짜서 내고 맞았습니다. 코포는 Yes/No를 대소문자 신경 안쓰고 대충 짜도 맞게 해주는 체커를 지원하는 점이 좋네요.

B (00:04)

B번 문제를 읽었습니다. 왜 쉬운 문제는 늘 문자열인지 5초 정도 생각했습니다.

suuus 같은 건 가운데 u 빼고는 조건 만족을 안 하니까 못 써요. 결국 u 근처는 싹 다 sus로 씌우라는 거고, s를 최소로 추가하려면 uu...u 뭉탱이를 잡아서 usus...u 꼴로 만드는 게 좋아 보입니다. 문자열의 끝 u는 항상 s로 바뀌어야 함에 유의해 구현합시다. 그대로 짜서 내고 맞았습니다.

C (00:12)

C번 문제를 읽었습니다.

마지막에 남을 친구를 고정하고 싶어집니다. 그 친구를 고정하면, 뒤에 있는 친구들은 전부 naughty해집니다. 반면 앞에 있는 친구들은 nice할지 naughty할지 산타 마음대로 결정할 수 있게 됩니다… 1번 친구는 빼고.

절댓값의 prefix sum과 원래 값의 suffix sum을 관리하면 ${\cal O}(N)$에 문제를 해결할 수 있습니다.

D (00:29)

D번 문제를 읽었습니다. 하스 지문이였고 아는 카드여서 좀 대충 읽어도 괜찮았습니다.

공격력 = 체력임에 주목합니다. 자기보다 공격력이 강한 하수인한테 박거나 박히면 하수인이 바로 죽어버립니다. 매 공격에서 적어도 한 하수인은 죽는다는 점으로부터, 해 구성이 가능한 답의 최댓값이 절반 근처임을 알 수 있습니다.

$k = 0$인가에 따라 풀이가 분기됩니다. $k=0$인 경우에는 마지막 공격으로 쪽을 내기 위해 딜 계산이 필요하기 때문입니다. $k \neq 0$이고 해 구성이 가능한 경우에는 딜 계산을 할 필요가 없습니다. 어차피 서로 한 대 맞거나 한 대 때리고 죽을 거에요.

기본적인 원리는 공격력이 강한 애가 약한 애를 때려서 공격권을 소비하면서 약한 애 하나를 없애는 겁니다. 이때 약한 하수인이 남으면 곤란하기 때문에, 약한 하수인이 다음으로 약한 하수인을 순서대로 때리고 죽게 만들어서 개체 수를 조정해 주면 됩니다.

$k=0$인 경우는 제일 체력 큰 애를 처치하는 게 목표입니다. 가능하면 나머지는 아까 전의 개체 수 조정 방법으로 적당히 제거하면 됩니다.

E?

E번 문제를 읽었습니다. $100\,000 < 2^{17}$에 $300$이라는 대놓고 로그제곱 떠먹여주는 제한인 데 못보고 이상한 루트질이나 인터랙션 평균 10번에 $2^x$가 답인지 판정하는 방법만 고민하다 흠 문제가 이상하군 하고 넘겨버렸습니다.

F (01:20)

F번 문제를 읽었습니다. 일단 트리 DP긴 한데 그냥 계산하면 당연히 죽을 것 같이 생겼습니다.

트리를 손으로 좀 옮겨보다 보니까 서브트리 안에서 흰색 정점들이 움직이는 게 이상합니다. 생각을 해보니까 흰색 정점이 생성되거나 소멸할 수 없더라고요.

해서 흰색 정점을 기준으로 트리를 쪼개버릴 수 있습니다. 어차피 그 서브트리에서 절대 못 벗어나요. 그래서 그 안에서 아무거나 하나 골라서 하얀색으로 칠해주고, 각 서브트리의 모양 자체는 고정이라 그대로 두면 됩니다. 하얀색 정점이 한 줄로 나열되도록 서브트리를 나열한 뒤 하얀색 정점을 앞 서브트리의 아무 정점 중 하나랑 이어줍니다. 마지막 서브트리 뒤에는 다른 하얀 정점이 붙지 않음에 유의해 식을 정리하면 이쁜 식이 하나 나와요. 짜서 내고 맞았습니다.

G?

E를 진짜 모르겠어서 G를 봤습니다. 홀짝성에서 모두 0 어쩌구저쩌구 하길래 XOR을 고려했습니다.

이제는 말할 수 있다: 당시 XOR Basis 쓰는 문제를 검수 중이였습니다. 그래서 XOR근이 좀 든든해져 있는 상태였음. 굿

아무튼 그래서 고민을 해보니까, u..v에서 교차하는 현 = 이번 현을 추가할 때 새로 생기는 체인들은 2N짜리 XOR 펜윅으로 적당히 관리하면 되겠거니 했습니다.

여기서 어차피 자기로 끝나는 체인의 수가 짝수 개면, 나중에 체인을 어떻게 만들든 해당 현을 무시할 수 있다는 관찰을 해 봤습니다. 얘를 확장하면, 어떤 현으로 끝나는 체인 안에 다른 체인이 짝수 개 들어가면 그 체인은 내 알 바가 아니라는 결론이 나옵니다.

따라서 각 현으로 끝나는 체인의 개수와, 그 체인들 안에 홀수 개 들어있는 현의 집합을 알 수 있다면, 현재 홀수 개 쓰인 현의 집합을 갱신해 가면서 비었는지 판정하는 식으로 문제를 해결할 수 있었습니다.

근데 어캐함?

E (02:18, +2)

모르겠어서 E로 돌아왔습니다. 그사이에 나빼고 다 풀었길래 어디 이상한 데서 매몰됐겠거니 하고 문제를 다시 읽었습니다.

근데 다시 읽어도 모르겠던데? 흠.

그래서 이상한 휴리스틱 그리디 백만개 내고 틀렸는데, 대부분 예제를 틀려서 페널티는 별로 안 쌓았습니다. 굿

숨 돌리러 편의점 가다가 로그제곱이라는 훨씬 reasonable한 복잡도가 생각났습니다. 그 복잡도를 써먹으려고 생각을 하니까 이게 A B를 둘다 A+B로 복제하고 쪼개서 길이를 늘리면 맥시멈이 단조감소하는 구조라, 그냥 합 기준 반 갈라서 짧은 쪽을 계속 고르면 땡인 거였던 겁니다.

흠. 왜 못 봤지.

이탐 로그번 하는 코드 짜고 맞았습니다.

이 시점에 레드 퍼포가 확정되었습니다.

G (02:45)

G로 돌아왔습니다. E를 풀면서 병렬로 고민한 결과는 랜덤 박는 거 말고 답이 없다였습니다. 그니까 구체적으로, 각 현을 랜덤 비트열 해시로 나타내서 XOR = 0을 한 번 더 써먹는 풀이였습니다. 근데 랜덤 박으면 듬직한 코포 형님들이 와서 저격킬하는 거 아닌가 하고 엄벌기에 돌입했는데…

어쩌겠습니까 다른 풀이 생각 안 나는데. 어차피 레드 퍼포 받은거 걍 랜덤으로 뚝딱 짰어요. 내니까 맞긴 했습니다. 그러고 걍 어디 저격할 거면 해봐라인 상태로 코포를 껐습니다.

에디토리얼을 까보니까 랜덤이 정해였습니다. 흠.

결과

2800+ 퍼포먼스 받고 2026년이 오기 전에 오렌지를 찍었습니다.

올해는 레드를 찍읍시다.

굿