559C - Gerald and Giant Chess

c++ Codeforce

Problem - C - Codeforces
Problem - E - Codeforces

  • 復習。本番普通に DP しようとして MLE した。
  • よく読むと h,w の制限が 10^5 とかなんで座標圧縮とかしないとダメなのかなー、座標圧縮ってどうやるのか？とか思っていたがそもそも方針が違った。
  • 総経路からダメなものを引くというやり方。
  • 「dp[i] := (0,0) -> A[i] まで black cell を通過せずにたどり着くための経路総数」という dp の持ち方をするので重複なく計算ができる。うまいなと思った。
  • nCr の計算を通常の int nCr[maxN][maxN]; みたいなテーブルでやると結局 TLE してしまうので、MOD が素数であることを利用したテーブル作成が必要。
  • 入力が row,column の順なのに cin>>x>>y とかやって答えが全然合わないというしょうもないバグを作ってしまった。
class nCombP {
    long long ModP;
    std::vector<long long> fact_;
    std::vector<long long> factr_;
public:
    // O(maxN)
    nCombP(int maxN, long long P) {
            ModP = P;
            std::vector<long long> inv(maxN+1, 0);
            fact_.resize(maxN+1,0);
            factr_.resize(maxN+1,0);
            inv[1] = fact_[0] = factr_[0] = 1;
            // 逆元をもとめておく。ModP は素数なので逆元は存在する。
            // ModP = i*a + b == 0 (mod ModP)
            // i*(-a) == b (mod ModP)
            // inv(i) = inv(b)*(-a) なので以下のような計算になる
            for (int i = 2; i <= maxN; ++i)
                inv[i] = inv[ModP % i] * (ModP - ModP/i) % ModP;
            for (int i = 1; i <= maxN; ++i)
            {
                fact_[i]  = fact_[i-1]*i % ModP;
                factr_[i] = factr_[i-1]*inv[i] % ModP;
            }
    }
    // n!/(r! (n-r)!)
    long long operator()(long long n, long long r) {
            if (r < 0 || r > n)
                return 0;
            return (fact_[n] * factr_[r] % ModP) * factr_[n-r] % ModP;
    }
};

class Div2C {
public:
    void solve(void) {
            int h,w,n;
            cin>>h>>w>>n;
            nCombP nCr(h+w, (int)(1E+9)+7);

            // 左上から右下までの移動経路総数を計算する。
            // 盤面が h,w <= 10^5 と広いので通常の dp でやると TLE or MLE する。
            // そこで
            // (1,1) -> (w,h) までの総経路数から黒タイルを通る経路を除くことで求める
            vector<pair<int,int>> A;

            REP(i,n)
            {
                int x,y;
                cin>>y>>x;
                --x,--y;
                A.emplace_back(x,y);
            }
            // 右下も追加しておく
            A.emplace_back(w-1,h-1);
            ++n;

            sort(RANGE(A));

            // dp[i] := (0,0) -> A[i] まで black cell を通過せずにたどり着くための経路総数
            vector<ModInt> dp(n, 0);

            // (xj,yj) -> (xi,yi) までの総数は nCr(xi-xj+yi-yj,xi-xj)
            REP(i,n)
            {
                int xi,yi;
                tie(xi,yi) = A[i];

                // (0,0) -> A[j] までの経路総数
                ModInt total = nCr(xi+yi, xi);
                // black cell を通過してたどり着くものを引く
                for (int j = 0; j < i; ++j)
                {
                    int xj,yj;
                    tie(xj,yj) = A[j];
                    // 左・下の移動で到達できないなら飛ばす
                    if ( xj <= xi && yj <= yi )
                    {
                        // 複数の black cell を通過するケースは nCr(...) のほうに含まれている
                        // dp[j] の方に含まれるパスは j 毎に異なるので重複はない
                        total -= dp[j]*nCr(yi-yj+xi-xj, xi-xj);
                    }
                }
                dp[i] = total;
            }
            cout<<dp[n-1]<<endl;
    }
};