競プロっておいしいの?(仮)

vs. ABC 062 D - 3N Numbers

だからお前はだめなんだ。

はい。なんかとても悲しい気分のNafmoです。

priority_queueを使うとても素晴らしい問題に出会った気がした。

戦うほどのことはしていないが、とりあえず。

D: 3N Numbers - AtCoder Beginner Contest 062

本番でときたかった難易度な気がしてならない

完全に考察と発想で勝てる...と思ってる

問題概要

  1. 3Nの長さの数列が投げられる。
  2. 前からN個後ろからN個取る
    ここで、クロスして取ることはできない(1 3&2 4など)
  3. 前の総和-後ろの総和 を最大にして

ソートして幸せになりたい!!!!(TLEです)

毎回ソートするという考えしか浮かばず死亡。

解法

  1. 境目を決める。前と後でとる境目をN<=k<=2Nでスライドして
    すべてのkに於いてもとめる
  2. で、前の和はなるべく大きく。後ろの和は小さくしていく。
  3. 前N個の和をpriority_queue(大きい方が先に出る)にぶっこむ
    その和を変数に保持しておく
  4. 次の値をpushする。和を更新する(足す)
  5. キューの中で一番小さいものを抜く。和を更新する(引く)
  6. 後ろについても同じことをする。
  7. 後ろからN個の和をキュー(小さいほうが先に出る)にぶっこむ。同じく和を保持
  8. 4をやる
  9. 5と同じように、popして、一番大きいものを抜く
  10. 対応しているところの和で大きいものを出す。

注意事項。

int → long long int に気をつけて

INFの大きさ気をつけないと死ぬ

おわり。

ソース。Submission #1338045