読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

Topcoder SRM 690 Div 2 Hard WolfHockeyTeamEasy

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

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

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;
}