Educational Codeforces Round 127 (Rated for Div. 2)

https://codeforces.com/contest/1671

 

뭔가 문제가 잘 풀리던 날. 문제들의 풀이가 애초에 떠올리기만 하면 구현이 매우 쉬웠다.

사실 저번에 #782에서 2109점이 되었는데, 이때 2100점을 넘기지 못하였더라면 이번에 2200점은 되었을 듯하다.

(점수판을 보니 2088점이 2511퍼포를 보이면 예상 점수 증가가 111점이다. 내가 저 상황이였으면...)

퍼포가 2520 정도인데 개인 등수 80등 정도도 처음이었던 것 같다.

 

A. String building

 

2 이상의 모든 정수는 2와 3의 합으로 나타낼 수 있음이 자명하다.

-> a가 연속으로 1개만 나오는 경우만 피해주면 된다.

 

B. Consecutive Points Segment

 

결국에는 어차피 1밖에 이동할 수 없기 때문에 최대 3조각으로만 나뉘어져 있어야 한다.

-> 맨 뒤 원소와 맨 앞 원소의 차이가 n + 1이하이면 가능하다.

https://codeforces.com/contest/1671/submission/154513990

 

C. Dolce Vita

 

단순하게 맨 앞에서부터 a값들의 sum을 끌고가서 a_i를 몇일날까지 구매할 수 있는지 계산해주면 된다.

이때 사실 분수식 연산이 잘 안되어서 런할까 3분정도 멍때렸다.

https://codeforces.com/contest/1671/submission/154521116

 

D. Insert a Progression

 

사실 문제를 잘못 이해해서 https://codeforces.com/problemset/problem/1661/F와 유사한줄 알았다.

하지만 div2 D에서 저런게 나올 리가 없다는 확신을 하고 다시 문제를 봤다.

 

관찰 1 : 1과 x만 insert한다고 생각해도 충분하다. 

-> 1과 x가 우선 있기만 한다면 그 사이 어떤 부분에 S의 증가 없이 2, 3, ...를 insert할 수 있다.

관찰 2 : 1과 x는 min, max, 맨 앞, 맨 뒤 중 한 곳에 존재한다.

-> 1을 삽입할 때 만일 맨앞이나 맨 뒤가 아니라면 (a_i - 1)*2만큼 증가하므로 최소가 되는 a_i 옆에 두는게 좋다.

-> 하지만 맨 앞이라면 (a_0 - 1)만큼 증가하므로 a_0가 최소가 아니라도 더 좋은 선택일 수 있다.

https://codeforces.com/contest/1671/submission/154536360

 

E. Preorder

 

세그트리에서 merge하듯이 어떤 i에 대해 L, R의 자식이 있으면 L, R을 merge하여 i번 노드를 만들어주면 된다.

-> 이때 각 노드에는 1. 이 밑을 이용해서 만드는 string의 개수 2. 이 밑을 정렬한 최소의 string를 넣어두면 된다.

-> L.2 != R.2 인 경우에는 i.1 = L.1 * R.1 * 2이 된다. ((s_i + L + R)로 배열하던가 (s_i + R + L)로 배열)

-> 하지만 L.2 == R.2인 경우에는 L이 앞이든 R이 앞이든 똑같으므로 i.1 = L.1 * R.1이 된다.

이런 merge 과정을 루트까지 다해주면 된다.

https://codeforces.com/contest/1671/submission/154547829

 

F. Permutation Counting

 

설명하기는 어렵지만 생각보다 단순한 방법으로 풀 수 있다.

 

k와 x의 값이 비정상적으로 작다는 것을 보자마자 확인할 수 있다.

따라서 n이 비정상적이지만 뭔가 나이브한 냅색처럼 잘 풀어낼 수 있을 거라는 생각이 든다.

(물론 비정상적인 n을 보고 행렬을 떠올리는게 맞는거 같기도 하다.)

 

관찰 1 : bubble sort에 필요한 swap의 최소 횟수는 inversion의 수와 동일하다.

