Educational Codeforces Round 113 복기

기존의 Codeforces Round가 아니라 Educational Codeforces Round에 참가했다.

D 문제가 D1, D2로 나누어져 있는 것을 제외하고는 무슨 차이가 있는지는 잘 모르겠다.

A, B가 너무 쉬워서 A, B, C 까지는 무난한 게 제출하나 싶었지만 C에서 막히고 넘어간 D에서도 막혔다...

 

https://codeforces.com/contest/1569/problem/C

Problem - C - Codeforces

정수 배열의 모든 값을 순차적으로 1씩 감소시키는 행위를 배열의 모든 숫자가 0이 될 때까지 반복하여 진행했을 때, 같은 위치에서 연속으로 감소하는 경우가 없는 경우 nice permutations라고 한다.

n개의 정수가 주어졌을 때, n개의 정수로 만들 수 있는 배열 중 nice permutations의 개수를 구하는 문제.

배열이 nice permutation이 되는 경우는 두가지가 있다.

1. 배열 내의 최댓값이 중복으로 존재하는 경우.

2. 최댓값 - 1의 값이 배열 내에서 최댓값보다 뒤에 존재하는경우.

1번을 만족하는 경우에는 모든 배열이 nice permuation이기 때문에 n!을 출력하면 된다.(n에 따라 값이 매우 커질 수 있기 때문에 modulo 998244353를 사용하라고 문제에 제시되어있다)

1번을 만족하지 않는 경우, 즉 최댓값의 중복이 없는 경우에는 최댓값 - 1이 존재하지 않으면 0을 출력하고 존재한다면 전체 개수에서 최댓값 - 1의 값이 전부 왼쪽에 있는 경우의 수를 빼주면 된다.

최댓값 - 1이 r개 존재한다고 하면 r! * (n - r - 1)! + (r+1)! * (n - r - 2)! + .... + (n-1)! 을 계산하면 최댓값 - 1이 모두 왼쪽에 있는 경우의 수를 구할 수 있다.

하지만 여기서 관점을 조금 바꾸어 생각하면 계산식이 훨씬 간단해질 수 있다. r개의 최댓값 - 1과 최댓값을 묶어 총 r+1개의 값을 하나로 묶은 후에 r+1개의 값의 순서는 고려하지 않는 전체 경우의 수 n! / (r+1)! 에 최댓값을 가장 오른쪽에 고정하고 r+1개를 나열하는 경우의 수 r! 를 곱해주면 n! / r+1로 간단해진다.

1을 만족하는 경우에는 n! 를 그 외의 경우에는 n! - (n! / r+1)을 출력한다. (r이 0인 경우에 n! - n! = 0이 되기 때문에 따로 처리할 필요가 없다)

  int k = count(a.begin(), a.end(), mx - 1);
    int ans = 1, sub = 1;
    for (long long i = 1; i <= n; ++i) {
      ans = ans * i % MOD;
      if (i != k + 1) sub = sub * i % MOD;
    }

솔루션의 코드를 보면 n! 을 mod연산을 하면서 구하기 때문에 n! 에 r+1을 나누는 것으로는 원하는 값을 구할 수 없기 때문에 분수에서 약분을 하듯이 1부터 n까지 구하는 과정에서 r+1을 제외하고 곱하는 방식으로 따로 계산을 하여 저장한다.

이 문제는 nice permutation의 조건을 알아내는 것은 오래 걸리지 않았지만 큰 값의 계산을 정수 표현 범위 내에서 잘 처리하지 못해 헤맸던 것 같다.