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

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

ソースコード📃