素数に関する定理で、面白いものを見つけたのでメモ。 自然数 について、素数全体の集合を と置くとき、 表題の定理の場合は が素数 となっています。 が素数でないときの、 で割った余りがいくつになるかも、ひと手間加えれば示せるので、先のような書き方…

今回は競技プログラミングに関する記事です。 以前 Prim Jarnik 法に関する記事を公開したのですが、間違えた内容であることが分かったので内容を修正した記事となります。その節はご迷惑をおかけしました。 もうひとつの最小全域木生成アルゴリズムである K…

競プロのアルゴリズムです。 契機としてはこちら。 atcoder.jp 定理本体の説明や、数学的証明はこちら参照。 manabitimes.jp algo-logic.info ざっくりいうと、 を前計算 、クエリ で計算することができるアルゴリズムです。ただし は素数。 素朴に実装する…

練習問題としてはこことか、こことか。 atcoder.jp atcoder.jp 一般に桁 DP でぐぐると、「桁を一個一個みていく DP だよ！」みたいな記事を見かけがちですが、冒頭の問題のように「 以下の」といった条件がある場合、文面通り桁だけ見ていくと条件を満たし…

(2022/05/28 追記) 当記事は内容に誤りがあります。 修正版の記事を公開したのでそちらをご参照ください。 なお、記事中紹介している Python スクリプト自体は正しい Prim Jarnik 法のものとなっております。もしスクリプトをコピーされてしまっている場合で…

今日は競技プログラミングに関する記事です。 最小全域木という、なかなか聞きなれない単語ですが、「ある無向グラフがあって、その辺の一部だけを選んで残して木にしたもののうち、もっとも辺のコストの総和が小さいもの」のことを指します。 ひどい実装を…

今回は競技プログラミングに関する記事です。 以前、グラフのノード間の最短距離を求めるアルゴリズムとしてこちらの３つをご紹介いたしました。 グラフ系アルゴリズム：ダイクストラ法 - katoufujiBanana’s blog グラフ系アルゴリズム：ベルマン・フォード…

今回は競技プログラミングに関する記事です。 初めてみたとき、アルゴリズム名から何をやってるのかよくわからなかったアルゴリズム、ダブリングのご紹介です。 ある関数 が定義されており、 の値はいくらか、というのを計算する際に効力を発揮するアルゴリ…

今回は競技プログラムの記事です。 前回、Python の二分探索用の標準ライブラリ bisect をご紹介いたしました。 Python の bisect を使えば、リストの長さが とかになっても対応可能です。計算量が なので指数の肩が増えるくらいなら計算速度的には大丈夫で…

本日は競技プログラミングの記事です。 突然ですが、ソート済みのリストの要素のうち、 以下（もしくは 未満）のもののうち、最大の要素が格納されているインデックスを求めたい、となった場合、どう求めるのが良いでしょうか？ 素朴に書くとこんな感じでし…

今日は競技プログラミングの記事です。今回は、アダマール変換です。 このアルゴリズムは、ビットの排他的論理和（xor）で畳み込みをすることができます。 wikipedia でのアダマール変換の説明はこちらです。 注意点として、wikipedia の定義では正規化係数…

今日は競技プログラミングの記事です。今回は、ゼータ変換・メビウス変換を使った畳み込み計算の高速化です。 ゼータ変換とメビウス変換は競プロ界隈の中でも、何をゼータ変換と呼び、メビウス変換と呼ぶかが、どうもふんわりしているようです。 なので、当…

今日は競技プログラミングの記事です。あまり畳み込みの分野は詳しくないのですが、数学とか工学では頻出な感じがする離散フーリエ変換です。 ある長さ のリスト について、 となるような、長さが のリスト を求めることを考えます。愚直にやると計算量は 程…

ないしは、それに相当する、いくつかの不偏ゲームを複数個同時並列でプレイするような不偏ゲームの必勝法について。 今回は競技プログラムに関する記事です。 katoufujibanana.hatenadiary.jp こちらの記事の続編です。Grundy 数などの説明は前回の記事に書…

今回は競技プログラミングの記事です。 グラフの中の任意の２点間の最短距離を求められるアルゴリズム、ワーシャル・フロイド法（Floyd–Warshall Algorithm）のご紹介です。日本語と英語で逆なんですねー。 過去にご紹介したダイクストラ法や、ベルマン・フ…

