AOJ : 2298 - Starting Line

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2298
日本語の問題文があるので, 説明省略です.

アルゴリズム

効率よく解こうとすると非常に面倒なので, 1メートルごと進みながらシミュレートするのがラクかと思います.
この問題で, 一番気を付けなければならないケースは, 親切にもサンプルの2番目に入れてくれているので, これさえ通ればACできるでしょう.

やらかしたミス

• 読解ミスして, タイムロス
• 1メートルごとシミュレートできないと思って, ごちゃごちゃなコードを書こうとしていた.

プログラム

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

int main(void){
  int n,k,t,u,v,l;
  int d[202];
  bool flg[10002]; //ある位置に人参があるかどうか

  while(cin>>n>>k>>t>>u>>v>>l){
    memset(flg,0,sizeof(flg));
    rep(i,n){
      cin>>d[i];
      flg[d[i]] = true;
    }

    int pos = 0; //現在の位置
    int rem = 0; //速さvで進める残り距離
    int hav = 0; //現在持っている人参の数
    double ans = 0;

    while(pos < l){
      if(flg[pos]){
        if(hav == k){
          rem = t * v;
        }
        else{
          hav++;
          if(rem == 0){
            rem = t * v;
            hav--;
          }
        }

        ans += 1.0 / v;
        rem--;
        if(rem == 0 && hav > 0){
          rem = t * v;
          hav--;
        }
      }
      else{
        if(rem > 0){
          ans += 1.0 / v;
          rem--;
          if(rem == 0 && hav > 0){
            rem = t * v;
            hav--;
          }
        }
        else{
          ans += 1.0 / u;
        }
      }

      pos++;
    }

    printf("%.7f\n",ans);
  }
}