Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2196-97ed0dbe
この記事にトラックバックする(FC2ブログユーザー)

SRM530 DIV1 HARD - GogoXBallsAndBins (この記事を編集する[管理者用])

Source

TopCoder SRM530 DIV1 HARD (900pt)
Problem Statement

問題概要

相異なる0以上50以下の整数からなる配列Sを考える.(要素数Nは50以下,与えられるわけではない)
ある要素を1増やして,ある要素を1減らす,という操作を繰り返すことで,配列Sを昇順にソートした.
操作の回数は最小回数でソートし,ソートした後の配列Tとなった.
操作の回数とTが与えられた時,考えうるSの数をmod 1000000009で求める問題.
操作の回数は650以下.

解法

S[i]がT[i]より大きければ,S[i] - T[i]回だけS[i]を減らす操作を行わないといけないので,操作の最小回数は
 max(0, S[i] - T[i])の和
となる.同様に増やす操作の数を考えると,これは
 max(0, T[i] - S[i])の和
にも等しく,更に
 |S[i] - T[i]| / 2 の和
とも等しい.この問題を考えるときは最後のを用いる.
S[i]はT[i]の置換なので,各iに対して,T[i]とどのT[k]を対応付けるか,を探すことになる.
わかりにくいので,T1[i] = T2[i] = T[i]とすると,T1[i]とT2[k]を対応付けると,
 kがiより大きい時,T[k]回プラス,T[i]回マイナス
 kがiより小さい時,T[k]回マイナス,T[i]回プラス
していって,合計回数がmoves*2になるものの対応の数を求める問題になる.
このとき,kがiより大きいか小さいかだけによって,プラスマイナスが反転する,つまり,kは具体的に決める必要はないことに注意する.
また,T1[i]と対応付けるT2[k]を考えるのと同時に,T2[i]と対応付けるT1[m]も考える.
この時,iとkの大小関係,iとmの大小関係で,4パターンある.
kやmの方が小さいときは,今まで自分より大きいものと対応させたのと対応させなければならない.
ので,
 i

 今まで大きいものと対応させた数 - 今まで小さいものと対応させた数

 現在の回数
を状態としてDPする.
今まで大きいものと対応させた数 - 今まで小さいものと対応させた数はT1とT2で別々に所持しなくても,同じになる.
重複してカウントしないために,大きいものと対応させる時か,小さいものと対応させる時かのどちらかしか,残ってる大きいもの,小さいものの数をかけてはいけない.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000009
#define ll long long

ll dp[60][2000], next[60][2000];

class GogoXBallsAndBins {
public:
int solve(vector <int> T, int moves) {
  int i,j,k,n;

  n = T.size();

  rep(i,n+1) rep(j,2000) dp[i][j] = 0;
  dp[0][1000] = 1;

  rep(k,n){
    rep(i,n+1) rep(j,2000) next[i][j] = 0;

    rep(i,n+1) REP(j,100,1900) if(dp[i][j]){
      next[i][j] = (next[i][j] + (2*i+1) * dp[i][j])%M;
      if(i) next[i-1][j+T[k]] = (next[i-1][j+T[k]] + i*i*dp[i][j])%M;
      next[i+1][j-T[k]] = (next[i+1][j-T[k]] + dp[i][j])%M;
    }

    rep(i,n+1) rep(j,2000) dp[i][j] = next[i][j];

//    printf("k = %d\n",k);
//    rep(i,n+1) rep(j,2000) if(dp[i][j]) printf("%d %d %lld\n",i,j,dp[i][j]);
  }

  return dp[0][1000+moves];
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2196-97ed0dbe
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。