Python3で解く AtCoder Beginner Contest 173 D - Chat in a Circle

どういう時に最大値を取るのかがわかれば、実装自体は簡単

概要

問題

1. 人ユーザーがいる。
2. はi番目のユーザーのフレンドリーさ。
3. 円陣をつくる。
4. 円陣を作った時に両隣のユーザーのうちフレンドリーさが低い方の値が心地よさとなる。
5. 最適な順番かつ場所に円陣に全てのユーザーが加わったときに心地よさの最大値は？

解くときに考えた内容

• 隣り合うユーザーの低い方なので、割り込むユーザーはその時点で最大の値にしたい。
  （[1, 2, 3, 4, 5]のときに、[5, 3]の状態に4を割り込ませると心地よさは3になるが、[5, 4]なら3を割り込ませれば4となるので）
• そう考えるとまずリストを降順でソートして大きいものからpopしていくのが良さそう。
• ただどのように足していくかを考える必要がある。
• [8, 7, 6, 5, 4, 3, 2, 1]などだと、[8, 7, 7, 6, 6, 5, 5]のようになるようにするのイメージとなる。

円陣にユーザーを最適に配置していく時の心地よさが計算されるイメージ

• きちんとした証明になっていないかもだが、その時点で最適の値をとるには、
  • 最大値をまず円陣に加える。
  • その次に大きい値を円陣に加える。
  • ３つめまではそれでよい。
  • ４つめは３つのうちどこを選ぶかということになるが、その時点で割り込めるうちで両隣の小さい値が最も大きい場所を選ぶことが心地よさの合計が最も大きくなる。
  • 同順（[8, 7, 6, 6, 6, 5, 4, 3]）がある場合は、上記の選択でその時点で割り込めるうちで両隣の小さい値が最も大きい場所が6である割り込み先がいくつか出てくるがその時は別にどこを選んでも結果は変わらない。
  • 以上をコードに起こす。

コードに起こす時のポイント

• 心地よさ計算用のキューを用意する
• １つめは心地よさの評価の対象になるのは１回。
  • １つめは先にキューに入れておいてforに入った時に吐き出す。
• １つめ以外は最大２回心地よさの評価の対象になる。
  • これはある値が入った時にその両脇に割り込んで来た時に評価の対象になるため
  • 実装的にはキューに同じ値を２回appendする。
• forの回転数はrange(1, n)のn-1回。
  • 円陣に入る１人目は心地よさを得ることができないので。

---

コード

from collections import deque

n = int(input())
a = [int(x) for x in input().split()]
ans = 0
a.sort(reverse=True)
q = deque([])
q.append(a[0])
for i in range(1, n):
    ans += q.popleft()
    # ここを現状最大を2回加えることがポイント（両脇分）
    q.append(a[i])
    q.append(a[i])
print(ans)

---