C++

ベルトランの仮説（Bertrands Postulate）とは、「3より大きい任意の整数 n に対して、n と 2n−2 の間に少なくとも1つの素数 p が存在する」ことを主張する数学の定理です。素数が数直線上にどれほど密に分布しているかを示す重要な結果として知られています。ベルトランの仮説の定式化n < p < 2n − 2ここで、n は n > 3 を満たす整数、p は素数を表します。素数とは、正の約数が 1 とその数自身のみである自然数のことです。たとえば、2、3、5、7、11 などが素数の代表例です。また、ベルトランの仮説には、より扱いやすい緩い定式化もあります。n

beta()、betaf()、betal()は、C++の標準テンプレートライブラリ（STL）に組み込まれている数学関数です。これらの関数は、2つの正の実数を受け取り、ベータ関数の値を計算するために使用されます。ベータ関数は次のように定義されます。B(x, y) = ∫01 t(x−1)(1−t)(y−1) dtbeta()関数beta()関数はdouble型の値を扱うための関数です。引数としてdouble型の値を受け取り、計算結果をdouble型で返します。構文double beta(double x, double y)パラメータx：ベータ関数におけるxの値（double型） y：ベータ関数

サイズ n の整数配列があり、初期状態ではすべての要素が 0 になっているとします。この配列に対して、次の2種類のクエリを処理することを考えます。update(l, r, value) ― インデックス l から r までの範囲に含まれるすべての要素に value を加算します。たとえば update(2, 4, 5) なら、インデックス 2〜4 の各要素に 5 を足す操作を意味します。getRangeSum(l, r) ― インデックス l から r までの範囲に含まれる要素の合計を求めます。たとえば getRangeSum(4, 7) なら、インデックス 4、5、6、7 の要素の総和を計算

この問題では、二分木が与えられます。求められているのは、C++で二分木を括弧付きの文字列に変換するプログラムを作成することです。 二分木の各ノードの値は整数であり、先行順巡回（プレオーダー走査）の順序でプログラムに入力されます。生成する文字列には整数と括弧「()」のみを含めることができ、さらに最適化されている必要があります。つまり、不要な空の括弧ペアはすべて取り除かなければなりません。 二分木とは、各ノードが最大2つの子ノードを持つという特別な条件を満たす木構造のことです。 二分木の例 先行順巡回：[4, 1, 8, 3, 9, 2, 5] 具体例を見ながら問題を理解しましょう。 入力 p

この記事では、Linuxでパイプ(pipe)を使用するCプログラムの作成方法を解説します。作成するプログラムでは、入力ストリームからテキストを読み込み、それを出力画面に表示します。まずは、Linuxにおけるパイプの基礎知識から確認していきましょう。Linuxにおけるパイプとはパイプ(pipe)はデータを転送するための仕組みで、LinuxやUnixベースのシステムにおいて、プロセス間・コマンド間・プログラム間で標準出力を受け渡すためのプロセス間通信(IPC)として利用されます。パイプについて注意すべき重要な点として、パイプは単方向であるということが挙げられます。つまり、データはプログラム内で左か

ストロボグラム数とは？ ストロボグラム数（strobogrammatic number）とは、数字を180度回転させても同じように見える数のことです。回転しても元の形を保てるのは「0」「1」「8」の3種類だけで、さらに「6」と「9」は互いに入れ替わるペアとして機能します。これらの数字だけを組み合わせることで、回転対称となる数を作れます。 例えば、low = 50、high = 100 という入力が与えられた場合を考えてみましょう。この範囲に含まれるストロボグラム数は 69・88・96 の3つであるため、出力は 3 になります。 解法のアプローチ この問題は「指定した桁数のストロボグラム数をすべ

ペイントハウスII問題とはn軒の家が一列に並んでいるとします。各家はk色の中から1色を選んで塗ることができますが、色ごとに塗布コストが異なります。ここで守らなければならない条件は、隣り合う家同士が同じ色にならないように、すべての家を塗るということです。各家を特定の色で塗るときのコストは、n×kの行列として与えられます。このとき、すべての家を塗るために必要な最小コストを求めるのがこの問題の目的です。例えば、入力が次のような場合を考えてみましょう。153294この場合の出力は5になります。家0を色0で塗り、家1を色2で塗れば、最小コストは1 + 4 = 5です。あるいは、家0を色2で、家1を色0で

