ARC080 E: Young Maids

arc080.contest.atcoder.jp

解き方

• 辞書順なので、先頭から埋める
  • 最初の数列で、奇数番目が解答の先頭に、偶数番目が解答の2番目にくる
    • 奇数番目の最小の数字が先頭に、それより後ろで最小の偶数番目が2番目にくる
  • 3つの領域に分割されるので、それらについて同じように考える
• ある領域の中で最小の数字を見つけるのはセグメント木（RMQ）
• いくつかの領域のなかで奇数番目が最小の領域を見つけるには、priority_queueを使う

ハマったところ

• 最小の領域を見つけるのに、priority_queueを使わずmin_elementを使用
  • いい加減O(n)のSTLを使ってTLEはやめたい
• セグメント木の実装をコンテスト中にバグらせずにやるのは時間が足りない
• 不要なところを埋めるmaxに10^5を使っていた。
  • 1e7とか書くと浮動小数点になるから嫌だなぁと思っていたけど、わかりやすさのためには使った方が良い気がする

github.com