ARC108E

https://gyazo.com/455722a2c76a9cb48d1f29febf4ea080

コンテスト中は手付かず

考えたこと

たとえば1,4,2,3の時に、先に4を選んでしまうと2,3は選べなくなる

端から「選んだ場合、選んでない場合」で場合わけしていくと2^2000になる

1を選ばなかった場合でも最終的に選ぶ羽目になるから頭から決めていくのは微妙？

極大な単調増加列を見つける必要がある？

先頭からではなく小さい方から決める？

違いそう

足し算の順序の変更かなー

各数値についての「最終的に選ばれるかどうか」は「自分より左の自分より大きい数が自分より先に選ばれてるかどうか」

左の大きい数が全部でx個ある時に1/(1+x)と考えて良い？

良くない、4,2,3の時、2が選ばれる確率は1/2ではなく2/3

3が選ばれた時に4は選べなくなるから

公式解説

これを区間DPだと思いつくことがまったくできなかった