Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM266 DIV1 EASY (300pt)
TopCoder SRM266 DIV2 MEDIUM (550pt)
Problem Statement

問題概要

未知なる1次元の世界がある.
最初,探査機が0の場所で止まっていて
 進み始めろ (正の方向に)
 進む向きを変えろ
 止まれ
の3つのコマンドを送ることができる.
また,探査機は生物を見つけると,生物を見つけましたという合図を送ってくる.
ただし,通信には双方向ともdelayだけ時間がかかる.
ちょうど生物がいる場所に探査機を止めたい.
今,得られている情報だけから,最悪ケースを想定して,最小時刻で探査機を止める戦略をとる.
生物のいる場所が与えられたとき,探査機が止まる時間を求める問題.
速度は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)

class ExploringEuropa {
public:
int travelTime(string surface, int delay) {
  int i,k;
  int tm, place;
  int res=INT_MAX, tmp;

  // 動き始めた時刻をt=0として, 動き始めるまでの時刻はreturnする時に足します (コード書くとき忘れてた)

  // 折り返して, 左に進んでいる最中に新しいVを発見することはないので, 
  // 最初のVを発見して 折り返す間までに発見したしたV全てに対して, 最小でどの時刻で止まることができるかを調べて, その最小値を求めます.

  // 何故これで良いかというと(ここからの3行分の説明は以下のソースを見て考えてからの方がわかりやすい),一番最短時間で止まれる場所は,最初に見つかったVからdelayだけ進んだ先にVがあるとき.
  // それ以前にVがあっても,そこに止まろうとしてREVERSE命令送ることはないので,判断を保留してると思えば良い.
  // また,もっと先のVに止まるのが最適になるなら,一番最初に出くわしたVが最適な場所であって,REVERSE命令を送っても大丈夫だから.

  rep(k,surface.size()) if(surface[k]=='V') break; // 最初に見つかったVの位置, これを発見したと探査機がわかると即座にREVERSE命令が出される

  rep(i,surface.size()) if(surface[i]=='V'){ // iに止まるために必要なな時刻をtmpに代入して, resを更新する
    if(i > k+2*delay) continue; // このVの上を探査機は歩いてないから, 未発見

    // tm    は surface[i]のVが見つかった知らせが届く時刻
    // place は 時刻tm での探査機の場所 (ただしまだ右向きに動いているなら, 折りかえす地点で対称に折りかえした先の場所)
    tm    = i + delay;
    place = k + (k+4*delay - tm);   // 場所kに時刻k+4*delayに戻ってくるはずなので

    // 即座にstop命令を送っても, iを通りすぎちゃう場合, すぐREVERSE命令を送って, そのあと良い感じにSTOP命令をおくる (通りすぎちゃう時間分だけまってSTOP命令を出す)
    if(place - delay <  i) tmp = tm + delay + i-(place-delay);

    // そうでなければ, iにぴったり止まれるようになるタイミングでSTOP命令を送る
    if(place - delay >= i) tmp = tm + delay + (place-delay)-i;

    // 上の2つの場合は tmp = tm + delay + abs(place-delay-i); とまとめれるけど, 解説のためこう書いただけです

    // 最小値の更新
    if(res > tmp) res = tmp;
  }

  // 最初に動き始めるまでの時間delayを足す
  return res+delay;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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