from ARC108
E - Random IS
- コンテスト中は手付かず
- 考えたこと
- たとえば1,4,2,3の時に、先に4を選んでしまうと2,3は選べなくなる
- 端から「選んだ場合、選んでない場合」で場合わけしていくと2^2000になる
- 1を選ばなかった場合でも最終的に選ぶ羽目になるから頭から決めていくのは微妙？
- 極大な単調増加列を見つける必要がある？
- 先頭からではなく小さい方から決める？
- 違いそう
- 足し算の順序の変更かなー
- 和の期待値は期待値の和的な
- 各数値についての「最終的に選ばれるかどうか」は「自分より左の自分より大きい数が自分より先に選ばれてるかどうか」
- 左の大きい数が全部でx個ある時に1/(1+x)と考えて良い？
- 良くない、4,2,3の時、2が選ばれる確率は1/2ではなく2/3
- 3が選ばれた時に4は選べなくなるから
- 公式解説