Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM285 DIV1 MEDIUM - RobotTesting (この記事を編集する[管理者用])

Source

TopCoder SRM285 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

長さ50以下の命令列が与えられる.ロボットはそれ命令を1つずつ行って,最後の命令の後には最初の命令を行う.
命令は,上下左右のどれかに1マス移動せよ,というもの.
最初,N*Nの盤面のどこかにロボットが等確率でいるものとする.
命令は,50000ステップ行うか,盤面から外に飛び出すまで,実行する.
実行される命令数の期待値を求める問題.
Nは1000以下.

解法

今,どの命令を実行中か,今いる場所はどこか,を状態としてDPすると,状態数が最大で50*1000*1000となって駄目.
問題文にベタに書かれている数字50000が実は小さいということに気づけばOK.
各ステップごとに,上下左右にどれだけ,余裕があれば今までの全コマンドが実行されているかを考えれば解ける.

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

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

class RobotTesting {
public:
double estimateCommands(int N, string program) {
  int tm, dx, dy;
  int x_min, y_min, x_max, y_max;
  double res=0;

  // 現在の場所は,初期位置からのどれだけずれてますか?
  dx=dy=0;

  // まだはみ出して止まってない初期位置の長方形の四隅の座標
  x_min=y_min=0; x_max=y_max=N-1;

  // 5万回,シミュレート
  rep(tm,50000){
    if(x_min > x_max || y_min > y_max) break; // もう全ての初期値が止まってる
    
    if(program[tm%program.size()]=='D') dx++;
    if(program[tm%program.size()]=='U') dx--;
    if(program[tm%program.size()]=='R') dy++;
    if(program[tm%program.size()]=='L') dy--;

    // はみ出した分の長方形を削る
    if(dx+x_min <  0) res += (tm+1)*(y_max-y_min+1), x_min++;
    if(dx+x_max >= N) res += (tm+1)*(y_max-y_min+1), x_max--;
    if(dy+y_min <  0) res += (tm+1)*(x_max-x_min+1), y_min++;
    if(dy+y_max >= N) res += (tm+1)*(x_max-x_min+1), y_max--;
  }

  // まだ止まってないのは5万回で止まる
  res += 50000.0 * (x_max-x_min+1) * (y_max-y_min+1);

  return res/N/N;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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