Topcoder SRM 690 Div 2 Hard WolfHockeyTeamEasy

解くのに10時間ほどかかった...
問題
TopCoder Statistics - Problem Statement
$2N$ 人が横に２列になって写真を撮る．それぞれの人は $0$ から $2N-1$ まで番号がふられている．
この時の並びは"nice"かつ"different"でなくてはいけない．"nice"とは， $K$ 以上の番号がふられた人が２つの列に少なくとも一人ずついることである．"different"とは，各列の番号の最大値，縦に並んでいる２人の番号の最大値が異なる組み合わせのことである．
この時，並ぶ組み合わせは何通りあるか求める問題．

解法
ここからは横方向を行，縦方向を列と呼ぶ．
まず，列の下の方が番号が大きく，行の右の方が番号が大きい行列，つまり

0	1	3	4	6
2	5	7	8	9

のような行列を考える．
この行列の行，列ごとに並び替えたものは"different"である．その組み合わせは $N!*2$ 通り存在する．
上のような列が何通りあるか数えて，それに $N!*2$ をかければすべての組み合わせになる．
メモ化再帰で実装する．

int dp[1001][1001];

int dfs(int i, int j) {
    if (dp[i][j])
        return dp[i][j];
    int ret = 0;
    if (i > j)
        ret += dfs(i-1,j);
    if (j > 0)
        ret += dfs(i,j-1);
    return dp[i][j] = ret % MOD;
}

int count(int N, int K) {
    int i;
    ll ret;
    dp[0][0] = 1;
    ret = dfs(N,N);
    REP (i,1,N) ret = ret * i % MOD;
    ret = ret * 2 % MOD;
    return ret;
}

常に $i\geq j$ なので動的計画法でもできる．

int count(int N, int K) {
    int i, j;
    int dp[1002][1002] {};
    dp[0][0] = 1;
    rep (i,N+1) rep (j,i+1) {
        dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
        if (i > j)
            dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
    }
    ll ret = dp[N][N];
    REP (i,1,N) ret = ret * i % MOD;
    ret = ret * 2 % MOD;
    return ret;
}

実は上で考えた行列だけでは"different"なものをすべて列挙したことにならない．3と7を入れ替えた行列，

0	1	7	4	6
2	5	3	8	9

も"different"であるが上の手法では含まれない．しかし，これは簡単に数えることができる．
3と7を入れ替えただけで"different"になったのは上の行の最大値が6だからである． $dp[N][7-N]$ 通りの行列は上の列が必ず7以下になるため，同じように入れ替えれば"different"になる．
よって， $i=N,N+1,...,2N-1$ について $dp[N][i-N]$ を足しあわせたものが求める値になる．

    ll ret = dp[N][N];

を

    ll ret = 0;
    rep (i,N) ret = (ret + dp[N][i]) % MOD;

とすればよい．
ここからは"nice"であることを考える．先ほどの動的計画法において"nice"であるかどうか分けて考えれば良い．つまり，
dp[上の行を埋めた数][下の行を埋めた数]["nice"かどうか]=組み合わせの数
で動的計画法をすれば良くなる．

N=4,K=6の時，"nice"でない行列，

0	1	2	3	4
5	6	7	8	9

も2と7などを入れ替えれば"nice"になることに注意する．

ソースコード

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000
#define MOD 1000000007

ll dp[1002][1002][2];

int count(int N, int K) {
    int i, j, k;
    dp[0][0][0] = 1;
    rep (i,N+1) rep (j,i+1) rep (k,2) {
        dp[i+1][j][i+j >= K] = (dp[i+1][j][i+j >= K] + dp[i][j][k]) % MOD;
        if (i > j)
            dp[i][j+1][k] = (dp[i][j+1][k] + dp[i][j][k]) % MOD;
    }
    ll ret = dp[N][N][0] * (2 * N - 1 - K);
    rep (i,N) ret = (ret + dp[N][i][1]) % MOD;
    REP (i,1,N) ret = ret * i % MOD;
    ret = ret * 2 % MOD;
    return ret;
}

h_nosonの日記

競プロ、CTFなど

Topcoder SRM 690 Div 2 Hard WolfHockeyTeamEasy