CODE FESTIVAL 2015 あさぷろ Hard A: 一次元オセロ

問題

code-festival-2015-morning-hard.contest.atcoder.jp

解法

1回もひっくり返されない区間iが存在する。この時、区間i-jと区間i+jは、それぞれj回ひっくり返されるので、ある区間を選んだ時にひっくり返される合計の回数は累積和で予め計算しておくことが出来る。

ゲームの性質上、必ず全て白になった状態でゲームは終了するので、1回もひっくり返されない白区間を全探索して最小値を求めれば良い。

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  vector<ll> imos1(A);
  for (int i = 1; i < N; ++i) {
    imos1[i] += imos1[i - 1] + 1;
  }
  for (int i = 1; i < N; ++i) {
    imos1[i] += imos1[i - 1];
  }

  vector<ll> imos2(A);
  for (int i = N - 2; i >= 0; --i) {
    imos2[i] += imos2[i + 1] + 1;
  }
  for (int i = N - 2; i >= 0; --i) {
    imos2[i] += imos2[i + 1];
  }

  ll ans = 1000000000000000000;
  for (int i = 0; i < N; ++i) {
    if (i % 2 == 1) continue;
    ll sum = 0;
    if (i > 0) sum += imos1[i - 1];
    if (i < N - 1) sum += imos2[i + 1];
    ans = min(sum, ans);
  }
  cout << ans << endl;
}