Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM494 DIV1 MEDIUM/DIV2 HARD - AlternatingLane (この記事を編集する[管理者用])

Source

TopCoder SRM494 DIV1 MEDIUM (500pt)
TopCoder SRM494 DIV2 HARD (1000pt)
Problem Statement
SRM494 DIV1 自分の参加記録

問題概要

n本 (50以下) の木の高さの分布が与えられる.
それぞれの分布はa[k]以上b[k]以下 (a[k], b[k]は100000以下) の整数を等確率に取るような分布.
木の高さが与えられたとき,以下でスコアを定める.そのスコアの期待値を求める問題.
 Alternatingとは,木の高さAが順番に大きくなって小さくなって (または,小さくなって大きくなって) となること,つまり
  A[0] > A[1] < A[2] > A[3] < … または A[0] < A[1] > A[2] < A[3] > …
 Alternatingな木の高さに関しては,スコアは隣合う木の高さの差の絶対値を足した物,つまり
  |A[0]-A[1]| + |A[1]-A[2]| + |A[2]-A[3]| + …
 Alternatingじゃない木の高さに関しては,好きな数だけ木を無視して,Alternatingな木の高さにしたときのスコアの最大値

解法

木を取り除くとしたら,極値を取る木以外を取り除くのが最適で,それは取り除かなかったときのスコアと同じになる.
結局,期待値の線形性より,隣り合う2つの木に対して,その高さの差の期待値を別々に求めて全部足してやれば良い.
愚直にO(100000^2)は間に合わないので,等差数列の和の公式を使って上手く計算するとか,何か工夫が必要.
以下は,隣合う木の高さの差がiとなる場合の数を数え上げて計算している.

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 ab(int x){if(x<0) return -x; return x;}

class AlternatingLane {
public:
double expectedBeauty(vector <int> A, vector <int> B) {
  int i,j,k,n;
  int up, down, x, y, dist, tmp;
  double res = 0, xy;

  n = A.size();
  REP(k,1,n){
    up = B[k] - A[k-1];
    down = A[k] - B[k-1];

    x = B[k]-A[k]+1;
    y = B[k-1]-A[k-1]+1;
    xy = x*(double)y;

    REP(i,down,up+1){
      dist = ab(i-down);
      tmp = ab(i-up); if(dist > tmp) dist = tmp;

      dist++;
      if(dist > x) dist = x;
      if(dist > y) dist = y;

      res += ab(i) * (double)dist / xy;
    }
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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