この記事ではOR演算、XOR演算を用いた全探索をPythonで実装していきます。一緒に例題を解きつつOR演算、XOR演算を使った全探索について理解しましょう。 OR演算、XOR演算の出力表 OR演算 XOR演算 例題 問題文 制約 実装 まとめ OR演算、XOR演算の出力表 それ…

本記事では、半分全列挙をPythonで実装していきます。実際に一緒に問題を解きながら半分全列挙を理解しましょう。 半分全列挙とは 例題 問題文 制約 実装 まとめ 半分全列挙とは 半分全列挙は、その名の通り個の要素を半分に分けてそれぞれを全列挙し、半分…

AtCoderのような競技プログラミングの世界では数学的知識が求められる問題が存在します。本記事ではその中でも頻出の数学的知識とその知識を使って解ける問題を列挙しました。Pythonでの実装例も合わせて載せています。 基数変換 基数変換とは「ある進数で表…

本記事ではエラトステネスの篩（ふるい）をPythonで実装していきます。実際に問題を解きながらエラトステネスの篩の動きを確認していきましょう。 エラトステネスの篩とは 例題 問題文 制約 実装 まとめ エラトステネスの篩とは エラトステネスは古代ギリシ…

この記事では累積和と尺取り法を駆使することで解ける問題をPythonで実装していきます。それぞれのアルゴリズムについての説明はこの記事では省略しますが、別記事で解説していますので累積和と尺取り法についてまず知りたいという方は以下にリンクを載せて…

競技プログラミングではしばしば数学の知識が問われる問題が出されることがあります。今回は高校で習う余弦定理を利用して解ける問題をPythonで解いていきます。 余弦定理 例題 問題文 制約 実装 まとめ 余弦定理 余弦定理は一言で説明すると2つの辺の長さと…

本記事では順列全探索をPythonで実装していきます。Pythonではitertoolsを使うことで簡単に順列を生成することができます。 順列全探索とは 例題 問題文 制約 実装 まとめ 順列全探索とは 順列全探索とは通りの順列の組み合わせを全探索する手法です。例えば…

この記事では競技プログラミング等で頻出のアルゴリズムである「動的計画法」をナップサック問題を通して解説していきます。まず動的計画法についての解説をしてから、実際にナップサック問題をPythonで解いていきます。 そもそも動的計画法（DP）とは ナッ…

本記事ではダイクストラ法の全体的な流れを確認したあとに実際に例題をPythonで解いていきます。ダイクストラ法の基本的な考え方は貪欲法です。最短距離でいけるところを選んで距離をひたすら更新していきます。

この記事では、Pythonで平方根の計算の精度を上げる方法を記します。Pythonで平方根の計算をただすること自体は難しくありません。例えば以下のように”**”を使う方法や print(2**0.5) #1.4142135623730951 numpyを用いて求める方法もあります。 import numpy…

AtCoderなどの競技プログラミングではコーディングのスピードは非常に重要視されます。そこで本記事では、コーディング時間を短縮するためにスニペットを利用する方法について紹介します。 (adsbygoogle = window.adsbygoogle || []).push({}); 実行環境 拡…

この記事ではタイトルにある通りbit全探索の問題をひたすら解いていきます。bit全探索自体の解説は以下の記事を参照してください。 nashidos.hatenablog.com 例題1（難易度：茶） 問題文 実装 例題2（難易度：茶） 問題文 実装 例題3（難易度：緑） 問題文 …

この記事ではPythonを使って動的計画法(DP)の問題を解いていきます。本記事ではこれから動的計画法の勉強を始める入門者向けに解説していきます。動的計画法のイメージをつかむために簡単な問題を解いていきますので、がっつりDPを勉強をしたい人にとっては…

この記事ではPythonを使ってランレングス圧縮（RLE）を実装していきます。ランレングス圧縮はデータ圧縮アルゴリズムの一種でRLE(Run Length Encoding)とも言われます。連続したデータを、ひとつ分のデータと連続した長さで表現します。たとえば「AAABBCCCCA…

しゃくとり法は以下のような時に使えるアルゴリズムです。〇〇を満たす区間 (連続する部分列) のうち、最小or最大の長さを求めよ、〇〇を満たす区間 (連続する部分列) を数え上げよ。左端と右端のインデックスを条件に合わせて適切に動かすことによって最適…

この記事では区間スケジューリング問題をPythonを利用して解いていきます。区間スケジューリング問題はソートと貪欲法を利用することによって解くことができます。貪欲法を知らない方はまずこちらの記事をお読みください。 nashidos.hatenablog.com (adsbygo…

今回は幅優先探索をPythonで実装していきます。本記事では、幅優先探索の基本的な最短経路を求める問題と少し応用的な問題を解いていきます。 幅優先探索(BFS)とは 例題１ 実装 例題２ 実装 まとめ 幅優先探索(BFS)とは 幅優先探索(BFS)はBreadth First Sear…

本記事では、深さ優先探索をPythonを利用して実装していきます。実際に深さ優先探索の典型問題をスタックと再帰関数の2パターンの解き方で実装し、解説していきます。 深さ優先探索(DFS)とは 例題 問題文 再帰関数で実装 スタックで実装 まとめ 深さ優先探索…

今回の記事ではPythonで貪欲法(Greedy Algorithm)を実装していきます。貪欲法は最適化手法の中でも基本的なアルゴリズムで比較的実装も簡単なので書けるようにしておきましょう。 貪欲法とは 例題 問題文 制約 実装 さいごに (adsbygoogle = window.adsbygoo…

今回は優先度付きキューをPythonのheapqで実装していきます。優先度付きキューとは一言で説明すると最大値、最小値を普通のリストよりも早く見つけることができるアルゴリズムです。通常のリストでは最大値、最小値を見つける計算量が(O(N))であるのにたいし…

本記事ではProgateが終わったら次にすべきことについて私自身の考えを述べていきます。Progateが終わったら次は「自分で何かを作ってみるといい」ということがよく言われますが実際のところはどうなのかについて考察していきます。 「自分で何かを作る」は正…

自分の環境では実行できるのにAtCoderで実行してみるとAttributeError:'module' object has no attribute 'gcd'と表示されて困った方もいるのではないでしょうか。私もAtCoderで初めてgcdを使った時にエラーが出てきて、対処法に困ったのでここに解決策を記…

本記事ではPythonを使って二分探索を実装していきます。二分探索とはソートされたデータを高速に探索することができるアルゴリズムです。ソートされていないものには使えないので注意してください。二分探索はその名の通り、データを2つに分けて探索するとい…

累積和とはその名の通り、累積の和をとる前処理をすることによってクエリの速度を上げることができるアルゴリズムです。実際に累積和の問題をPythonで解いていきます。どれくらい速くなるかを確認していきましょう。

bit全探索 全探索にもいろいろ種類がありますが今回はbit全探索をPythonで実装していきたいと思います。bit全探索とはその名の通りbit演算を利用して行う全探索で、Yes or Noのような2択を網羅的に探索する時に使えます。説明を聞いてもわかりにくいかもしれ…

全探索 問題 問題文 制約 実装 全探索 全探索にはbit全探索やDFSなどいろいろありますが、今回は最も簡単な基本の全探索をPythonで実装していきます。 問題 問題は ABC 051 B-Sum of Three Integersを扱います。B - Sum of Three Integers 問題文 2 つの整数…