No.411 昇順昇順ソート

Quiz

https://yukicoder.me/problems/no/411

Submit

https://yukicoder.me/submissions/341357

サンプルを理解する (N=5, K=3) K!=1の場合

• 一般的であるK!=1である場合を考える
• 下がる時に使う数字は1固定となる
• サンプルのようにK=3のときは、下がる前にK+1〜Nまでの数字を使うかどうかの自由度がある
  • 数字の数は N - (K+1) - 1 = N-K 個
  • 今回で言えば 4, 5を1で下げる前に使うかどうかの自由度がある
  • 2²通り
• そこからは1で下がって、残りの点で上がるので1通り
• よって一般に、2^N-K

K=1の場合

• サンプルとしてN=5, K=1を考えてみよう
• 今回は 2, 3, 4 で下がることができる
• 2で下がる時、下がる前に3, 4, 5のいずれかが存在する必要がある
  • 下がる前に3だけ使ってもいいし、3, 4, 5すべてを使ってもいい。3, 4, 5全てを使わないのだけはダメ
  • よって、余事象より、上記の組み合わせは2³ - 1
• 3で下がる時、下がる前に4, 5のいずれかが...（以下同様）
  • 組み合わせは 2² - 1
• 4で下がる時、〃
  • 組み合わせは 2¹ - 1
• これらの和が答えで、7 + 3 + 1 = 11 が答え。
• 一般に、2^N-1 - N となる