Problem Solving Diary #19

요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 10개 뽑아 풀어 보았다. 괜찮은 문제도 있었던 반면 풀기 싫은 문제도 많이 있었다.

1. ?

정말 풀기 싫은 문제가 뽑혀서 안 풀고 넘어갔다. 무슨 문제였는지는 공개하지 않는다.

2. Монотонная подпоследовательность

길이가 $n$인 순열 중 LIS나 LDS의 길이 최댓값이 $k$인 것을 찾는 문제이다.

Erdos-Szekeres Theorem에 의하면 길이가 $(r-1)(s-1)+1$ 이상인 수열은 길이 $r$의 증가부분수열이나 길이 $s$의 감소부분수열이 있다. $r=s=k+1$을 넣으면, $k^2+1$ 이상의 길이를 가진 수열은 길이 $k+1$ 이상의 IS/DS가 있다. 따라서 $n > k^2$이면 불가능하다.

$n = k^2$라면, $k(k-1)+1, k(k-1)+2, \cdots, k(k-1)+k, k(k-2)+1, k(k-2)+2, \cdots, k(k-2)+k, \cdots, 1, 2, \cdots, k$라는 자명한 해가 있고, $n < k^2$이면 그 앞 $n$개만 따면 답이 된다. 좌표 압축을 해 주어야 함에 유의하자.

3. 슬라이딩 퍼즐 마스터

슬라이딩 퍼즐의 모든 칸을 잇는 경로를 하나 만들고, 처음에 빈칸이 있는 위치가 한쪽 끝이 되도록 하자. 이제 앞으로 모든 교환은 이 경로상의 인접한 두 점 위에서만 일어난다고 생각한다. 빈칸을 일종의 숫자로 본다면, 두 인접한 수를 교환하는 것과 한 수를 미는 것이 똑같은 종류의 연산이라는 것을 알 수 있다. 결국 풀어야 하는 문제는, $[1,2, \cdots, N]$이 적힌 배열에서 인접한 수를 교환하는 것만을 반복해 모든 $N!$가지의 상태를 만들어야 한다.

그렇다면 이 부분은 어떻게 할 수 있을까? 이 부분은 Steinhaus–Johnson–Trotter Algorithm이라는 걸 쓰면 된다고 한다. 발상 자체는 쉽다면 쉬운 것 같은데, 재귀적인 느낌이다. $N-1$에서의 해를 가지고 있을 때, $N$을 적당한 자리에 끼워넣는다는 생각으로 접근하자. 그러면 첫 번째 해는 $N$을 맨 오른쪽에 끼우는 것부터 시작해 맨 왼쪽으로 가고, 두 번째 해는 $N$을 맨 왼쪽에 끼우는 것부터 시작해 맨 오른쪽으로 가고, 이런 식으로 지그재그 느낌으로 끼워넣어주면 조건을 만족하는 $N$짜리 해를 찾을 수 있다.

4. Prosječni

$N \times N$ 격자에 서로 다른 수 $N^2$개를 채워야 하는데, 각 열과 행의 평균값이 그 열이나 행에 들어가 있어야 한다.

$N$이 홀수면 그냥 $1$부터 $N^2$까지 쭉 채우면 된다.

$N=2$면 불가능하다.

$N$이 2보다 큰 짝수일 때가 문제인데, 일단 각 행은 왼쪽의 수보다 1씩 증가하되, 마지막 수는 $\frac{n}{2}$만큼 추가로 증가시킨다. 아랫줄로 내려갈때도 앞 줄 맨 오른쪽 수에 1을 더한 것을 다음 줄 맨 왼쪽 수로 넣되, 마지막 줄은 $\frac{3}{4} n^2$만큼 추가로 증가시킨다.

자세한 건 코드로 대체한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll arr[102][102];

int main(){
    scanf("%d", &n);
    if(n==2){
        puts("-1");
        return 0;
    }
    if(n%2){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) printf("%d ", (i-1)*n+j);
            puts("");
        }
        return 0;
    }

    ll s = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            s += j<n ? 1 : n/2+1;
            printf("%lld ", s);
        }
        s += i<n-1 ? 0 : n/2*(n+n/2);
        puts("");
    }
}

5. 오렌지 수

이 문제는 사실 오렌지컵 문제인데 그때 검수를 안 한 덕에 이번에 랜덤 뽑기에서 뽑혔다.

