Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-07-22

KingdomAndTrees (SRM 548 Div2Medium, Div1Easy)

17:53 | KingdomAndTrees (SRM 548 Div2Medium, Div1Easy) - capythm@TopCoder を含むブックマーク はてなブックマーク - KingdomAndTrees (SRM 548 Div2Medium, Div1Easy) - capythm@TopCoder KingdomAndTrees (SRM 548 Div2Medium, Div1Easy) - capythm@TopCoder のブックマークコメント

問題概要

N本の木が直線上に立っている。木の高さを昇順になるようにしたい。

魔法使いは木の高さを-level~+levelの範囲で変化させることができる。

昇順にするための最小レベルはいくつか?

http://community.topcoder.com/stat?c=problem_statement&pm=11967

解法

二分探索を使います。

あるレベルの時に昇順にできるかどうかの判定方法(関数check)は以下のような感じです。

  • 木を先頭から見ていく。
  • 現在の木をできる限り低くする。ただし直前の木より+1は高くする。
  • 魔法を使った後の木の高さと元の木の高さを比較して、今のレベル以上必要だったらNG

ソースコード

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class KingdomAndTrees{
  bool check( vector<int> h, int lev ){
    int prev = 0;
    for( int i=0; i<h.size(); i++ ){
      int curr = max( prev+1, h[i]-lev );
      if( abs( curr - h[i] ) > lev ) return false;
      prev = curr;
    }
    return true;
  }
public:
  int minLevel(vector <int> heights){
    int lo=0,hi=1000000000,ret=-1;
    while( lo <= hi ){
      int mid = (lo+hi)/2;
      if( check( heights, mid ) ){
        ret = mid;
        hi = mid-1;
      } else {
        lo = mid+1;
      }
    }
    return ret;
  }
};

Pillars (SRM 547 Div1Easy)

22:37 | Pillars (SRM 547 Div1Easy) - capythm@TopCoder を含むブックマーク はてなブックマーク - Pillars (SRM 547 Div1Easy) - capythm@TopCoder Pillars (SRM 547 Div1Easy) - capythm@TopCoder のブックマークコメント

問題概要

2本の棒が地面に立っている。棒は距離w離れている。

棒の高さはそれぞれ、1~x、1~yの範囲で一様にランダム。

棒のてっぺん同士をひもで結ぶとき、必要なひもの長さの期待値を求めよ。

http://community.topcoder.com/stat?c=problem_statement&pm=12055

解法

以下の計算式で計算できる。

 \frac{1}{xy}\sum_{i=1}^{x}\sum_{j=1}^{y}\sqrt{w^2+(j-i)^2}

x,yの範囲が1~100,000なので、単純に合計値を計算すると最大ループ回数が100000^2でTLEする。

1/xyは最後に乗算するとして、式中の総和部分だけを効率的に計算する方法を考える。

よく考えると、一方の棒の高さがiの時、もう一方の棒の高さjが低い場合と高い場合で対称っぽい感じに

なっている。要するに、

 S_i=\sum_{j=1}^{y}\sqrt{w^2+(j-i)^2}=\sum_{j=0}^{i}\sqrt{w^2+j^2}+\sum_{j=0}^{y-i}\sqrt{w^2+j^2}-w

となるので、最初に一方の棒の高さが0の場合でメモ化しておいて、あとで上式のように分解したものを

総和すると、ループ回数が最大でも100000*2になって、間に合う。

ソースコード

#include <cmath>
#include <algorithm>
using namespace std;
double s[100002];
class Pillars{
public:
  double getExpectedLength(int w, int x, int y){
    double sum=0.0;
    s[0] = w;
    if( y < x ) swap( x, y );
    for( int i=1; i<=y; i++ ) s[i] = s[i-1] + sqrt( (double)w*w + (double)i*i );
    for( int i=1; i<=x; i++ ) sum += s[i-1] + s[y-i] - w;
    return sum / ((double)x*y);
  }
};