-> 대회 중에 발견한 당연한 느낌의 성질인데 인터넷 어딘가에서 well known일 만한 성질인거 같다. 

그렇다면 결국 k개의 swap과 x개의 decrease(dec)을 가지는 permutation의 개수를 세면 된다.

 

관찰 2 : 결국 저 swap들과 inversion을 만드는 부분의 길이는 n처럼 큰 숫자가 아니라 매우 작은 부분(=seg)이다.

-> 예를 들어 20 이상 차이나는 두 숫자의 위치가 바뀌어 있다고 가정하자. 그러면 swap의 수가 11을 훌쩍 넘는다.

-> 이 풀이를 처음 떠올렸을 때에는 seg의 최대 길이를 최대 7이라 착각 (7, 2, 3, 4, 5, 6, 1) = (swap 11, dec 1)

-> 하지만 막바지에는 이 최대 길이가 12임을 깨달았다. (11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10) = (swap 11, dec = 1) 

 

그렇다면 결국 k번의 swap과 x번의 dec는 여러 seg에서 이루어지는 swap과 dec들의 합임을 알 수 있다.

또한 k와 x의 크기제한으로 인해서 쓰이는 seg의 개수는 11개 이하이다.

그렇다면 예를 들어 길이의 합이 p가 되는 seg들을 q개 이용하서 swap = k, dec = x를 만들었다고 하자.

그러면 이 q개의 사이와 앞뒤에 있는 q + 1개의 공간에 남는 숫자 (n - p)개를 적당히 넣어주면 된다.

-> 이는 H(q + 1, n - p)이다.

다만 n 제한이 1e9이기에 모든 factorial 값을 전처리 해주는 방식은 불가능하다.

-> 적당히 1~100까지의 factorial값과 n * (n -1) * ... (n - i)의 값을 100개 정도만 미리 계산해두면 된다.

 

우선 대회중에 작성한 코드는 다음과 같다. 

처음 코드를 만들었을 때에는 MAXLEN의 크기를 7로 착각하였기에 TLE를 편하게 통과할 수 있을 줄 알았다.

sd[x][{y, z}] = w 의 의미는 길이가 x이고 swap이 y개, dec가 z개인 seg의 종류이다. 

주의) 아래 코드에서 fact[i]는 1/(i!)을 의미하며 invfact[i]는 n * (n - 1) * ... (n - i + 1)을 의미한다.

signed main(){
    //IOS;
 
    int MAXLEN = 13;
    vector<map<pii, int>> sd(MAXLEN);
    for(int len = 2; len < MAXLEN; len++){
        vi tmp(len);
        iota(tmp.begin(), tmp.end(), 0);
        do{
            for(int i = 0, j = 0; i < len - 1; i++){
                j += tmp[i];
                if(j == i * (i + 1) / 2) {
                    int idx = -1;
                    for(int p = 0; p < len; p++){
                        if(tmp[p] == i + 1) idx = p;
                    }
                    j = j - tmp[i] + tmp[idx];
                    swap(tmp[idx], tmp[i]);
                }
            }
            int cnt_swap = 0;
            int cnt_dec = 0;
            vi sorting(len);
            for(int i = 0; i < len; i++) sorting[i] = tmp[i];
            for(int i = 0; i < len; i++){
                if(i && tmp[i] < tmp[i - 1]) cnt_dec++;
                int idx = -1;
                for(int j = 0; j < len; j++) if(sorting[j] == i) idx = j;
                while(idx != i) swap(sorting[idx], sorting[idx - 1]), idx--, cnt_swap++;
            }
            if(cnt_swap > 11 || cnt_dec > 11) continue;
            sd[len][{cnt_swap, cnt_dec}]++;
        }while(next_permutation(tmp.begin(), tmp.end()));
    }
 
    vi fact(100, 1);
    for(int i = 1; i < 100; i++) fact[i] = fact[i - 1] * i, fact[i] %= MOD;
    for(int i = 0; i < 100; i++) fact[i] = modinv(fact[i]);
 
    int t; cin >> t;
    while(t--){
        int n, k, x; cin >> n >> k >> x;
 
        map<int, int> invfact;
        invfact[n] = n;
        for(int i = n - 1; i >= max(0ll, n - 100); i--){
            invfact[i] = invfact[i + 1] * i;
            invfact[i] %= MOD;
        }
 
        vector<map<tiii, int>> dp(12);
        dp[0][{0, 0, 0}] = 1;
        int ans = 0;
        for(int i = 1; i < 12; i++){
            for(auto it1 = dp[i - 1].begin(); it1 != dp[i - 1].end(); it1 = next(it1)){
                for(int j = 0; j < MAXLEN; j++){
                    for(auto it2 = sd[j].begin(); it2 != sd[j].end(); it2 = next(it2)){
                        auto[p, q] = *it1;
                        auto[r, s] = *it2;
                        auto[p1, p2, p3] = p;
                        auto[r1, r2] = r;
                        if(p2 + r1 > k || p3 + r2 > x) continue;
                        dp[i][{j + p1, p2 + r1, p3 + r2}] += q * s;
                        dp[i][{j + p1, p2 + r1, p3 + r2}] %= MOD;
                    }
                }
            }
            for(auto it1 = dp[i].begin(); it1 != dp[i].end(); it1 = next(it1)){
                auto[p1, p2, p3] = it1 -> first;
                if(p1 > n || p2 != k || p3 != x) continue;
                ans += fact[i] * invfact[n - p1 + 1] % MOD * modinv(invfact[n - p1 + i + 1]) % MOD * it1 -> second % MOD;
                ans %= MOD;
            }
        }
        cout << ans << endl;
    }
}

