読者です 読者をやめる 読者になる 読者になる

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

AtCoder 競技プログラミング

解法

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;
}