読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

Problem A. Bot Trust

問題概要
青と橙のロボットがある。
それぞれのロボットは別々の廊下に隔離されてテストを行う。
各々のロボットの初期値は buttun 1 である。(距離が1の場所)
各々のロボットは1秒間で上下どちらの方向かに1進むことができる、
または、指定位置にいる場合は button を押すことができる
テストを完了するために、指定された順序でbuttonを押さなければならない
テストを完了するためにかかる最短時間を求める

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define DEB 0
#define all(x) x.begin(), x.end()

int main(){
  int T;
  scanf("%d",&T);
  rep(x,T){
    char r;
    int n,p,pb=0,po=0,tmp;
    int blue=1,orange=1,ret=0;

    scanf("%d ",&n);
    rep(i,n){
      scanf(" %c %d ",&r,&p);
      if( r=='O' ){
	tmp = max(abs(p-orange)-pb,0) + 1;
	po += tmp;
	ret += tmp;
	orange = p;
	pb = 0;
      }else{
	tmp = max(abs(p-blue)-po,0) + 1;
	pb += tmp;
	ret += tmp;
	blue = p;
	po = 0;
      }
    }
    printf("Case #%d: %d\n",x+1,ret);
  }
  return 0;
}


・試行錯誤のめも
単純なシミュレーション
計算量は考える必要ない
とりあえず実装、サンプルあわない、あるぇー
アドホック修正も虚しく。んー、青と橙の総移動距離の和を求めて最大値を返せばいいんじゃね?
だめでした、待つ時間を忘れてた
Cのほうが簡単だろ、と思いつつ、手を動かすがなんかうまくいかない。
うーんうーん、整理するのへたくそだなぁ
p-orange で 距離差(ボタンは含まれてない
pb(prev_blue) が、blueのボタンを押すのにかかった時間だとすると、(これはボタン含んでる
abs(p-orange)-pb これが、必要な操作回数になる
max(abs(p-orange)-pb,1) これで、ボタンを押すのも含めた橙の時間
これを ret に加算して、橙の位置を更新し、青にかかった時間を0にする
まった、pbにボタンを押す時間を含めたらだめな気がする、え、いや、必要だろ
てきとーに修正、small通った。さすがにこのサイズだとオーバーフローしないだろ、largeも提出