問題の概要 ある新しい異星人の言語(エイリアン語)がラテン文字を使用しているとします。ただし、文字同士の順序関係は不明です。この言語のルールに従って辞書順にソートされた、空でない単語のリストが与えられるので、この言語における文字の順序を求めてください。 例えば、入力が [wrt,wrf,er,ett,rftt] の場合、出力は wertf となります。 解法のアプローチ:トポロジカルソート この問題は、グラフ理論におけるトポロジカルソートを用いることで効率的に解けます。隣接する2つの単語を比較し、最初に異なる文字が現れた位置から文字間の順序関係(有向エッジ)を抽出し、そのグラフに対してトポロジ

問題概要 二分探索木（Binary Search Tree：BST）とターゲット値が与えられたとき、そのBSTの中からターゲットに最も近いk個の値を見つけることを考えます。ここで注意すべき点是として、ターゲット値は浮動小数点数であるという点が挙げられます。なお、kは常に有効な値であり、k ≤ 全ノード数が保証されているものとします。 例えば、次のようなBSTが入力として与えられた場合を考えます。 このとき、target = 3.714286、k = 2 とすると、出力は [4, 3] となります。 解法のアプローチ この問題は、ターゲットより小さい値の候補と大きい値の候補をそれぞれ管理する2

問題概要 パターン文字列と、もうひとつの文字列 str が与えられます。str がこのパターンに従っているかどうかを判定してください。ここで「パターンに従う」とは完全一致を意味し、パターン中の各文字と str 中の空でない部分文字列との間に、全単射（一対一対応）が成立していなければなりません。 たとえば、パターンが "abaa"、str が "orangegreenorangeorange" の場合を見てみましょう。a → "orange"、b → "green" という対応が成り立ち、"abaa&quo

問題の概要2人以上からなるグループが集まりたいとき、全員の移動距離の合計を最小限に抑えられる場所を求めます。ここでは、0または1の値を持つ2次元グリッドが与えられ、各「1」はグループ内の誰かの家を表しているものとします。距離はマンハッタン距離で計算され、次の式で定義されます。distance(p1, p2) = |p2.x − p1.x| + |p2.y − p1.y|入力例100010000000100出力例この場合の出力は 6 になります。行列から、(0,0)、(0,4)、(2,2) の3か所に住む3人がいることが読み取れます。点 (0,2) が理想的な集合地点であり、総移動距離は 2 +

はじめにシリアライズ（直列化）とは、データ構造やオブジェクトを一連のビット列へ変換する処理のことです。これにより、データをファイルやメモリバッファに保存でき、後から同じ環境でも別のコンピュータ環境でも元の構造として復元（デシリアライズ）できます。本記事では、二分木を対象に、シリアライズとデシリアライズを行うアルゴリズムを解説します。なお、二分木とは各ノードが最大2つの子ノードしか持たない根付き木のことを指します。例えば、次のような二分木が与えられたとします。この場合の出力は以下のようになります。シリアライズ結果：1 2 3 4 5 N N N N N Nデシリアライズ後の木（中順走査）：4 2

問題の概要 ある画像が2値行列で表現されていると考えます。0は白ピクセル、1は黒ピクセルを表します。ここで、黒いピクセル同士は上下左右に連結しており、黒い領域はちょうど1つだけ存在するものとします。黒いピクセルのうち1つの座標 (x, y) が与えられたとき、すべての黒いピクセルを囲む最小の(軸に平行な)長方形の面積を求めるのが目的です。 例えば、入力が次のような場合を考えてみましょう。 001001100100 このとき x = 0、y = 2 とすると、出力は 6 になります。 解き方の手順 この問題は二分探索を応用することで効率的に解けます。既知の黒ピクセル (x, y) を基準に、上

