2020年3月31日AtCoder剰余, 動的計画法, 数え上げ, 逆元, 木DP, 部分木, 階乗

問題へのリンク

問題概要

木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。

制約\(2 \leq N \leq 1000 \)
考え方前提: ...

2020年3月30日グラフグラフ, 重み付きグラフ

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。

ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。

負の辺が含まれていても動作する
負の閉路がある場 ...

データ構造配列, Trie木, 文字列, prefix

Trie木は、効率的な検索(retrieval)のために使われるデータ構造です。文字列などの先頭部分(接頭辞: prefix)の共通部分を共有して保存することで、\(O(M)\) での検索を可能にします。(文字列の長さを\(M\) と ...

数学全探索, 素因数分解, 約数の個数, 平方数, 平方根

Nが自然数の2乗で表現できるとき、平方数と言います。

平方数の例4 (= 2×2)
9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム

全探索でのアルゴリズム ...

数学約数, 素因数分解, 約数の個数

素因数分解を用いることで、約数の個数を簡単に求めることができます。

アルゴリズム

Nの約数の個数:

N を素因数分解する
それぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる

AtCoder二項係数, Lucasの定理, 偶奇性, パスカルの三角形, 差の絶対値

問題へのリンク

問題概要

1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する。

\(x_{1,j} := a_j\) ...

グラフグラフ, 貪欲法, 最小全域木, プリム法

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月23日グラフグラフ, 貪欲法, クラスカル法, 最小全域木

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

数学二項係数, 動的計画法, パスカルの三角形

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)

数学剰余, 二項係数, Lucasの定理, 素数の剰余, 偶奇性

Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。

アルゴリズム

Lucasの定理をそのまま利用したアルゴリズム:

\({}_{n_i}\mathrm ...