Edit

【pythonでABC173を解説】D - Chat in a Circle

問題概要

問題ページ

D - Chat in a Circle
D - Chat in a Circle

問題ページへ移動する

問題文

あなたはオンラインゲーム「ATChat」のチュートリアルを終え、その場に居合わせたプレイヤー \(N\) 人で早速とある場所を訪ねることにしました。この \(N\) 人には \(1\) から \(N\) の番号が振られており、人 \(i\ (1 \leq i \leq N)\) の フレンドリーさ は \(A_i\) です。

訪ねる際、\(N\) 人は好きな順番で \(1\) 人ずつ到着します。あなたたちは迷子にならないために、既に到着した人たちで環状に並び、新たに到着した人は好きな位置に割り込んで加わるというルールを決めました。

最初に到着した人以外の各人は、割り込んだ位置から到着した時点で「時計回りで最も近い人」と「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい 心地よさ を感じます。最初に到着した人の心地よさは \(0\) です。

\(N\) 人が到着する順番や割り込む位置を適切に決めたとき、\(N\) 人の心地よさの合計の最大値はいくらになるでしょう？

制約

  • 入力はすべて整数
  • \(2 \leq N \leq 2 \times 10^5\)
  • \(1 \leq A_i \leq 10^9\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = sorted(list(map(int, input().rstrip('\n').split())))
    dq = collections.deque([a.pop()])
    t = 0
    while len(a):
        s = a.pop()
        dq.appendleft(s)
        dq.appendleft(s)
        t += dq.pop()
    print(t)


if __name__ == '__main__':
    solve()

-Edit
-