Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM528 DIV1 HARD (1000pt)
Problem Statement

問題概要

N個 (50以下) の正整数が与えられる.各整数は2000以下.
整数P1, P2が与えられる.これらは50以上2000以下.
以下の操作を好きなだけやって,得られる得点の最大値を求める問題.
N個の中から異なる2つの整数を選んで,片方からP1だけ減らし,片方からP2だけ減らし,P1+P2点を得る.ただし,整数が負になってはいけない.

解法

1回の操作で得られる得点は一定なので,何回操作できるか,P1減らす,P2減らすをどのように振り分けるかを考えれば良い.
まず,操作の回数の最大値は1000.
P1減らす操作と,P2減らす操作を,別々にできるとするならば,DPで,P1をk回減らす操作を行った時,残りからP2減らす操作を行うことのできる最大値を求めることができる.
このDPはO(50*1000*2000/50)程度.
残りの制約は,P1とP2は同じ回数でなければいけないのと,同じ要素からいっぺんにP1とP2を同時に減らせないこと.
前者は簡単で,後者は,全体の操作回数がMとして,一つの要素から合計でM回以下しか減らしてないなら,適当に振り分ければ可能.
Mの値を決めつければ,DPによってそれが達成できるか判定可能なので,二分探索すれば良い.
自分の解答では,基本的に小さいケース以外は振り分けれてしまうので,Mの最大値を求めて,少しずつ減らしながら調べた.

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[1010], next[1010];

class ColorfulCookie {
public:
int getMaximum(vector <int> in, int P1, int P2) {
  int i,j,k,g,m,n;
  int mx;
  int res;

  if(P1 > P2) swap(P1, P2);
  sort(in.begin(), in.end());
  n = in.size();

  mx = 0;
  rep(i,n) mx += in[i];
  mx /= (P1+P2);
  mx += 2;

  rep(i,mx) dp[i] = -1000000000;
  dp[0] = 0;
  
  rep(k,n){
    rep(i,mx) next[i] = dp[i];
    rep(i,mx) if(dp[i] >= 0){
      for(j=0;;j++){
        if(i+j >= 1010) break;
        if(in[k] - P1*j < 0) break;
        g = (in[k] - P1*j) / P2;
        next[i+j] = max(next[i+j], g+dp[i]);
      }
    }
    rep(i,mx) dp[i] = next[i];
  }

  for(;;){
    m = 0;
    rep(i,mx) if(m < min(i,dp[i])) m = min(i,dp[i]);
    printf("%d\n",m);

    rep(i,mx) dp[i] = -1000000000;
    dp[0] = 0;
  
    rep(k,n){
      rep(i,mx) next[i] = dp[i];
      rep(i,mx) if(dp[i] >= 0){
        for(j=0;j<=m;j++){
          if(i+j >= mx) break;
          if(in[k] - P1*j < 0) break;
          g = (in[k] - P1*j) / P2;
          if(g > m-j) g = m-j;
          next[i+j] = max(next[i+j], g+dp[i]);
        }
      }
      rep(i,mx) dp[i] = next[i];
    }

    rep(i,mx) if(m <= min(i,dp[i])) break;
    if(i<mx) break;
  }

  res = m * (P1+P2);
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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