STLやPythonで範囲指定の多くは左閉半開区間を基調にしています。しかし、std::string::substrでの範囲指定は大きく異なり、戸惑います。気が付くと実装時に繰り返し同じことを考え、無駄を感じていたのでまとめてみました。 以下はstring::substr - C++ Ref…

エラトステネスの櫛はN以下の素数を列挙するアルゴリズムとして知られています。まずは素数を列挙するナイーブな実装を行い、計算量を落としていきながらエラトステネスの櫛を考えてみることにします。次の実装の計算量はO(N2)です。 #include <iostream> #include <vector> #d</vector></iostream>…

素数を扱う簡単なアルゴリズムはO(√n)で行えます。以下の何れのアルゴリズムもO(√n)で行うことができます。 素数判定 約数の列挙 素因数分解 プログラミングコンテストチャレンジブックでは二つの式を使って簡潔に説明をしています(p. 111)。例えばnの素因数…

Codeforces # 223 Div. 2 http://codeforces.com/contest/381Codeforces # 223 Div. 2に参加。ABCが通り、2,492点。94位。部屋(Room 74)でも初めて1位となり、嬉しい回であった。レートは1,621から1,720へ。紫コーダーになった。今回のエントリではstd::lowe…