이런 코드는 결국에 12!가지를 직접 해야하므로 무조건 TLE이다.

또한 뒷부분에 DP의 계산을 무려 T번 반복하므로 애초에 잘못된 코드이기도 하다.

 

업솔빙을 할 때 저 sd의 계산을  약간의 편법으로 이를 통과시켰다.

감각적으로든 직접확인해서든 sd에 들어있는 숫자의 종류가 얼마 되지 않는다는 확신을 할 수 있다. (실제로 <150)

따라서 sd를 코드 내에서 계산하는게 아니라 로컬에서 모두 계산해두고 박아두면 TLE를 피해갈 수 있다.

signed main(){
    IOS;
 
    int MAXLEN = 13;
    vector<map<pii, int>> sd(MAXLEN);
    sd[2][{1, 1}] = 1;
    sd[3][{2, 1}] = 2;
    sd[3][{3, 2}] = 1;
    sd[4][{3, 1}] = 3;
    sd[4][{3, 2}] = 1;
    sd[4][{4, 1}] = 1;
    sd[4][{4, 2}] = 4;
    sd[4][{5, 2}] = 3;
    sd[4][{6, 3}] = 1;
    sd[5][{4, 1}] = 4;
    sd[5][{4, 2}] = 4;
    sd[5][{5, 1}] = 2;
    sd[5][{5, 2}] = 12;
    sd[5][{5, 3}] = 2;
    sd[5][{6, 1}] = 2;
    sd[5][{6, 2}] = 12;
    sd[5][{6, 3}] = 4;
    sd[5][{7, 2}] = 9;
    sd[5][{7, 3}] = 6;
    sd[5][{8, 2}] = 3;
    sd[5][{8, 3}] = 6;
    sd[5][{9, 3}] = 4;
    sd[5][{10, 4}] = 1;
    sd[6][{5, 1}] = 5;
    sd[6][{5, 2}] = 10;
    sd[6][{5, 3}] = 1;
    sd[6][{6, 1}] = 3;
    sd[6][{6, 2}] = 28;
    sd[6][{6, 3}] = 13;
    sd[6][{7, 1}] = 4;
    sd[6][{7, 2}] = 35;
    sd[6][{7, 3}] = 29;
    sd[6][{7, 4}] = 1;
    sd[6][{8, 1}] = 3;
    sd[6][{8, 2}] = 35;
    sd[6][{8, 3}] = 41;
    sd[6][{8, 4}] = 4;
    sd[6][{9, 1}] = 1;
    sd[6][{9, 2}] = 30;
    sd[6][{9, 3}] = 44;
    sd[6][{9, 4}] = 7;
    sd[6][{10, 2}] = 17;
    sd[6][{10, 3}] = 45;
    sd[6][{10, 4}] = 7;
    sd[6][{11, 2}] = 8;
    sd[6][{11, 3}] = 30;
    sd[6][{11, 4}] = 11;
    sd[7][{6, 1}] = 6;
    sd[7][{6, 2}] = 20;
    sd[7][{6, 3}] = 6;
    sd[7][{7, 1}] = 4;
    sd[7][{7, 2}] = 55;
    sd[7][{7, 3}] = 50;
    sd[7][{7, 4}] = 3;
    sd[7][{8, 1}] = 6;
    sd[7][{8, 2}] = 80;
    sd[7][{8, 3}] = 118;
    sd[7][{8, 4}] = 18;
    sd[7][{9, 1}] = 6;
    sd[7][{9, 2}] = 95;
    sd[7][{9, 3}] = 186;
    sd[7][{9, 4}] = 48;
    sd[7][{10, 1}] = 6;
    sd[7][{10, 2}] = 101;
    sd[7][{10, 3}] = 230;
    sd[7][{10, 4}] = 85;
    sd[7][{10, 5}] = 2;
    sd[7][{11, 1}] = 2;
    sd[7][{11, 2}] = 94;
    sd[7][{11, 3}] = 260;
    sd[7][{11, 4}] = 113;
    sd[7][{11, 5}] = 4;
    sd[8][{7, 1}] = 7;
    sd[8][{7, 2}] = 35;
    sd[8][{7, 3}] = 21;
    sd[8][{7, 4}] = 1;
    sd[8][{8, 1}] = 5;
    sd[8][{8, 2}] = 96;
    sd[8][{8, 3}] = 145;
    sd[8][{8, 4}] = 26;
    sd[8][{9, 1}] = 8;
    sd[8][{9, 2}] = 155;
    sd[8][{9, 3}] = 358;
    sd[8][{9, 4}] = 124;
    sd[8][{9, 5}] = 3;
    sd[8][{10, 1}] = 9;
    sd[8][{10, 2}] = 207;
    sd[8][{10, 3}] = 616;
    sd[8][{10, 4}] = 313;
    sd[8][{10, 5}] = 16;
    sd[8][{11, 1}] = 11;
    sd[8][{11, 2}] = 250;
    sd[8][{11, 3}] = 859;
    sd[8][{11, 4}] = 567;
    sd[8][{11, 5}] = 53;
    sd[9][{8, 1}] = 8;
    sd[9][{8, 2}] = 56;
    sd[9][{8, 3}] = 56;
    sd[9][{8, 4}] = 8;
    sd[9][{9, 1}] = 6;
    sd[9][{9, 2}] = 154;
    sd[9][{9, 3}] = 350;
    sd[9][{9, 4}] = 126;
    sd[9][{9, 5}] = 4;
    sd[9][{10, 1}] = 10;
    sd[9][{10, 2}] = 268;
    sd[9][{10, 3}] = 898;
    sd[9][{10, 4}] = 552;
    sd[9][{10, 5}] = 48;
    sd[9][{11, 1}] = 12;
    sd[9][{11, 2}] = 389;
    sd[9][{11, 3}] = 1654;
    sd[9][{11, 4}] = 1404;
    sd[9][{11, 5}] = 204;
    sd[9][{11, 6}] = 1;
    sd[10][{9, 1}] = 9;
    sd[10][{9, 2}] = 84;
    sd[10][{9, 3}] = 126;
    sd[10][{9, 4}] = 36;
    sd[10][{9, 5}] = 1;
    sd[10][{10, 1}] = 7;
    sd[10][{10, 2}] = 232;
    sd[10][{10, 3}] = 742;
    sd[10][{10, 4}] = 448;
    sd[10][{10, 5}] = 43;
    sd[10][{11, 1}] = 12;
    sd[10][{11, 2}] = 427;
    sd[10][{11, 3}] = 1967;
    sd[10][{11, 4}] = 1887;
    sd[10][{11, 5}] = 357;
    sd[10][{11, 6}] = 6;
    sd[11][{10, 1}] = 10;
    sd[11][{10, 2}] = 120;
    sd[11][{10, 3}] = 252;
    sd[11][{10, 4}] = 120;
    sd[11][{10, 5}] = 10;
    sd[11][{11, 1}] = 8;
    sd[11][{11, 2}] = 333;
    sd[11][{11, 3}] = 1428;
    sd[11][{11, 4}] = 1302;
    sd[11][{11, 5}] = 252;
    sd[11][{11, 6}] = 5;
    sd[12][{11, 1}] = 11;
    sd[12][{11, 2}] = 165;
    sd[12][{11, 3}] = 462;
    sd[12][{11, 4}] = 330;
    sd[12][{11, 5}] = 55;
    sd[12][{11, 6}] = 1;
    
    vi fact(100, 1);
    for(int i = 1; i < 100; i++) fact[i] = fact[i - 1] * i, fact[i] %= MOD;
    for(int i = 0; i < 100; i++) fact[i] = modinv(fact[i]);
    vector<map<tiii, int>> dp(12);
    dp[0][{0, 0, 0}] = 1;
    int ans = 0;
    for(int i = 1; i < 12; i++){
        for(auto it1 = dp[i - 1].begin(); it1 != dp[i - 1].end(); it1 = next(it1)){
            for(int j = 0; j < MAXLEN; j++){
                for(auto it2 = sd[j].begin(); it2 != sd[j].end(); it2 = next(it2)){
                    auto[p, q] = *it1;
                    auto[r, s] = *it2;
                    auto[p1, p2, p3] = p;
                    auto[r1, r2] = r;
                    if(p2 + r1 > 11 || p3 + r2 > 11) continue;
                    dp[i][{j + p1, p2 + r1, p3 + r2}] += q * s;
                    dp[i][{j + p1, p2 + r1, p3 + r2}] %= MOD;
                }
            }
        }
    }
    int t; cin >> t;
    while(t--){
        int n, k, x; cin >> n >> k >> x;
 
        map<int, int> invfact;
        invfact[n] = n;
        for(int i = n - 1; i >= max(0ll, n - 100); i--){
            invfact[i] = invfact[i + 1] * i;
            invfact[i] %= MOD;
        }
        int ans = 0;
        for(int i = 1; i < 12; i++){
            for(int j = 0; j < 100; j++){
                if(dp[i].find({j, k, x}) == dp[i].end()) continue;
                ans += fact[i] * invfact[n - j + 1] % MOD * modinv(invfact[n - j + i + 1]) % MOD * dp[i][{j, k, x}] % MOD;
                ans %= MOD;
            }
        }
        cout << ans << endl;
    }
}

딱 150번의 map insert으로 무려 12!번의 계산치를 대체할 수 있으니 매우 편안하게 통과할 수 있다.

예상복잡도는 T * (여러 seg의 합의 최대 길이 < 100) * (사용되는 개수) * 로그로그 (modinv, map으로 만든 dp)

물론 실제로는 아마 여러 seg의 합의 최대 길이도 100에 훨 못 미칠 것 같아서 좀 조절해주면 더 줄일 수 있다.

(TLE를 당하지 않는 범위에서 숫자들의 기준치를 매우 넉넉하게 잡긴 했다.)

 

일단 이런 수학씹덕은 atcoder 영향으로 일본애들이 잘할 것 같아서 SSRS 코드부터 까봤다.

이해를 잘 못해서 tourist꺼도 까봤는데 풀이가 비슷하다.

대충 풀이의 결이 비슷한거로 보아 editorial이 저걸 알려줄거라 생각하고 고민을 멈췄는데 정해가 내 편법이다.

 

SSRS의 그리 복잡하지는 않은 solution. 어케 굴러가는지는 잘 모르겠다

https://codeforces.com/contest/1671/submission/154558308