第19回日本情報オリンピック　一次予選(第3回)

2019年11月21日
情報オリンピック日本委員会

解説

数列のすべての連続部分列について，ソート済みかどうかを判定し，ソート済みであったものの中で最長のものの長さを求めればよい．

ソート済みかどうかは，連続部分列を左端から順に見ていき，一つ右の数字との大小関係が矛盾している場所が無いかどうかを確認すればよい． 確認は O(N) ででき，連続部分列は全部で O(N²) 個あるので，全体として，O(N³) で解くことができる．

この問題ではこれ以上の高速化は要求されていないが，以下のようにもっと早く解く解法もある．

数列の各要素について，そこを左端とするソート済み連続部分列のうち最長のものを見つける方針もある．この場合，決めた左端から開始して，次の数字との大小関係が矛盾するか，数列の最後に来るまで部分連続列を伸ばしていくと，最長のものが見つかる．この操作は O(N) ででき，左端の候補は O(N) 個なので，全体として O(N²)で解くことができる．

左端のインデックスが l であるソート済み連続部分列のうち，最長のものの右端のインデックス r だったとき，左端のインデックスが l ＜ k ≦ r となるような k であるソート済み連続部分列の長さは，左端のインデックスが l であるソート済み部分列より必ず短いことがわかる．これを用いて，先程の解法の左端の候補を減らすことができる．この解法では全体として O(N) で解くことができる．