Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM469 DIV1 MEDIUM - TheMoviesLevelTwoDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM469 DIV1 MEDIUM (500pt)
Problem Statement
SRM 469 自分の参加記録

問題概要

映画が20個以下あって,各映画に盛り上がる場所が1箇所ずつある.
最初のテンションは74で,1分ごとに1減る.
盛り上がる場所をみた瞬間,テンションが47上がる.
テンションが-0.5になったら寝て,もう起きない.
映画を見る順番を自由に選んで,完走できる映画数を最大化したい.
そのような映画の順番を求める問題.複数個解があるなら辞書順で最も速い問題を求める問題.

解法

ビットDP.
今まで見た映画の集合から今のテンションが一意に定まること,見れなかった映画は後で辞書順に追加することなどに注意.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

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

int dp[1111111], next[1111111];
int len[22], tmm[22], n;

int solve(int mask){
  int i,j,k;
  int st;
  int res=0,nex=-1,tmp;

  if(dp[mask]>=0) return dp[mask];

  st=74;
  rep(i,n) if(mask&1<<i) st+=47-len[i];

  rep(i,n) if(!(mask&1<<i)){
    if(st+47 < len[i]) continue;
    if(st < tmm[i]) continue;

    tmp = solve(mask|(1<<i)) + 1;
    if(res<tmp) res=tmp, nex=i;
  }

  dp[mask]=res; next[mask]=nex;
  return dp[mask];
}

class TheMoviesLevelTwoDivOne {
public:
vector <int> find(vector <int> length, vector <int> scary) {
  int i,j,k;
  vector <int> res;
  int used[100];

  n=length.size();
  rep(i,n) len[i]=length[i], tmm[i]=scary[i];
  rep(i,1<<n) dp[i]=-1;

  solve(0);

  rep(i,n) used[i]=0;

  k=0;
  while(next[k]!=-1){
    res.push_back(next[k]); used[next[k]]=1;
    k |= (1<<next[k]);
  }
  rep(i,n) if(!used[i]) res.push_back(i);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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