問題概要2次元の行列 matrix が与えられ、左上隅と右下隅で定義される矩形領域内に含まれる要素の合計を計算するのがこの問題です。さらに重要なポイントとして、行列の要素を後から更新（mutable）できることも求められています。例として、次のような入力を考えてみましょう。3014256321120154101710305ここで、以下のようにメソッドを呼び出すケースを想定します。sumRegion(2, 1, 4, 3)update(3, 2, 2)sumRegion(2, 1, 4, 3)このとき出力は 8 と 10 になります。最初の呼び出しでは、上の表の緑色で示した部分、つまり (2,1

問題概要空き地に家を建てることを考えてみましょう。条件は、その家からすべての建物へ移動する距離の合計が最小になることです。移動は上下左右の4方向のみ許されます。盤面は、0・1・2 のいずれかの値を持つ2次元グリッドとして与えられます。それぞれの意味は次の通りです。0：自由に通行できる空き地1：通行できない建物2：通行できない障害物入力例と出力例例として、次のグリッドが与えられたとします。102010000000100この場合の出力は 7 です。3つの建物が (0,0)、(0,4)、(2,2) の位置にあり、障害物が (0,2) に存在します。そこで (1,2) が家を建てるのに最適な空き地とな

問題概要 文字列が与えられたとき、最大 k 個の異なる文字を含む最長の部分文字列 T の長さを求めるのがこの問題の目的です。 例えば、入力が s = "eceba"、k = 2 の場合、出力は 3 になります。これは T = "ece" となり、その長さが 3 であるためです。 解法のアプローチ：スライディングウィンドウ この問題はスライディングウィンドウ（尺取り法）とハッシュマップを組み合わせることで、線形時間 O(n) で効率的に解くことができます。 具体的な手順は以下の通りです。 ans := 0（答えとなる最長の長さ） マップ m を定義する

問題の概要 空でない文字列 s と整数 k が与えられたとき、同じ文字同士が互いに少なくとも距離 k 以上離れるように文字列を並べ替えることを考えます。入力の文字列はすべて小文字の英字で構成されているものとします。条件を満たす並べ替えが存在しない場合は、空文字列を返します。 たとえば、入力が s = "aabbcc"、k = 3 の場合、出力は "abcabc" のようになります。これは、どの文字も同じ文字が再び現れるまでに3文字以上の間隔が空いているためです。 解き方のアプローチ：優先度付きキューとスライディングウィンドウ この問題は貪欲法（グリーデ

問題の概要 N個の軸に平行な長方形が与えられたとき、それらがすべて組み合わさって、ある矩形領域を「隙間も重なりもなく」正確に覆っているかどうかを判定します。各長方形は左下の頂点と右上の頂点で表現され、たとえば単位正方形は [1,1,2,2] と表されます（左下の点が (1,1)、右上の点が (2,2) を意味します）。 たとえば、入力が rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] の場合、5つの長方形全体がぴったり一つの矩形領域を覆うため、答えは true（1）になります。 解法のポイント この問題は、次

この記事では、C++を使って「最小の一意な単語の略語（Minimum Unique Word Abbreviation）」問題を解く方法を解説します。ビットマスクと深さ優先探索（DFS）を組み合わせた効率的なアルゴリズムの考え方と実装例を紹介します。 問題の概要 まず、文字列「word」には次のようなさまざまな略語が考えられます。 [word, 1ord, w1rd, wo1d, wor1, 2rd, w2d, wo2, 1o1d, 1or1, w1r1, 1o2, 2r1, 3d, w3, 4] ここで、ターゲット文字列と、辞書として与えられる文字列の集合が入力として渡されます。求めるのは、

ワードスクエアとは？ユニークな単語の集合が与えられたとき、そこから作成できるすべての「ワードスクエア（単語正方形）」を見つけることを考えましょう。単語のシーケンスが有効なワードスクエアとなる条件は、k番目の行とk番目の列がまったく同じ文字列を読み取ることです（ここで 0 ≤ k < 行数と列数の最大値）。例えば、単語列 [ball, area, lead, lady] はワードスクエアを構成します。どの単語も横方向にも縦方向にも同じように読めるからです。ballarealeadladyしたがって、入力が [area, lead, wall, lady, ball] の場合、出力は [[wall