Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM541 DIV1 EASY/DIV2 MEDIUM - AntsMeet (この記事を編集する[管理者用])

Source

TopCoder SRM541 DIV1 EASY (250pt)
TopCoder SRM541 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

蟻が50匹以下,2次元平面上を歩く.
蟻の初期位置と,歩いている方角が与えられる.
初期位置は,座標の絶対値1000以下の格子点の何処かで,方角は上下左右のどれか.
歩く速度はすべての蟻が1で一定.
2匹以上の蟻が衝突すると,その瞬間,衝突した蟻が全部消える.
最終的に残る蟻の匹数を求める問題.

解法

衝突する可能性のある時間は0.5の倍数のみ.
また,衝突する可能性のある時間は2000以下だけ.
なので,時間を0.5ずつ進めながらシミュレーションすれば良い.
(座標が大きくなると,衝突する可能性のある時間を列挙してからシミュレーション)

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 AntsMeet {
public:
int countAnts(vector <int> x, vector <int> y, string dir) {
  int i,j,k,n,tm;
  int ok[51];
  int dx[4] = {0,1,0,-1};
  int dy[4] = {1,0,-1,0};

  n = x.size();
  rep(i,n){
    if(dir[i]=='N') dir[i] = 0;
    if(dir[i]=='E') dir[i] = 1;
    if(dir[i]=='S') dir[i] = 2;
    if(dir[i]=='W') dir[i] = 3;
  }

  rep(i,n) x[i] *= 2, y[i] *= 2;

  rep(tm,5000){
    rep(i,n) x[i] += dx[dir[i]];
    rep(i,n) y[i] += dy[dir[i]];

    rep(i,n) ok[i] = 1;
    rep(i,n) REP(j,i+1,n) if(x[i]==x[j] && y[i]==y[j]) ok[i] = ok[j] = 0;

    k = 0;
    rep(i,n) if(ok[i]) x[k] = x[i], y[k] = y[i], dir[k] = dir[i], k++;
    n = k;
  }

  return n;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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