ABC076 D - AtCoder Express

問題ページ
D: AtCoder Express - AtCoder Beginner Contest 076 | AtCoder

考えたこと

各区間で場合分けして見ていくのを考える。サンプルを見ていると無限に場合分けがありそうで確実にバグらせるのでやめる。
現在の速度を持っておいて1秒ごとにシミュレーションしていき、速度を+1 or キープ or -1の中でできる速度を最大にするものを選択すればよさそうと思って実装する。このタイミングで速度をプラス(キープ)して次の速度までに下げきれるかを判定する。
サンプル4で引っかかって0.5秒ごとのシミュレーションに変更。もっと細かくしないといけないパターンが存在しないか考えたがなさそうだったのでこれで提出するとWA。
速度を変更するところで次の速度だけを見てるがそれだともっと先の区間に間に合わないパターンが存在する事に気づいた。制約を見返すとさらにもう一個Nが掛かっても何とかなりそうなので速度の更新パートにO(N)掛けることにして実装して投げたら通った。

実装面倒だなーと思ったけど考察したらそうでもなかった。

解法

現在の速度を持ちつつ、0.5秒ごとにシミュレーションして速度の更新を行う。速度の更新をするときにプラス(キープ)した後にマイナスをし続けても間に合わない区間が先に存在する時はプラス(キープ)が行えない。したがって現在可能な最大の速度を持ちつつ、これまでに走った最長の距離を求めていく。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int t[210], v[210];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> t[i];
  REP(i, n) cin >> v[i];

  double ret = 0, sp = 0;
  REP(i, n) {
    for(double j=0; j<t[i]; j+=0.5) {
      bool flag1 = true, flag2 = true;
      double ti = t[i]-j-0.5;
      FOR(k, i+1, n) {
        ti += t[k];
        if(sp+0.5-ti > v[k+1]) flag1 = false;
        if(sp-v[k+1] > ti) flag2 = false;
      }
      if(sp+0.5 <= v[i] && flag1 && (sp+0.5-(t[i]-j-0.5)) <= v[i+1]) {
        ret += sp*0.5;
        ret += 0.125;
        sp += 0.5;
      } else if(sp - v[i+1] <= t[i]-j-0.5 && flag2) {
        ret += sp*0.5;
      } else {
        sp -= 0.5;
        ret += sp*0.5;
        ret += 0.125;
      }
    }
  }
  cout <<fixed << setprecision(15) << ret << endl;

  return 0;
}