2023-03

競技プログラミングを勉強している中で、二次元のグリッドを使った問題と度々出会います。解いた問題の備忘録も兼ねて、問題とその解法についてまとめておきます。

高校数学の場合の数でよく見る、二次元のグリッドの道順総数を解く問題を扱います。この問題を解くための３つのアルゴリズムを紹介します。 3つのアルゴリズムとして、動的計画法・メモ化再帰・重複順列を取り上げます。重複順列では数字が大きくなっても対応できるよう、逆元というテクニックについても紹介しています。

二分探索の応用問題の一つとして、条件を満たす値のうち最大のものを探索する問題があります。 これに関連するいくつかの問題を取り上げ、判定と範囲の絞り込みの考え方を紹介します。