Codeforces 1000B Light It Up

http://codeforces.com/problemset/problem/1000/C

問題概要

時間 0,a1,a2,...,aN,M のタイミングで明かりがON,OFFを繰り返す.

ここで最大1個,タイミングを増やすことができる.

明かりがついている時間を最大化せよ.

解法

onの区間にXを挿入する

a_i-2 [off] a_i-1 [on] a_i [off] a_i+1

のような区間を

a_i-2 [off] a_i-1 [on] X [off] a_i [on] a_i+1

とすることを考えると,このときの明かりがついている時間の合計は,Xを挿入する前の状態を考えて

(a[i]より左側のonの時間) - 1 + (a[i]より右側のoffの時間)

となる.なぜなら,なるべくonの区間を長くしようとするとX = (a_i) - 1となるからである

offの区間にXを挿入する

a_i-2 [on] a_i-1 [off] a_i [on] a_i+1

のような区間を

a_i-2 [on] a_i-1 [off] X [on] a_i [off] a_i+1

とすることを考えると,このときの明かりがついている時間の合計は,Xを挿入する前の状態を考えて

(a[i - 1]より左側のonの時間) + (a[i - 1]より右側のoffの時間) - 1

となる.なぜなら,なるべくonの区間を長くしようとするとX = (a_i - 1) - 1となるからである

Xの挿入する区間がonかoffかはindexの偶奇によって決まるので,それを実装してやれば良い.

source code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int N;
i64 M;
vector<i64> A;

int main(){
  cin >> N >> M;
  A.resize(N + 2);
  A[0] = 0;
  rep(i,1,N) cin >> A[i];
  A[N + 1] = M;

  vector<i64> on;
  vector<i64> off;
  on.push_back(0);
  off.push_back(0);
  rep(i,1,N + 1){
    if(i % 2 == 1){
      on.push_back(A[i] - A[i - 1] + on.back());
      off.push_back(off.back());
    }
    else{
      off.push_back(A[i] - A[i - 1] + off.back());
      on.push_back(on.back());
    }
  }

  i64 ans = on.back();

  rep(i,1,N){
    if(i % 2 == 1){
      ans = max(ans , on[i] - 1 + off.back() - off[i]);
    }
    else{
      ans = max(ans , off.back() - off[i - 1] - 1 + on[i]);
    }
  }
  cout << ans << endl;
}

こういう問題をきれいに早く実装したいなぁ...