問題へのリンク

状況

コンテスト中解けず．ACまで結局3時間かかった．

解説を読んで

「辞書順最小の良い整数列」を一度に求めようとしたので話を複雑にしてしまった．

  • 良い整数列を全部求める
  • その中で辞書順最小のものを決める

と考えるべきだった．

[1] のように問題が与えられた時，[2] のように後ろから最適な場所をマークしていく． [3] の青線が，良い整数列の全部になる．この際，前の段階で「最適」とは言われなかったところも 良い整数列として現れていることに注意． もっとも下にある青線の列が答となる．