Hatena::Grouptopcoder

shnyaの参戦記録

2011-03-31【本番】TopCoder SRM 501

×--

0点だったけど、問題がシンプルなのにやりがいがあって面白かったです。

難度もDPの練習に丁度良くて、こういう問題をもっと解けば確実に力がつきそうだと思えました。

SRM 501 Div1 Easy FoxPlayingGame 00:03  [http://www.topcoder.com/stat?c=problem_statement&pm=11284&rd=14430:title=SRM 501 Div1 Easy FoxPlayingGame] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11284&rd=14430:title=SRM 501 Div1 Easy FoxPlayingGame] - shnyaの参戦記録

問題概要

Fox Cielさんは次のようなボードゲームを考えました。

・プレイヤーはスタート地点からA移動をnA回、B移動をnB回行うことができます。

・A移動を一度行うと、現在のスコアにscoreA分加算され、B移動を行うと現在のスコアをscoreB倍することができます。


最適な移動方法を考えてください。

ただし、次の制約があります。

0 <= nA <= 50
0 <= nB <= 50
-100000 <= paramA <= 100000
-2000 <= paramB <= 2000
scoreA = paramA / 1000.0
scoreB = paramB / 1000.0

考えたこと

DPでいこう! 漸化式書いた。いける! あれ?無理。

scoreAとscoreBってマイナスの値取ることあるんか。。。

あれ、わからんようになった。とりあえず全探索書いてみる。

これをDPに・・・うーん。

とりあえず確信はないけど、ヒューリスティクスを入れた嘘解答で提出。

チャレンジされた。やっぱり。。。


ということで後で書き直したコード。

maxとminの両方の状態を覚えておけばよかったのかー。

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(x) memset(x, 0, sizeof(x))

class FoxPlayingGame
{
  double scoreA, scoreB;
  int nA,nB;
  long double dp[52][52][2];

public:
  double theMax(int nA1, int nB1, int paramA, int paramB)
  {
    nA = nA1+1;
    nB = nB1+1;
    CLR(dp);
    scoreA = paramA / 1000.0;
    scoreB = paramB / 1000.0;
    REP(i,nA) REP(k,2) if(i > 0)
      dp[i][0][k] = dp[i-1][0][k] + scoreA;

    REP(i,nA) REP(j,nB) if(j > 0 && i > 0) {
      dp[i][j][0] = max(dp[i-1][j][0]+scoreA,
                        max(dp[i][j-1][1]*scoreB,
                            dp[i][j-1][0]*scoreB));
      dp[i][j][1] = min(dp[i-1][j][1]+scoreA,
                        min(dp[i][j-1][0]*scoreB,
                            dp[i][j-1][1]*scoreB));
    }

    return dp[nA1][nB1][0];
  }
}

FoxAverageSequence 00:03  [http://www.topcoder.com/stat?c=problem_statement&pm=11340&rd=14430:title=FoxAverageSequence] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11340&rd=14430:title=FoxAverageSequence] - shnyaの参戦記録

問題概要

A[0],A[1],...,A[N-1]A[N]からなるなシーケンスを考えた時、

次の条件を満たす時、美しいシーケンスであると考えます。

1. シーケンスの各要素が、0<=A[i]<=40からなる

2. シーケンスの各要素が、その前までのシーケンスの平均よりも小さい

3. シーケンスのどの3つの連続する要素を選択しても、A[i]>A[i+1]>A[i+2]を満たさない


-1 <= seq[i] <= 40であるシーケンスseqが与えられた時、-1の値を適切な値に置き換えることによって美しいシーケンスを完成させてください。


考えたこと

プラクティスで解きました。

問題的には見るからにDP

総和をDPの状態として取るのは思いついたけど、3の条件を考えるためにseq[i-1],seq[i-2]の値も覚えておくようにするとTLE

フラグだけでいいんだと気付いて、システムテスト通りました。

これも漸化式を思いつけるようにならないとなぁ。。

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

int dp[50][2501][50][2];

bool is_minus(int k, int l){
  if(k < l)
    return 1;
  else
    return 0;
}

bool check(int i, int j , int k, int l, int sum){
  if((i > 1 && (l == 1 && k > j)) || (double)j > (double)sum/i)
    return false;
  else
    return true;
}

class FoxAverageSequence
{
  vector<int> seq;
  const static int mod = 1000000007;

  int rec(int i, int sum, int k, int l){
    if(i == SZ(seq)) return 1;
    if(dp[i][sum][k][l] != -1) return dp[i][sum][k][l];
    int res = 0;
    if(seq[i] == -1){
      REP(j,41){
        if(check(i,j,k,l,sum)){
          res += rec(i+1,sum+j,j,is_minus(j,k));
          if(res > mod) res -= mod;
        }
      }
    }else{
      if(!check(i,seq[i],k,l,sum)){
        return dp[i][sum][k][l] = 0;
      }else{
        res += rec(i+1,sum+seq[i],seq[i],is_minus(seq[i],k));
        if(res > mod) res -= mod;
      }
    }
    return dp[i][sum][k][l] = res;
  }

public:
  int theCount(vector <int> seq1)
  {
    memset(dp,-1,sizeof dp);
    seq = seq1;
    return rec(0,0,50,0);
  }
}