Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM598 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

2人でゲームを行う.最適に行動した時,先手必勝か後手必勝か,永遠に決着がつかないかを判定する問題.
無限に長い一直線上で戦う.
最初,座標 $0$ に先手が,座標 $d$ に後手がいる.
先手の移動力は $M_1$,射程は $R_1$,後手の移動力は $M_2$,射程は $R_2$ である.
各ターン,
 移動力以下だけ離れた場所に移動し,相手キャラまでの距離が射程以下だと勝ち
ということを繰り返す.

解法

$1$ ターン目で先手が勝つ,$2$ ターン目で後手が勝つは,判定しておく.
$2$ ターン目までで決着がつかないなら,移動力が高い方しか勝つ可能性はない.勝てないなら逃げられるから.
移動力が高い方は,好きなように相手との距離を詰めることができる.
近づきすぎると負けるので,相手の移動力 $+$ 射程より $1$ だけ離れた場所に行き,相手が全力で離れた後,$1$ ターンでトドメがさせるかどうかを判定すれば良い.
それができないなら,引き分け.

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

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

#define ll long long

int solve(ll mov1, ll mov2, ll rng1, ll rng2, ll d){
  ll i, j, k;

  if(d <= mov1 + rng1) return 1;
  if(mov1+d <= mov2 + rng2) return -1;

  if(mov1 > mov2){
    if(mov1 + rng1 > mov2 + mov2 + rng2) return 1;
  }

  if(mov2 > mov1){
    if(mov2 + rng2 > mov1 + mov1 + rng1) return -1;
  }

  return 0;
}

class FoxAndFencing {
public:
string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d) {
  int i;

  i = solve(mov1, mov2, rng1, rng2, d);

  if(i==1) return "Ciel";
  if(i==0) return "Draw";
  return "Liss";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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