멋없는 격자

결과 격자를 $B$라고 하자.

먼저 다음 조건이 핵심이다.

$$B_{i,j+1} \neq B_{i+1,j}\qquad(1\leq i<N,\ 1\leq j<M).$$

이 조건이 깨지는 칸 $(i,j)$가 있다면, $(i,j)$까지 같은 경로를 따라간 뒤 한 경로는 오른쪽-아래, 다른 경로는 아래-오른쪽으로 이동하고, $(i+1,j+1)$부터 다시 같은 경로를 따라가면 된다. 두 경로에서 달라지는 유일한 위치의 문자가 같으므로 같은 문자열을 얻는다.

반대로 서로 다른 두 최단 경로를 잡고 처음으로 다른 방향으로 이동하는 순간을 보자. 두 경로가 다음에 방문하는 칸은 어떤 $(i,j+1)$과 $(i+1,j)$이다. 위 조건에 의해 두 문자가 다르므로 두 경로가 만드는 문자열도 다르다.

따라서 격자가 멋있는 격자가 아닌 것과 위 조건은 동치이다.

$i+j$가 같은 칸들을 하나의 반대각선이라고 하자. 위 조건은 각 반대각선의 값이 위에서 아래로 $0,1,0,1,\ldots$ 또는 $1,0,1,0,\ldots$ 중 하나여야 한다는 뜻이다. 서로 다른 반대각선 사이에는 아무 제약이 없다.

반대각선 하나의 길이를 $L$이라 하자. 기준 패턴을 $P_{i,j}=(i-1)\bmod 2$로 두고, 이 반대각선에서 $A$와 $P$가 다른 칸의 수를 $c$라 하자. 이 반대각선을 기준 패턴으로 만들 때 필요한 반전 수는 $c$, 반대 패턴으로 만들 때 필요한 반전 수는 $L-c$이다.

따라서 이 반대각선의 최소 비용은

$$m=\min(c,L-c)$$

이고, 더 비싼 선택으로 바꿀 때 추가되는 비용은

$$w=|L-2c|$$

이다.

모든 반대각선의 최소 비용 합을 $S$라 하자. 반대각선 길이의 합은 $NM$이므로 가능한 최대 비용은 $NM-S$이다.

이제 $S$와 $NM-S$ 사이의 모든 정수가 실제로 가능함을 보이면 된다. 반대각선을 길이의 오름차순으로 정렬한다. 길이가 $L$인 반대각선의 $w$는 $L$과 같은 홀짝성을 가지며 $0\leq w\leq L$이다. 길이 $L\geq2$인 첫 반대각선 앞에는 각 길이 $1,2,\ldots,L-1$인 반대각선이 두 개씩 있다. 길이 $1$에서는 $w=1$이고, 홀수 길이에서는 항상 $w\geq1$이다. 따라서 앞선 $w$의 합을 $P$라 하면 항상 $P\geq L-1$이다. 같은 길이의 두 번째 이후 반대각선에서는 $P$가 더 커질 뿐이다. 그러므로 항상

$$w\leq P+1$$

이다.

부분합이 $0,1,\ldots,P$를 모두 만들 수 있고 새 가중치가 $w\leq P+1$이라면, 새 부분합은 $0,1,\ldots,P+w$를 모두 만들 수 있다. 길이 $1$인 첫 반대각선부터 귀납하면 모든 $w$의 부분합은 $0$부터 그 합까지 끊김 없이 모두 가능하다.

따라서 정확히 $K$번 반전하는 답이 존재할 필요충분조건은

$$S\leq K\leq NM-S$$

이다.

실제 선택도 같은 귀납을 역순으로 사용하면 된다. 정렬된 $w$의 누적합을 저장하고 $R=K-S$라 하자. 뒤에서부터 보면서 현재 $R$이 앞쪽 가중치의 누적합보다 크면 현재 반대각선의 더 비싼 패턴을 반드시 선택하고 $R$에서 $w$를 뺀다. 그렇지 않으면 더 싼 패턴을 선택한다. 위의 연속 부분합 성질 때문에 항상 정확히 $R=0$으로 끝난다.

격자를 한 번 순회해 각 반대각선의 $L,c$를 구하고, 반대각선 $N+M-1$개를 정렬하면 된다. 시간 복잡도는 $O(NM+(N+M)\log(N+M))$, 메모리 복잡도는 출력 격자를 제외하면 $O(N+M)$이다.

Solution written by GPT5.6