Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Qual. 1 MEDIUM - RobotSimulation (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Qualification Round 1 MEDIUM (500pt)
Problem Statement

問題概要

上下左右に動く命令列(命令列は10命令以下)と,その命令列を行う回数が与えられる.
そのとき,たどり着くマス目の数を求める問題.同じマスに2回以上たどり着いても1回とカウントする.
回数は1億以下.

解法

新しく辿りつけるマス目の数は,命令セットを何回か実行すると収束するので,後はまとめて処理する.
最初の10回ぐらい真面目に計算したらあとはまとめて良い.

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 d[2000][2000];

class RobotSimulation {
public:
int cellsVisited(string program, int times) {
  int i,j,k,tm;
  int res=0, add;
  int sx=1000, sy=1000;

  rep(i,2000) rep(j,2000) d[i][j]=0;
  d[sx][sy]=1; res++;
  
  rep(tm,min(20,times)){
    add=0;
    rep(i,program.size()){
      if(program[i]=='U') sx++;
      if(program[i]=='D') sx--;
      if(program[i]=='L') sy++;
      if(program[i]=='R') sy--;
      if(!d[sx][sy]) d[sx][sy]=1, add++;
    }
    res += add;
  }

  res += add * (times-tm);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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