[白俊/BOJ/2775]女性会長になりたい

1783 ワード
boj テキストリンク

2775|我是妇人会长。


問題のアクセスと設計


  • a階b号a-1階1~b号に住むサラミの数の和の人.

  • 0階i号はi名、湖は1から.

  • kは層数,nは湖

  • 2階は1階の人数、3階は2階の人数を知るべきだと思っているので、直接計算するしかありません.

  • DPの使用

  • まずアパートの0階を埋めます.
  • apt = [[_ for _ in range(1, n + 1)]]

  • スライス[:]を使用して、前の層の合計を加算する.

    • 使用するスキル


    時間の複雑さ

  • は、重複するテストケース
    • を含まない.
  • オーバーラップfor:O(n 2)
  • sum : O(n)
    • O(n3)

    改善する


  • DPも再帰も長い時間がかかるO(n 3)

  • 短い符号化コードを参照すると,組合せの性質を用いて解くのは簡単であることが分かった.
  • 時間の複雑さはよくわかりませんが、組み合わせも工場を使っているので、時間がもっと長いです.
    • 現在のコード:68ミリ秒
    組合せ使用:84 ms
  • の組み合わせを使用するコードは、
    • です.
    import math

..

print(math.comb(k+n, n-1))
    組み合わせの性質では、パスカルの三角形にホッケー棒のパターンがあります.これはそれを利用した解答で、説明すると
    パスカルの三角形では、上の2つの数の和が下の数です.
    以下に示すように、組み合わせとして表すことができる.
    nCk = n-1Ck-1 + n-1Ck
    ここでホッケーバットの図案は
    つまり、右下の対角線方向の総和はその左側の値に等しい.

    この点を利用する.
    k+nCn-1
    この式によりk層n号の人数を計算する.

    難易度


    難易度正解率(%)ブロンズ257.364%

    アルゴリズム分類

  • 数学
  • DP

    • ソースコード📃

    210716
    [TIL] NodeJS, NPM (2021.08.24)