概要

操作を一度も行わないことが許されているため、初期状態が条件を満たしているかを確認します。初期状態ではすべての街灯に警備員がいるので、常に条件を満たしており、答えは必ず \(0\) です。

考察

この問題では、警備員を撤収させる操作を \(0\) 回以上行えます。つまり、何もしないという選択肢も認められています。

初期状態を確認します。

• 街灯は \(N\) 個あり、各街灯にちょうど \(1\) 人ずつ警備員がいます。
• 制約より \(N \geq 2\) なので、最初から警備員は \(2\) 人以上います。
• すべての街灯に警備員がいるため、任意の街灯 \(i\) について、
  • 時計回りに \(\lfloor N/2 \rfloor\) 個先の街灯
  • 反時計回りに \(\lfloor N/2 \rfloor\) 個先の街灯

のどちらにも警備員がいます。

したがって、初期状態の時点で安心条件を満たしています。

また、操作コストは撤収させた警備員の費用の最大値であり、費用 \(A_i\) はすべて \(1\) 以上です。そのため、操作を行えばコストは \(0\) 以上になります。

すでに条件を満たしている状態から、わざわざコストを払って操作する必要はありません。
よって、最小コストは常に \(0\) です。

素朴に「どの警備員を残すか」を探索すると、残す集合の候補が非常に多くなり、\(N \leq 10^6\) では到底間に合いません。しかし、この問題では初期状態がすでに条件を満たすことに気づけば、探索は不要です。

アルゴリズム

1. 入力を読み捨てる。
2. 答えとして \(0\) を出力する。

操作を一度も行わない場合、撤収コストの合計は \(0\) です。
この状態で条件を満たしているため、これが最適解です。

計算量

• 時間計算量: \(O(N)\)
  入力を読み込むためです。判定自体は \(O(1)\) です。
• 空間計算量: \(O(N)\)
  sys.stdin.buffer.read() により入力全体を一度読み込んでいるためです。

実装のポイント

条件分岐や配列の解析は不要です。

import sys

def main():
    sys.stdin.buffer.read()
    print(0)

if __name__ == "__main__":
    main()

入力内容に関係なく、答えは常に \(0\) になります。

ソースコード

import sys

def main():
    sys.stdin.buffer.read()
    print(0)

if __name__ == "__main__":
    main()

---

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