今回は競技プログラミングの記事です。 グラフのある１点から、他のすべての点への最短距離を求められるアルゴリズム、ベルマン・フォード法（Bellman–Ford algorithm）のご紹介です。 ダイクストラ法では、グラフのすべての辺のコストが非負である必要があ…

今回は競技プログラミングの記事です。 グラフのある１点から、他のすべての点への最短距離を求めらえれるアルゴリズムである、ダイクストラ法（Dijkstra's algorithm）のご紹介です。ご存じな方も多いと思いますが、ダイクストラ法が適用できるグラフは、辺…

今回は、ちょっと難しいアルゴリズム、全方位木（Rerooting）に関する記事です。 全方位木を使うと、たとえば「与えられた木の各ノードについて、そのノードから最も遠いノードとの距離をすべて求めなさい」という問題を解くことができます。 もう少し抽象的…

今回は競技プログラミングの記事です。たびたび AtCoder のコンテストで見かけることのある Grundy 数と、それを使った不偏ゲームの必勝法の有無の判定についてです。 概念の説明が主な記事なので、説明文が多めです。スクリプトとしては、記事の真ん中のあ…

当ブログにて、区間クエリ系の問題で使えるデータ構造について、４つのデータ構造をご紹介しました。それぞれの記事へのリンクはこちらです。 区間クエリ：累積和、累積積、etc... - katoufujiBanana’s blog 区間クエリ：Binary Indexed Tree - katoufujiBan…

区間クエリ系、第四弾。Lazy Segment Tree（通称：遅延セグ木）です。 仕組みについては、外部記事をたくさん読んでください。めちゃめちゃむずいです。 通常の Segment Tree では更新が１点のみしかできませんが、Lazy Segment Tree では区間の更新が Segme…

今回は、区間クエリ系アルゴリズム（データ構造）第三弾、Segment Tree です。 今までにご紹介した累積和や、Binary Indexed Tree では、逆元の存在しないような演算には太刀打ちできませんでした。 ※ 過去の記事はこちら katoufujibanana.hatenadiary.jp ka…

今回は、アルゴリズム（というよりデータ構造の方が正しい？）の、Binary Indexed Tree（別名：BIT 木、フェニック木）のご紹介です。 こちらのアルゴリズムは、以前の記事 katoufujibanana.hatenadiary.jp と同じく、区間和や区間積などなどを高速に計算で…

今日は、競プロのアルゴリズム系の記事で、累積和（および、それに類似したもの）のご紹介です。 累積和を使う問題の典型例は、以下のような問題です。 個の自然数 が与えられる。 その後、 個の自然数 と、 個の自然数 が与えられるので、 以上 以下の自然…

今回は素因数分解のアルゴリズムです。 エラトステネスの篩を使った高速化なしのものと、ありのものの二本立てとなります。 katoufujibanana.hatenadiary.jp エラトステネスの篩に関する記事はこちら。 まずは、高速化なしの方の実装です。 import math def …

今回は、素数に関するアルゴリズムのうちの基礎中の基礎、エラトステネスの篩です。 唐突ですが、ある自然数 に対し、 が素数であるか否かの判定は で計算することができます。 以下証明です。 が素数でない場合、つまり が 以外の自然数 で割り切れる場合、…

以前の記事で、deque を使った深さ優先探索と幅優先探索の python スクリプトや、再帰関数をつかった深さ優先探索の行きがけと帰りがけの python スクリプトをご紹介しました。 deque による深さ優先探索は、前回の記事では行きがけの実装のみの記載となって…

タイトルには DP と付けましたが、どちらかというと計算のメモ化の色が強いです。 今回は、あると便利なフィボナッチ数、階乗、組み合わせ数の計算スクリプトをご用意したので記事にいたします。 コンテストに参加していると、ふとした瞬間に「階乗を計算す…

先日書いた記事の katoufujibanana.hatenadiary.jp にて、グラフ上のある２点が接続しているかどうかの判定アルゴリズムとして、Union-Find の名前を出しましたが、どのようなアルゴリズムだったかは触れなかったので今回は Union-Find を取り上げます。 ま…

今回は巡回セールスマン問題（Traveling Salesman Problem: TSP）のコードを書きます。グラフ上のすべてのノードをめぐる最小距離を求める問題です。どちらかというとグラフの探索アルゴリズムというよりかは、DP 的側面の強いアルゴリズムという印象。 素朴…