A: O(N * logN * log(10^12))가 계속 TLE나더라.... N이 무려 100만이나 해서 시간이 8초인데도 TLE가남.

아니 N 100만 양심 ㅇㄷ 30만정도로 해주지


좌우 스위핑, 위아래 스위핑, 빈칸 찾는 스위핑 총 3번 나눠서 잘 하면 O(N * logN)만에 될것 같기도 한데 코딩이 진짜 끔찍해서 그냥 건너뜀

이게 정해면 출제자님 때려야함


B. sqrt


C. O(N^2 + NMlog(NM))밖에 모르겠음. 왜 N,M<=2000으로 안주고 N*M<=500000으로 준것이죠 허어

일단 점화식은 찾았고 위 시간복잡도를 가지는 풀이를 짜니 모든 예제가 잘 나오는거 봐서 점화식을 맞게 찾은것 같음.

그런데 그 점화식 단순 계산하는데 O(N^2)이 걸리는데 최적화를 해야하나 2시간동안 연필 굴려봤는데 모르겠음

전형적인 Vandermonde's indentity식 중간에 power term 들어가니까 진짜 모르겠더라. 내가 모르는 그런 조합론 공식이라도 있나?

생성함수 이용해서 계산해보려고 했는데 딱히 식이 쉽게 나오지는 않았고, 마지막으로 (1+2x/1+x)^K를 K를 늘려나가며 계산해보려 했는데

결국 다항식 곱셈/나눗셈이 O(NlogN)이기에 오히려 O(N^2logN)으로 느려지는 결과밖에 안나왔음


2시간동안 점화식 빠르게 계산해보려고 앜앜앜앜앜 하다가 결국 시간 다됨. 뭐임? 도대체 뭐임? 뭐임? 푼사람 풀이좀 제발


D이후: 안봄. H가 많이 풀렸긴 했는데 볼걸 그랬나