| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 143 | 118 | 110 | 85.271% |
$N^2$개의 수가 $N$행 $N$열의 표 $A$에 채워져 있다. 표의 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열에 위치한 칸에는 정수 $A_{r,c}$가 적혀 있으며, $r$행 $c$열을 편의상 $(r,c)$로 표현한다.
표 $A$에서 직사각형 맨 왼쪽 위 칸이 $(r_1,c_1)$이고, 맨 오른쪽 아래 칸이 $(r_2,c_2)$가 되게 직사각형을 선택할 때, 1ドル\leq r_1\leq r\leq r_2\leq N,1\leq c_1\leq c\leq c_2\leq N$ 을 만족하는 $A_{r,c}$는 직사각형 안에 있는 수이다.
수 $x$개로 이루어진 배열이 1ドル$부터 $x$까지의 서로 다른 정수 $x$개로 이루어져 있다면, 순열이다. 예를 들어 $[2,3,1,5,4]$는 순열이지만, $[1,2,2]$와 $[1,3,4]$는 순열이 아니다.
직사각형의 네 변이 표의 경계선과 겹치도록 직사각형을 선택할 때, 직사각형 안에 있는 수를 나열한 것이 순열이 되는 경우의 수는 얼마일까?
첫째 줄에 표 $A$의 행과 열의 개수 $N$이 주어진다. (1ドル\leq N\leq 15$)
이후 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $A_{i,1},A_{i,2},\ldots ,A_{i,N}$이 공백으로 구분되어 주어진다. (1ドル\leq A_{i,j}\leq N^2$)
첫째 줄에 경우의 수를 출력한다.
4 1 2 1 5 3 1 8 1 1 2 1 3 3 1 4 1
16
$(3, 2)$와 $(3, 4)$ 사이에 있는 수는 $[2, 1, 3]$으로, 순열이다.
반면 $(3, 1)$과 $(4, 2)$ 사이에 있는 수는 $[1, 2, 3, 1]$으로, 순열이 아니다.
Camp > 숭고한 연합 Algorithm Camp > 2025 숭고한 연합 알고리즘 경진대회 > Div. 2 A번
Camp > 숭고한 연합 Algorithm Camp > 2025 숭고한 연합 알고리즘 경진대회 > Div. 3 D번