Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM501 DIV1 EASY/DIV2 MEDIUM - FoxPlayingGame (この記事を編集する[管理者用])

Source

TopCoder SRM501 DIV1 EASY (250pt)
TopCoder SRM501 DIV2 MEDIUM (500pt)
Problem Statement
SRM501 DIV1 自分の参加記録

問題概要

実数 A (-10以上10以下) と B (-2以上2以下) が与えられる.(実際にはそれを1000倍したものが整数で与えられる)
最初の得点は0.
行動の順番は自由にして良いので,ちょうどnA (0以上50以下) 回だけ以下の(1)を行う,ちょうどnB (0以上50以下) 回だけ以下の(2)を行ってできる最高点を求める問題.
 (1) 現在得点にAを足す
 (2) 現在得点にBをかける

解法

・解法1 (下のコードの1つ目)
線形性を考えると,Aを足すのはバラバラにやる意味はなくて,最適なタイミングに nA 回まとめて全部足すのが良い.
なので,Bを最初に何回かけるか,でループして,nB+1パターン全部試せば良い.
nBは2個かけると増えるか減るかはっきりするので,実は最初に何回かけるかは,0回,1回,nB-1回,nB回の4パターンのみ試せば良いのだが,nBが0のときなどに気を付けないとバグを生みやすい.

・解法2 (下のコードの2つ目)
DPする.AとBは固定して
 dp[i][j] = Aをi回足す,Bをj回かけるときの最大値と最小値
を覚えておけば良い.

・解法3
Aの正負,Bの正負,Bの絶対値が1以上かどうか,で8パターン場合分けして,それぞれgreedyにやる.
慎重に書かないと,きっとどのパターンかでバグ入れて間違える.

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

class FoxPlayingGame {
public:
double theMax(int nA, int nB, int paramA, int paramB) {
  int i;
  double A, B, res = 0, tmp;

  A = paramA / 1000.0;
  B = paramB / 1000.0;

  tmp = A;
  for(i=0;i<=nB;i++){
    res = max(res,tmp);
    tmp *= B;
  }

  return res;
}

};
// #includeとusing namespace std;は略

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

double A, B;
double dp1[66][66], dp2[66][66];
int vis[66][66];

void solve(int a, int b){
  int i,j,k;
  double res1 = -1e100, res2 = 1e100, tmp;

  if(a==0 && b==0){
    dp1[a][b] = dp2[a][b] = 0;
    return;
  }
  if(vis[a][b]) return;
  vis[a][b] = 1;

  if(a){
    solve(a-1,b);
    tmp = dp1[a-1][b] + A;
    if(res1 < tmp) res1 = tmp;
    if(res2 > tmp) res2 = tmp;
    tmp = dp2[a-1][b] + A;
    if(res1 < tmp) res1 = tmp;
    if(res2 > tmp) res2 = tmp;
  }

  if(b){
    solve(a,b-1);
    tmp = dp1[a][b-1] * B;
    if(res1 < tmp) res1 = tmp;
    if(res2 > tmp) res2 = tmp;
    tmp = dp2[a][b-1] * B;
    if(res1 < tmp) res1 = tmp;
    if(res2 > tmp) res2 = tmp;
  }

  dp1[a][b] = res1;
  dp2[a][b] = res2;
}

class FoxPlayingGame {
public:
double theMax(int nA, int nB, int paramA, int paramB) {
  int i,j;

  A = paramA / 1000.0;
  B = paramB / 1000.0;
  rep(i,66) rep(j,66) vis[i][j] = 0;

  solve(nA, nB);
  return dp1[nA][nB];
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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