[問題案] partially retroactive priority queue

[maspypy]

雰囲気問題文

priority queue に対する操作の列 (op0, op1, ..., op{N-1}) を考える はじめ、op[i] は「何もしない」である

Q クエリを処理し、処理するたびに、空な prique に対して (op0, op1, ..., op{N-1}) を行った最終結果の情報を出力せよ。

1 t x: op[t] を (push x) に変更 2 t: op[t] を (pop min (if the priority queue is non-empty)) に変更 3 t: op[t] を「何もしない」に変更

要検討

• 「「何もしない」である」みたいな書き方が妥当か。
• 空な prique に pop min を行った場合は？（エラー・無視どちらでも解ける）学術的に一般的な認識があれば合わせたいけど雑に調べただけだと分からず
• 「最終結果の情報を出力せよ」これは、高々 1 要素入れ替わるだけなので大体何でも答えられますが。sum だけでいいかな。

[maspypy]

https://x.com/maspy_stars/status/1814715828480454925

[NyaanNyaan]

「(無視した場合の解, エラーの有無) を両方出力する」に 1 票入れたいです。 フローを使用した実装であればエラーの有無は容易にわかるので、両方の出力を要求されても困らないと思っています。(他の実装ではどうなんだろう…)

最終結果は sum に 1 票です。

[maspypy]

最終状態の要素数がとれるならpop失敗回数は適当な足し引きで出るので、 (cnt,sum) を出力させるというはどうでしょうか。そっちの方が問題文が簡潔になりそう。