나는 이 문제를 Python으로 규칙을 찾아서 풀었다. 일단 열심히 나이브를 돌려 보면 가능한 경우가 $9k$나 $9k+1$꼴밖에 없다. 여기서 앞 자리 대부분을 $99\cdots99$로 채울 때 마지막 몇 자리만 적당히 넣으면 되는데, 그 패턴은 Python 나이브를 돌려서 찾으면 된다.

오렌지컵 에디토리얼 언제 쓰지…

6. Subset Equality

만약 쿼리가 한 문자면 단순히 그 문자의 개수만 비교하면 된다.

만약 쿼리가 두 문자 이상이면, 해당 쿼리의 모든 두 문자 subset에 대해 그 결과가 같은지만 봐도 된다. 증명은 자명하다.

이 두 가지만 판별하면 문제를 풀 수 있다.

7. Minesweeper Master (Large)

다음과 같이 하면 된다.

• $m=0$이거나 $m=RC$이면 불가능하다.
• 그렇지 않고, $R=1$ 혹은 $C=1$이면 항상 가능하다.
• 그렇지 않고, $R=2$ 혹은 $C=2$라면, $m$이 $RC-2$가 아닌 짝수면 가능, 홀수면 불가능하다.
• 그렇지 않다면, $RC-m$이 $2$, $3$, $5$, $7$이면 불가능, 아니면 가능하다.

마지막 경우에 실제로 해를 구성하는 방법은 다음과 같다. $RC-m$이 $1$, $4$, $6$, $8$인 경우는 각각 1x1, 2x2, 2x3, 3x3에서 귀퉁이를 뺀 모양으로 안전한 칸을 만들어 주면 된다. 이보다 더 커질 경우 정말 복잡한 케이스워크를 통해 답을 구해줄 수 있다.

8. Cubic Art

각 면에 1부터 54까지의 번호를 붙이자. 한 번 돌렸을 때 가는 번호를 세그먼트 트리에 함수처럼 집어넣으면, 세그먼트 트리의 두 노드를 합치는 연산 역시 $f(g(x))$와 같이 중첩하는 것이기 때문에 54번 연산해서 처리할 수 있다. 따라서, 6가지 돌리는 방향마다 큐브의 각 면이 몇 번으로 가는지를 수작업을 하든 모델을 짜든 잘 해서 코드에 집어넣으면 문제를 $O(54 Q \log N)$에 풀 수 있다. 나는 수작업으로 했는데, 다행히도 한 번에 맞았다.

9. Next Permutation

$3-1-2$ pattern-avoiding permutation이 하나 주어질 때 사전순으로 다음 $3-1-2$ pattern-avoiding permutation을 찾는 문제이다. 문제를 보자마자 DP의 향기가 진하게 난다.

푸는 법은 간단하다. 수열의 마지막에 $A_i > A_{i+1} > \cdots > A_n$인 최소 $i$를 잡는다. $A_{i-1} < A_i$이므로, $A_{i-1}$을 크기 순서에서 $A_{i-1}, \cdots, A_n$ 다음에 있는 것으로 바꿔 준다. 다음으로, $\max(A_1, \cdots, A_i)$ 미만인 수들을 먼저 내림차순으로 배치하고, 남은 수들을 오름차순으로 배치해 주면 된다.

10. Cubeword

일단 길이가 같은 단어들만 쓸 수 있다는 건 자명하다. 모든 단어들의 길이가 같다고 가정하자.

서로 맞닿지 않은 네 꼭짓점에 쓸 글자들을 고정하자. $N=62$라고 했을 때, 총 $N^4$가지가 있다. 이제 한 꼭짓점으로 연결된 세 개의 꼭짓점만 보며, 해당 세 간선을 채우는 방법의 수를 합한 뒤 네 방향의 경우의 수를 모두 곱해 주면 된다. 한 꼭짓점으로 연결된 세 개의 꼭짓점을 처리하는 부분은, 세 꼭짓점에 적혀 있는 수의 가짓수가 $N^3$가지 뿐이므로, 미리 전처리를 $O(N^4)$에 해둘 수 있다. 따라서 전체 문제를 $O(N^4)$에 해결할 수 있다. TL이 작아서 상수를 많이 줄여야 통과할 수 있으니 조심해야 한다.