残念ながら本番では通せなかったです。わかってしまえばなんてことないんですけどねぇ。
問題
https://codeforces.com/contest/1304/problem/D
問題概要
長さnの順列があり、その順列に関して、隣り合う項目の大小関係を不等号で示す長さn-1の文字列が与えられる。
与えられた大小関係を満たす順列で、LIS (longest increasing subsequence)が最小になるものと最大になるものを一つずつ示せ。
考察
まずは最小となるものを考えることにします。
できるだけ大きい数字を左に置いたほうがよいことは明らかです。もちろんLISを最小とするということは増加部分列を短くしなければなりません。 ですので、単調減少部分を左から詰められるだけ詰めてしまえばよいということになります。
例えばサンプルの2番目>><>><で考えてみます。
最初は減少なので大きいものから詰めていきます。
> > < > > < 7 6
3番目の項目から増加が始まるので、一旦保留して、次に減少が始まる4番目からさらに埋めていきます。
> > < > > < 7 6 ? 5 4 ? ?
7から下って4まで確定しました。
次に減少部分を埋めていきます。左が大きい方がよいので、一番左の?は4の次、3です。
> > < > > < 7 6 3 5 4 ? ?
最後に2つ分の増加列があるので、ここは1, 2です。
> > < > > < 7 6 3 5 4 1 2
このサンプルだとちょっとわかりにくいので、もう一例<<<>><<でやってみます。
まず減少部分を埋めます。
< < < > > < < ? ? ? 8 7 ? ? ?
一番左の増加列は3つ分あって、ここまで8, 7と消費しているので右端を6にしたいです。なので、4から6までで埋めます。
< < < > > < < 4 5 6 8 7 ? ? ?
最後に3つ残っているので、1から3までで埋めます。
< < < > > < < 4 5 6 8 7 1 2 3
いかがでしょうか？
LISを最大にする方も、同じような考え方で、左をできるだけ小さく、単調増加部分を左から詰められるだけ詰めていけばよいです。
とりあえず自分の実装です。→Submission #71282947 - Codeforces
もっと簡潔に書ける気はします。
