AGC030 B - Tree Burning - ferinの競プロ帳

考えたこと

まず部分点を取りに行く
木を燃やすときにi番目が燃えているがi-1番目を燃やさずに飛ばすような方法はない
状態がN^2個で収まりそう
dp[反時計回りにi個燃やした][時計回りにj個燃やした] = (かかる最大の時間) みたいなDPをしたい
遷移を考えると最後にいた頂点がiとjのどちらなのかわからないと移動にかかる時間がわからない
dp[i][j][k(=iとjのどちらにいるかを0/1で表す)] とする
dpの初期状態は dp[1][0][0] = x[0], dp[0][1][1] = l-x[n-1] からスタートする
このdpの遷移は
- chmin(dp[i+1][j][0], dp[i][j][0] + x[i] - x[i-1]) (iからi+1に反時計回りに移動)
- chmin(dp[i+1][j][0], dp[i][j][1] + x[i]+l-x[n-j]) (jからi+1に反時計回りに移動)
- chmin(dp[i][j+1][1], dp[i][j][1] + x[n-j] - x[n-j-1]) (jからj+1に時計回りに移動)
- chmin(dp[i][j+1][1], dp[i][j][1] + x[i-1] + l - x[n-j-1]) (iからj+1に時計回りに移動)
dpの添字は1-index、木の座標は0-indexで持っていることに注意
かなり遷移がややこしくて30分かけてしまったが部分点が通る
満点解法について考える
反時計→時計→反時計→…と交互に切り替えていくような移動をするのが強そう
これを使ってDPではなく貪欲をするのが第一感
常に交互に切り替えていくのはサンプル1がすでに反例
実験していると一旦交互に切り替える動作に入った後に同じ向きに進む動作に戻ることはなさそう
証明を考えていると反例が見つかった気がしたのでこの方針をやめる(が、実はこれが想定解法)
向きを切り替える前にどこまで進むかを貪欲に決められるみたいなのを考えるけどだめ
円環だと考えにくいのでどこか1箇所で切って直線にすることを考える
どこかの区間[x[i], x[i+1]]は1回も通らないので直線として考えて問題ないはず
直線にして実験していると最適な進み方は高々2通りしかないような気がしてくる
切る位置O(N)通りに対してO(N)かけていたらTLEなので無理
差分を持ってがんばって計算していくのをがんばって考えていたが実装が詰めきれない
-----解説を見た-----
一度移動する向きを交互に切り替え始めたら同じ方向に移動することはない
つまり反時計→時計→時計、時計→反時計→反時計という移動が最適になることはない
証明はここが詳しい AGC 030 B 公式解説の証明 - プログラミング初心者がRubyでAtcoderのBeginnerContestを解いていく
以上の移動パターンを含まないような移動方法は以下の2パターン
- 反時計→反時計→…→反時計→時計→反時計→時計→…
- 時計→時計→…→時計→反時計→時計→反時計→…
反時計、時計で移動し続けるときにどこの木まで移動するかを決めうち、残りの交互移動にかかる時間を高速に求められれば解ける
木iまで反時計で移動したあとに交互移動にかかる時間を求める
i→n-1→i+1→n-2→i+2→n-3→… と移動していくことがわかる
かかる時間は (x[i] + x[n-1]) + (x[n-1] + x[i+1]) + … = x[i] + x[i+1] + x[i+1] + x[i+2] + x[i+2] + … + x[n-1] + x[n-1] + x[n-2] + x[n-2] + … となる
区間和なので累積和等で高速に計算できる形をしている
よってこれは解ける
実装上のテクとして反時計回りで移動し続ける場合の答えを計算する部分さえ書いてしまえば時計回りで移動し続ける場合の答えは入力のX[i]を反転し反時計回りで移動し続ける場合と同様に計算することで求められる

証明のときにぼんやりとした命題で考えていたが反時計→時計→時計、時計→反時計→反時計を含むことがないとちゃんとはっきりとした命題に言い換えて考えるべきだった。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#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()
 
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); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll l, n;
  cin >> l >> n;
  vector<ll> x(n);
  REP(i, n) cin >> x[i];

  if(n == 1) {
    cout << max(x[0], l-x[0]) << endl;
    return 0;
  }
  
  ll ans = 0;
  auto solve = [&](){
    vector<ll> a(x);
    FOR(i, 1, n) a[i] += a[i-1];
    vector<ll> b(x);
    REP(i, n) b[i] = l-b[i];
    for(ll i=n-2; i>=0; --i) b[i] += b[i+1];
    
    // 木iまで反時計回りで進んだ後交互に往復する
    REP(i, n) {
      ll dist = x[i];
      if(n-i > 1) {
        // [i, i+(n-i-1)/2]
        dist += (a[i+(n-i-1)/2] - (i==0?0:a[i-1])) * 2;
        if((n-i)%2) dist -= x[i+(n-i-1)/2];
        dist -= x[i];
        // [n-(n-i)/2, n-1]
        dist += b[n-(n-i)/2] * 2;
        if((n-i)%2 == 0) dist -= l - x[n-(n-i)/2];
      }
      chmax(ans, dist);
    }
  };

  solve();
  reverse(ALL(x));
  REP(i, n) x[i] = l-x[i];
  solve();

  cout << ans << endl;

  return 0;
}