概要

この問題は、条件を満たすように警備員を撤収する操作コストの最小値を求める問題です。
しかし、実は何も操作しないことが常に最適です。

考察

まず重要なのは、操作は「\(0\) 回以上」行えるという点です。
つまり、必ずしも警備員を撤収する必要はありません。

初期状態では、すべての街灯に警備員が \(1\) 人ずつ配置されています。

このとき、条件を確認します。

条件1: 残った警備員が \(2\) 人以上

制約より \(N \geq 2\) です。
初期状態では警備員は \(N\) 人いるので、必ず \(2\) 人以上います。

条件2: 残った警備員全員が安心条件を満たす

街灯 \(i\) に警備員がいるとします。

安心条件は、

• 時計回りに \(\lfloor N/2 \rfloor\) 個先の街灯
• 反時計回りに \(\lfloor N/2 \rfloor\) 個先の街灯

のうち、少なくとも一方にも警備員がいることです。

初期状態ではすべての街灯に警備員がいるので、当然これらの街灯にも警備員がいます。

例えば、

• \(N\) が偶数の場合
  時計回りと反時計回りの \(\lfloor N/2 \rfloor\) 個先は同じ街灯ですが、その街灯にも警備員がいます。

• \(N\) が奇数の場合
  時計回りと反時計回りの先は異なる街灯ですが、どちらにも警備員がいます。

したがって、初期状態のままで安心条件も必ず満たしています。

コストについて

操作をしなければ、コストの合計は \(0\) です。

また、各操作のコストは撤収した警備員の費用の最大値であり、費用 \(A_i\) はすべて \(1\) 以上です。
したがって、操作コストは常に \(0\) 以上であり、合計コストが \(0\) より小さくなることはありません。

つまり、最小コストは必ず \(0\) です。

素朴に「どの警備員を残すか」を探索しようとすると、選び方が非常に多くなり、\(N \leq 10^6\) では現実的ではありません。
しかし、この問題では「操作をしない」という選択肢が常に条件を満たすため、そのような探索は不要です。

アルゴリズム

1. 入力を受け取る。
2. 何も操作しない場合、条件を必ず満たす。
3. よって答えは常に \(0\)。
4. \(0\) を出力する。

計算量

• 時間計算量: \(O(N)\)
  入力として \(A_1, A_2, \ldots, A_N\) を読む必要があるためです。
• 空間計算量: \(O(N)\)
  掲載コードでは配列 \(A\) に入力を保存しているためです。
  ただし、値を使わないので読み捨てれば \(O(1)\) にできます。

実装のポイント

この問題では、撤収費用 \(A_i\) の値は答えに影響しません。
入力だけ正しく読み取り、常に 0 を出力すればよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<long long> A(N);
    for (auto &x : A) cin >> x;

    cout << 0 << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。