Python | ページ 12

[Python] ABC007 D 桁DP

ABC007 Dを桁DPを使って解きます。桁DP/Digit DP 「n以下の整数の処理」を考えるときに、大きい桁から一桁ずつ数を見ていき、結果を代入するDP配列に、nより小さいことが確定しているかどうかのフラグを含めることで状態を管理する動的計画法で...

問題 C - 幅優先探索幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根...

問題 B - 辞書式順序入力例/出力例と同じ値になるようにしてみる。組み込み関数の chr(i) と ord(c) を使う。回答 A = input() lst_a = list(A) if len(lst_a) >=2: pr...

問題 A - 植木算植木算は算数の文章題、またその解き方の一種。線の上に乗っている数を計算して数える。長さを数えるなど。出典: フリー百科事典『ウィキペディア（Wikipedia）』回答 n = int(input()) print(n-1)...

クヌース–モリス–プラット法クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を...

以下の続きです。下の動画を参考にしています。決定性有限オートマトンを使うと、文字列検索アルゴリズムは以下の流れで表現できます。オートマトンを作るあるパターン\( P \)が与えられたとして、そのパターンに...

ラビン-カープ法テキストの中からパターンを探すときに、パターンのハッシュと検索箇所のハッシュが一致するかどうかを比較して検索を行います。ハッシュの時間計算量が \(O(m)\) の場合は、アルゴリズム全体の計算量が \(O(m \times n) \) ...

与えられた文字列の中から、パターンに一致する部分を総当たりで探します。時間計算量は \( O(n \times m) \)、空間計算量は\( O(1) \) になります。 import random import string def match_pa...

内挿探索 2分探索ではリストの中央の値を基準として探索を行いますが、内挿探索は、この基準の決め方を工夫することで、探索をより効率的に行おうとする検索方法です。要素が均一に分布している場合は、内挿探索は平均して\(log（log（n））\)、最悪の場合、最大...

2分探索二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。出典: フリー百科事典『ウィキペディア（Wikipedia）』ソート済みのリストにおいて、目標との中央...