典型とは 一般の人気・最新記事を集めました - はてな (original) (raw)

狭義単調増加な整数列を広義単調増加な整数列として扱う

http://codeforces.com/contest/1437/problem/E の部分問題を考えます概要としては，ある整数列 aaa が与えられ，「要素を一つ選び，任意の整数に置き換える」という操作を繰り返して aaa を狭義単調増加な数列に変えるために必要な操作回数の最小値を求める問題です例えば a=3,4,4,7,9,8,10,11a = \{3, 4, 4, 7, 9, 8, 10, 11\}a=3,4,4,7,9,8,10,11 なら三回の操作で a=3,4,5,7,8,9,10,11a = \{3, 4, 5, 7, 8, 9, 10, 11\}a=3,4,5,7,8,9,10,11 とできてこれが最小回数です自明な考察としてそのまま（狭義） LISLISLIS をとってそれ以外に対して操作をするということが考えられますが…