AtCoder ABC 173 D - Chat in a Circle (400点)

解き直し予定問題

優先度付きキュー使って解く

考察履歴（コンテスト中）

降順ソートして、大きい値から環につっこんでいくのが良さそう

大嘘考察（コンテスト中にやった）

数列の和をとって、最小値を引く。これでサンプルは通ってしまう。全然違う

大きい値から環にどうやって挿入していくのが良いか考える

環をどのようなデータ構造で表現できるか？

などを考えたかったがわからず時間切れ

考察履歴（解説動画観ながら）

https://www.youtube.com/watch?v=IMwigbYzLbI&feature=youtu.be

降順ソートして、大きい値から環に追加していことが最適解の１つとなる

動画ではその証明をしていたが理解できず

環への追加は二分木で表現することができる

要素の左右いずれかにしか、要素を追加することができないため、高々2回したスコアに影響できない

ただし、1要素目のみは特殊。1要素目追加時は、その値しかいないため、1回しかスコアに影響できない

実装は優先度付きキューを使っても良い

解説動画はforと変数制御で実現していた

code:rust

use std::io::*;

use std::str::FromStr;

fn read<T: FromStr>() -> T {

let stdin = stdin();

let stdin = stdin.lock();

let token: String = stdin

.bytes()

.map(|c| c.expect("failed to read char") as char)

.skip_while(|c| c.is_whitespace())

.take_while(|c| !c.is_whitespace())

.collect();

token.parse().ok().expect("failed to parse token")

}

fn main() {

let n: usize = read();

let mut a: Vec<u64> = (0..n).map(|_| read()).collect();

//降順ソート

a.sort_by(|x, y| y.cmp(x));

let mut ans: u64 = 0;

//足せる回数の初期値設定

let mut t = n-1;

//大きい順に到着していく

for i in 0..n{

//足せる回数の設定、1人目のみ1回になる

let mut lim = 2;

if i == 0 {

lim = 1;

}

//足せる分だけ足す

//n-1まで到着を処理するが、足し込んでいるのはt>0となっている場合まで

for _ in 0..lim{

if t > 0 {

t -= 1;

}

}

}

println!("{}", ans);

}

もっとdiff高いと思いたかった。。