perogram

No.411 昇順昇順ソート

Quiz

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

Submit

https://yukicoder.me/submissions/341357

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

f:id:peroon:20190421161636j:plain

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

K=1の場合

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

f:id:peroon:20190421165054j:plain