2002-07-01

TopCoder SRM 401 DIV1 Easy - FIELDDiagrams (本番 176 人)

TopCoder SRMDIV1Easy カタラン数数え上げ問題二項係数 DP DP状態:個数数列グラフ・盤面・数列の個数の数え上げ

素朴な DP でもできるけど、実はカタラン数！

問題概要

正の整数 $N$ が与えられる。以下の条件を満たす数列 $a = (a_{1}, a_{2}, \dots, a_{K})$ (数列のサイズ $K$ は $1$ 以上の範囲で自由に選んでよい) の個数を求めよ。

各 $i$ に対して、 $1 \le a_{i} \le N - i + 1$ である
$a_{1} \ge a_{2} \ge \dots \ge a_{K}$ である

たとえば、 $N = 2$ のとき、 $a = (2), (2, 1), (1), (1, 1)$ の 4 通りがある。

制約

$1 \le N \le 30$

考えたこと

素朴に DP でもできるが、実はカタラン数！！

たとえば $N = 5$ のとき、 $a = (5, 3, 2, 2)$ は条件を満たすが、これは下図の左のように図示できる。そしてそれは、下図の右のように $(N+1) \times (N+1)$ グリッドの最短経路に対応する。

$a_{1} \ge a_{2} \le \dots \le a_{K}$ という条件は、グリッドの対角線の下側のみを使うということに対応する。これはカタラン数そのものである。

よって、答えは「 $N+1$ 番目のカタラン数 - 1」である (1 を引くのは右下を通る最短経路を除外するため)。つまり、

$\displaystyle \frac{_{2N}\mathrm{C}_{N}}{N+1} - 1$

を答えればよい。計算量は $O(N)$ となる。

コード

オーバーフロー対策のために、__int128_t 型を用いた。

#include <bits/stdc++.h>
using namespace std;

// オーバーフロー対策
using u128 = __int128_t;

class FIELDDiagrams {
public:
    long long countDiagrams(int fieldOrder) {
        long long N = fieldOrder + 1;
        
        // N 番目のカタラン数 - 1
        // C(2N, N) / (N+1)
        u128 res = 1;
        for (long long i = 1; i <= N; ++i) {
            res *= N*2 - i + 1;
            res /= i;
        }
        res /= (N+1);  // N 番目のカタラン数
        return (res - 1);
    }
};

// BEGIN CUT HERE
namespace moj_harness {
    int run_test_case(int);
    void run_test(int casenum = -1, bool quiet = false) {
        if (casenum != -1) {
            if (run_test_case(casenum) == -1 && !quiet) {
                cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
            }
            return;
        }
        
        int correct = 0, total = 0;
        for (int i=0;; ++i) {
            int x = run_test_case(i);
            if (x == -1) {
                if (i >= 100) break;
                continue;
            }
            correct += x;
            ++total;
        }
        
        if (total == 0) {
            cerr << "No test cases run." << endl;
        } else if (correct < total) {
            cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
        } else {
            cerr << "All " << total << " tests passed!" << endl;
        }
    }
    
    int verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) { 
        cerr << "Example " << casenum << "... "; 
        
        string verdict;
        vector<string> info;
        char buf[100];
        
        if (elapsed > CLOCKS_PER_SEC / 200) {
            sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
            info.push_back(buf);
        }
        
        if (expected == received) {
            verdict = "PASSED";
        } else {
            verdict = "FAILED";
        }
        
        cerr << verdict;
        if (!info.empty()) {
            cerr << " (";
            for (int i=0; i<(int)info.size(); ++i) {
                if (i > 0) cerr << ", ";
                cerr << info[i];
            }
            cerr << ")";
        }
        cerr << endl;
        
        if (verdict == "FAILED") {
            cerr << "    Expected: " << expected << endl; 
            cerr << "    Received: " << received << endl; 
        }
        
        return verdict == "PASSED";
    }

int run_test_case(int casenum__) {
    switch (casenum__) {
        case 0: {
            int fieldOrder            = 2;
            long long expected__      = 4;
            
            clock_t start__           = clock();
            long long received__      = FIELDDiagrams().countDiagrams(fieldOrder);
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
        case 1: {
            int fieldOrder            = 3;
            long long expected__      = 13;
            
            clock_t start__           = clock();
            long long received__      = FIELDDiagrams().countDiagrams(fieldOrder);
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
        case 2: {
            int fieldOrder            = 5;
            long long expected__      = 131;
            
            clock_t start__           = clock();
            long long received__      = FIELDDiagrams().countDiagrams(fieldOrder);
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
            
            // custom cases
            
        case 3: {
            int fieldOrder            = 29;
            long long expected__      = 3814986502092303LL;
            
            clock_t start__           = clock();
            long long received__      = FIELDDiagrams().countDiagrams(fieldOrder);
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
        case 4: {
            int fieldOrder            = 30;
            long long expected__      = 14544636039226908LL;
            
            clock_t start__           = clock();
            long long received__      = FIELDDiagrams().countDiagrams(fieldOrder);
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
            /*      case 5: {
             int fieldOrder            = ;
             long long expected__      = ;
             
             clock_t start__           = clock();
             long long received__      = FIELDDiagrams().countDiagrams(fieldOrder);
             return verify_case(casenum__, expected__, received__, clock()-start__);
             }*/
        default:
            return -1;
    }
}
}
 

int main(int argc, char *argv[]) {
    if (argc == 1) {
        moj_harness::run_test();
    } else {
        for (int i=1; i<argc; ++i)
            moj_harness::run_test(atoi(argv[i]));
    }
}
// END CUT HERE