Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM475 DIV1 HARD (900pt)
Problem Statement

問題概要

コンテストの問題の配点と,各問題がシステムテストが終わったかどうかの情報が与えられる.
 システムテストが終わった問題に関しては,正解者のリスト,
 システムテストが終わってない問題に関しては,提出者のリスト(正解かどうか不明)
が与えられる.
参加者中,上位n人の中から,m人選んでチームをつくる場合,作れる可能性のあるチームの数をmod いくらかで求める問題.
問題数は50以下,参加者数は50以下,各問題の点数は100000以下.
同点の場合は,番号の若い参加者の方が順位が高いとみなす.

解法

m人が選ばれたとした場合,そのm人は不確定だった問題は全て正答していて,その他の人は不確定だった問題に全て間違えたと仮定する.
その時,それぞれのウサギに着目して,そのウサギは,m人の中で最下位になるようなm人の選び方が何通りあるかを考える.
それは,着目したウサギよりも,常に順位が上になるウサギがa人いて,順位が上に慣れるウサギがb人いたら,そのa+b人の中から,m-1匹選べば良い.
ただし,着目したウサギは,順位がmより下になることはできないので,bから選べる人数は限りがあることに注意して,コンビネーションの数を足していく.

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 ll long long

class RabbitProgramming {
public:
ll getTeams(vector <int> points, vector <string> standings, int qualified, int selected) {
  int i,j,k,m,n;
  int a,b;
  ll res=0;
  ll c[55][55];
  ll mx[55], mn[55];

  c[0][0]=1; REP(j,1,55) c[0][j]=0;
  REP(i,1,55){
    c[i][0]=1; REP(j,1,55) c[i][j]=c[i-1][j-1]+c[i-1][j];
  }

  n=standings.size();
  m=points.size();

  rep(i,n) mx[i]=mn[i]=0;
  rep(i,n) rep(j,m) if(standings[i][j]=='Y'){
    if(points[j]>0){
      mx[i] += points[j];
      mn[i] += points[j];
    } else {
      mx[i] -= points[j];
    }
  }

  rep(i,n){
    mx[i] = mx[i]*55 - i;
    mn[i] = mn[i]*55 - i;
  }

  rep(i,n){
    a=b=0;
    rep(j,n) if(i!=j){
      if(mn[j] > mx[i]) a++;
      else if(mx[j] > mx[i]) b++;
    }

    k = qualified-1-a;
    if(k>selected-1) k=selected-1;
    rep(j,k+1) res += c[a][selected-1-j] * c[b][j];
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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