D – 大ジャンプ 解説 (AtCoder Beginner Contest 011)

問題へのリンク 問題概要 座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\) で \(D\) だけ移動する。 制約 \( 1 \leq N \leq 1000\)\(1 \leq D \leq 10^9\)\(-10^9 \leq X, Y \leq 10^9

「写像12相」で典型的な数え上げ問題のパターン総整理

条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 この記事では、ある集合からある集合へのマッピングが何通り存在するのかを考えるときに便利な「写像12相（the twelvefold way）」について紹介し、これを通じて典

自然数nをk個の0以上の整数に分割する方法の総数を求めるアルゴリズム

以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。 \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数\(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然

自然数nをk個の1以上の整数に分割する方法の総数を求めるアルゴリズム

以下の2つを混同しそうですが、ここでは \(p_k(n)\) を求めることを考えます。 \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数\(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然数 \(n\)

ベル数を求めるアルゴリズム：第2種スターリング数の和を効率的に計算する

ベル数とは ベル数とは「区別できる \(n\) 個の要素を区別できない \(k\) 個以下のブロックに分割する方法の数」のことです。 これは、第2種スターリング数を用いて表すことが可能です。 第2種スターリング数とは、区別できる \(n\) 個の要素を区別できない \(k\) 個のブロックに分割する方法の数のことで、\(S(n,k)\) などと表すことが多いです。 ベル数は、第2種スターリング数の

第2種スターリング数を求めるアルゴリズム

第2種スターリング数とは 第2種スターリング数 \(S(n,k)\) は、以下の3つの性質を持つ数です。 \(S(0,0)=1, ~ \forall i_{\geq 1}. S(i,0)=0\) として、\(S(n,k) = k S(n-1,k) + S(n-1, k-1)\) が成立する区別できる \(n\) 個の要素を区別できない \(k\) 個のブロックに分割する方法の数\(f_k(x)=x

部分和問題（N個の配列から和がKになるように選ぶ）とその解き方

部分和問題とは、\(N\) 個の数 \( a_1, a_2, ..., a_n\) が与えられたとき、その中からいくつかを選んで和をちょうど \(K\) にできるか判定をする問題です。 例えば配列が [1,3,8] で、\(K\) が 9 のときは、1,8 を選ぶと和が 9 になり K に一致します。 全探索による単純なアルゴリズムでは計算量が大きくなってしまいますが、\(K\)と \(N\) の

座標圧縮の解説（1次元から2次元の圧縮まで）

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。 仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。 例：\(0\) ~ \(10^9\) の数直線はメモリにのらない例：\(10^9 \times 10^9\) の領域はメモリにのらない このような状況では、情報を圧縮しなければ探索などを行うことができません。 情報のない空白部分が連続している場合、不要

ダブリングの基本概念とその応用

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において 前処理：\(O(N \log K)\) 時間, \(O(N \log K)\) 空間クエリ：\(O(\log K)\) で行うことができるようにするアルゴリズムです。 繰り返し二乗法もダブリングの一種と捉えることができ、最近共通祖先

D – Teleporter 解説 (AtCoder Beginner Contest 167)

問題へのリンク 問題概要 町が \(N\) 個ある。町 \(i\) から町 \(A_i\) に移動することを K 回繰り返す。町 1 から始めた時、最終的にどの町にたどり着くか？ 制約 \(2 \leq N \leq 2 \times 10^5\)\(1 \leq A_i \leq N\)\(1 \leq K \leq 10^{18}\) 考え方 単純にシミュレーションをしようとしても、\(K\)

再帰関数を用いた深さ優先探索(DFS)による全探索アルゴリズム

forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。 複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要がある場合があり、競技プログラミングなどで良く出題されています。 前提知識 今回の内容を理解するために必要なことを簡単に説明しておきます。 再帰関数とは 再帰関数を詳しく考えようとす

ランレングス圧縮と復元

ランレングス圧縮（ランレングス符号化）とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。 同じ文字が連続して何文字出現するかに変換します。 例： In: aaallgooooooOut: a3l2g1o6 圧縮(encode)する際は Run Length Encoding, 復元(decode)する際は Run Length Decoding と言います。 ア

重みが最小となる閉路を求めるアルゴリズム

アルゴリズム 最小コストの閉路： 任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除くv から u への最短経路 d を求める(ダイクストラ/BFS など)d+cost(u,v) を計算するグラフ G に e を戻すd+cost(u,v) の最小値が、閉路の重みの最小値 ※ ある辺 e を含む最小のコストの閉路を、全ての辺について求めます。 ※ 具体例では以下の様に

F – Division or Substraction 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 \(N\) が \(K\) 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような \(K\) が何通り存在するか答えよ。 \(N\) が \(K\) で割り切れる：\(N\) を \(\frac{N}{K}\) にする\(N\) が \(K\) で割り切れない：\(N\) を \(N-K\) にする 制約 \( 2 \leq N \leq 10^{12}\)

E – Yutori 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 N日間のうちK日働く。 一日働いたら、直後のC日間働けないi+1 日目は、Sの i 文字目が 'o' の時だけ働ける 必ず働く日を全て求めよ。 制約 \(1 \leq N \leq 2\times 10^5\)\(1 \leq K \leq N\)\(0 \leq C \leq N\) 考え方 「必ず働く日」や「必ず働かなくても良い日」というのは、どの

D – Lunlun Number 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ 制約 \(1 \leq K \leq 10^5\) 考え方 制約が結構重要です。小さい方から1つずつ全探索することができれば、求められそうだということが分かります。 特殊な条件を持つ数を小さい方から全探索する時（パナソニックプログラミングコンテスト2020 D -

木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。 木DP 基本的な考え方とイメージ 木DP とは、根を一つ固定した木について、以下のように部分木に関する値を利用して計算する動的計画法です。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 木が N 頂点から構成されるなら、部分木

木DPと全方位木DPの総まとめ【競技プログラミング】

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。 木DP 基本的な考え方とイメージ 木DP とは、根を一つ固定した木について、以下のように部分木に関する値を利用して計算する動的計画法です。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 木が N 頂点から構成されるなら、部分木

N – 木 解説（AtCoder Typical DP Contest）

問題へのリンク 問題概要 木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。 制約 \(2 \leq N \leq 1000 \) 考え方 前提：木DPの考え方 俗に言う、木DP を用います。木DPでは以下のようなDPを基本に考えます。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 それぞれの部分木から

ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。 ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。 負の辺が含まれていても動作する負の閉路がある場合は検出できる という利点があります。 アルゴリズム グラフ G = (V, E) に対するワーシャル・フロイド法は以下のようになります。 ワーシャル・フロイド法：（「dist[ i ][ j