정말 오랜만에 딥2를 쳤습니다.
최근에 PS를 전혀 안 하고 있어서 퍼포가 잘 안 나올 줄 알았는데, 다행히도 대회 시간이 거의 다 돼서 5솔에 성공해 작은 양델타를 얻을 수 있었습니다.
다만 아직 최고 레이팅을 복구하지는 못했습니다. 슬프네요.
대충 타임라인을 적어보자면 다음과 같습니다:
를 봤고, 111..00을 출력하면 됨을 관찰해 바로 풀었습니다.
를 한참 봤습니다.
스플레이 트리 문제에서 사용하는 테크닉인 flip 연산 세 번으로 배열을 k칸만큼 미는 걸 사용하면 $3N$번의 연산으로 풀 수 있음을 관찰했으나, 더 줄이지는 못했습니다.
포기하고 C를 봤습니다.
그리디하게 적은 수의 연산으로 1 개수를 올릴 수 있는 것 부터 올리는 게 최적이라는 사실을 관찰했습니다.
1 개수를 하나 올리는 데에 필요한 연산은 $O(\log a)$에 구할 수 있습니다.
$k\leq 10^{18}$이기에 시간 제한이 약간 걱정됐으나, 필요한 연산이 대충 두 배씩 증가하므로 $O(N(\log N+\log a))$ 정도에 돌 것이라고 믿고 짰습니다. 맞았습니다.
C를 풀고 D를 봤으나, 깡수학 문제일 것 같은 예감이 들어 B로 돌아왔습니다.
한참 고민하면서 다양한 방법을 시도하다가, 1 1 1 2 1 2 3 1 3 … n 1 n을 적용해봤습니다.
그랬더니
1 2 3 4 5
2 1 3 4 5
3 2 1 4 5
4 3 2 1 5
5 4 3 2 1
꽤 이쁘게 나오더라고요?