数学二項係数,動的計画法,数え上げ,重複組合せ,写像12相,スターリング数,第2種スターリング数,ベル数

条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 ...

数学動的計画法,写像12相,分割,分割数

以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。

\(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できな ...

数学分割,分割数,動的計画法,写像12相

以下の2つを混同しそうですが、ここでは \(p_k(n)\) を求めることを考えます。

\(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) ...

2020年10月23日数学数え上げ,写像12相,スターリング数,第2種スターリング数,ベル数

ベル数は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理

ベル数とは

...

2020年10月22日数学スターリング数,第2種スターリング数,数え上げ,写像12相

第2種スターリング数は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理

第 ...

動的計画法bit全探索,DP,配列,部分和問題

部分和問題とは、\(N\) 個の数 \( a_1, a_2, …, a_n\) が与えられたとき、その中からいくつかを選んで和をちょうど \(K\) にできるか判定をする問題です。

例えば配列が で、\(K\ ...

2020年5月19日その他二次元,座標圧縮

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。

仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。

例:\(0\) ~ \(10^9\) の数直線はメモリにのらない

2020年5月11日その他,その他繰り返し二乗法,競プロ,LCA,ダブリング

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において

前処理:\(O(N \log K)\) 時間, \(O(N ...

2020年5月10日探索

forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。

複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要があ ...

2020年4月13日その他圧縮,復元,ランレングス圧縮

ランレングス圧縮(ランレングス符号化)とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。

同じ文字が連続して何文字出現するかに変換します。

例:

In: aaal ...