C++

文字列と、クエリの集合Qが与えられている状況を考えてみましょう。各クエリは2つの整数 i と j、および1つの文字 c から構成されます。クエリが実行されると、文字列のインデックス i と j にある文字が新しい文字 c に置き換えられ、その結果の文字列が回文（前から読んでも後ろから読んでも同じになる文字列）であるかどうかを判定する必要があります。 例えば、「AXCDCMP」という文字列に対してクエリ (1, 5, B) を適用すると、文字列は「ABCDCBP」になります。続けて別のクエリ (0, 6, A) を適用すると、文字列は「ABCDCBA」となり、これは回文です。 アルゴリズムの流れ

ここでは、0と1で構成された2次元配列（マトリックス）が与えられ、左上の角から右下の角まで到達できる経路が存在するかどうかを判定する問題を扱います。0は通行可能な領域を、1は障害物（ブロック）を表します。なお、左上のセルは常に出発点として扱われるものとします。 例として、次のようなマトリックスを考えてみましょう。 0001010011000101000000100 このマトリックスには複数の経路が存在するため、プログラムはtrueを返します。経路が1つも存在しない場合はfalseを返します。 アルゴリズムの考え方 この問題は、到達可能なセルの値をすべて-1に書き換えていくことで解決できます。

本記事では、与えられた正方行列が魔方陣（マジックスクエア）であるかどうかをC++で判定する方法を解説します。 魔方陣とは？ 魔方陣とは、各行・各列、そして両対角線上の要素の合計値がすべて等しくなるような正方行列のことです。この共通の合計値は「魔定数」と呼ばれることもあります。 例として、次のような3×3の行列を考えてみましょう。 618753294 この行列を確認すると、以下のすべての合計が 15 で一致していることがわかります。 1行目：6 + 1 + 8 = 15 2行目：7 + 5 + 3 = 15 3行目：2 + 9 + 4 = 15 1列目：6 + 7 + 2 = 15 2列目：1

サイズnの配列が与えられたとき、その配列が高さnの二分探索木（BST）を表すことができるかどうかを判定する問題について解説します。ここで「高さn」とは、根から葉までの最長パスがn個のノードで構成されることを意味し、つまり配列の各要素が木の各レベルに1つずつ対応することを指します。 問題の理解 BSTのルールに従って要素を挿入していくとき、配列の順序通りに挿入した結果、高さがちょうどn（要素数と同じ）になるかどうかを確認します。これは、配列の各要素が前の要素の左または右の子として挿入され、一度も同じレベルに複数のノードが配置されないことを意味します。 例として以下の2つの配列を考えます：

数値を表す文字列が与えられたとき、その数値が指定された基数 B で有効に表現できるかどうかを判定することを考えます。例えば、文字列が「101110」で b = 2（2進数）の場合、プログラムは true を返します。同様に、文字列が「A8F」で基数が16（16進数）の場合も true となります。 判定方法は非常にシンプルです。文字列内のすべての文字が、指定された基数で使用される記号（数字または英字）の範囲内に含まれていれば true を返し、1つでも範囲外の文字が存在すれば false を返します。 このプログラムは基数16までに対応しています。基数が10以下の場合は「0」～「9」の数字のみ

本記事では、ある整数が「ジャンブル数（jumbled number）」と呼ばれる条件を満たしているかどうかを判定する、興味深い問題をC++で解いていきます。ジャンブル数とは？ジャンブル数とは、すべての隣り合う桁同士の差が最大でも1であるような数のことです。例えば「1223」は隣接する桁の差がそれぞれ1以下であるためジャンブル数ですが、「1256」は2と5の差が3あるためジャンブル数にはなりません。判定アルゴリズムこの問題を解くには、数値の下の桁から順に隣接する桁との差を調べ、差が1より大きい桁がひとつでも見つかった時点でfalseを返し、最後まで確認できればtrueを返すという手順を踏みます。

この記事では、ある数値が5で割り切れるかどうかを判定する方法を紹介します。通常であれば「num % 5 == 0」のように剰余演算子（%）を使えば簡単に判定できますが、ここでは「/」（除算）および「%」（剰余）の演算子を一切使用せずに判定を行います。 判定の考え方 5の倍数には重要な特徴があります。それは「一の位（最後の桁）が必ず 0 または 5 になる」という点です。したがって、数値の末尾の桁が 0 か 5 であれば、その数は5で割り切れると判断できます。それ以外の場合は5の倍数ではありません。 さらに、この方法では数値を文字列として扱うため、long long 型などの整数型の範囲を超え

この記事では、ある数値が回文数（パリンドローム）かどうかを判定する方法を解説します。回文数とは、前から読んでも後ろから読んでも同じになる数値のことです。例えば、12321 は回文数ですが、12345 は回文数ではありません。判定のロジックは非常にシンプルです。数値を逆順に並べ替え、元の数値と一致するかどうかを比較します。一致すれば回文数、一致しなければ回文数ではありません。より理解を深めるために、アルゴリズムを見ていきましょう。アルゴリズムisPalindrome(n) −入力 − 数値 n出力 − 数値が回文数であれば true、そうでなければ false 0, do rev

数値が与えられたとき、その数が完全平方数（perfect square）かどうかを判定することを考えます。ここでは、平方根の演算を使用せずに判定を行う方法を紹介します。例えば、1024は 32 × 32 = 1024 と表せるため完全平方数ですが、1000はいかなる整数の二乗にもならないため完全平方数ではありません。 考え方は非常にシンプルです。1から順に整数 i を増やしながら、i × i が n を超えるまで調べます。このとき、n が i で割り切れ、かつ商（n ÷ i）も i と等しい場合、すなわち n = i × i が成立した時点で、n は完全平方数であると判定できます。 アルゴリズ

この記事では、ビット演算子のみを使って、ある数値が正の数、負の数、ゼロのいずれであるかを判定する方法を解説します。if文などの条件分岐に頼らずに判定できるのがポイントです。判定の仕組み32ビット整数を前提とすると、算術右シフトでは符号ビットが伝播するという性質を利用します。n >> 31 を実行すると、負の数は -1 に、それ以外の数は 0 になります。-n >> 31 を実行すると、正の数は -1 になります（負号を反転しているため）。n が 0 の場合は、n >> 31 と -n >> 31 のどちらも 0 を返します。これらの性質を組み合わ

この記事では、ある数値が8の累乗であるかどうかを、簡単な手法を使って判定する方法を紹介します。例えば4096という数値は8の累乗（84）なので、プログラムはtrueを返します。 判定の仕組み 考え方は非常にシンプルです。まず log8(num) を計算します。この結果が整数であれば、その数値nは8の累乗であると判断できます。 ただし、浮動小数点数の計算には誤差が伴うため、単純に整数かどうかを比較するだけでは不十分な場合があります。そこで、trunc(n) 関数を使ってdouble型の値の小数部分を切り捨てた整数値を求め、元の値との差が十分に小さいかどうかを確認します。この誤差の許容範囲を0.0

はじめにこの記事では、ある数値と値 k が与えられたとき、その数値が k の冪乗であるかどうかを「基数変換法(底の変換)」を用いて判定するC++プログラムを紹介します。例として、数値が 27、k = 3 のケースを考えてみましょう。27 を 3 進法で表すと「1000」になります。このように基数変換を行った結果、「1」がちょうど1回だけ現れ、それ以外の桁がすべて「0」であれば、その数値は k の冪乗であると判断できます。アルゴリズムの手順この問題は、以下の手順に従って解くことができます。フラグ(flag)を false として初期化するnumber > 0 の間、手順3〜6を繰り返すdi

中心座標 (h, k)、長半径 a、短半径 b をもつ楕円が1つ与えられ、さらに任意の点 (x, y) が与えられたとします。このとき、その点が楕円の内側にあるのか、外側にあるのか、あるいは境界上にあるのかを判定する方法を解説します。判定に使う数式点の位置関係は、次の式に点の座標 (x, y) を代入して計算することで求められます。$$\frac{\left(x-h\right)^2}{a^2}+\frac{\left(y-k\right)^2}{b^2}$$この計算結果と 1 を比較することで、点の位置を以下のように分類できます。結果が 1 未満の場合 → 点は楕円の内側結果が 1 と等しい

放物線と点の位置関係を判定する方法頂点座標 (h, k)、焦点と頂点の距離 a で表される放物線が1つ与えられ、さらに任意の点 (x, y) が与えられたとします。このとき、その点が放物線の内側にあるのか、外側にあるのか、あるいは放物線上にあるのかを判定する問題を解いてみましょう。判定の原理判定には、放物線の標準形の方程式を利用します。与えられた点 (x, y) を次の式に代入し、左右の差を計算します。(y − k)² = 4a(x − h)具体的には、res = (y − k)² − 4a(x − h) を求め、その値の符号によって点の位置を判定します。res < 0 の場合: 点は放

問題の概要友人同士でお金の貸し借りを行っていると、グループ内に複数の資金の流れ(キャッシュフロー)が発生します。本記事では、このキャッシュフローを最小限に抑える方法を解説します。例として、P1、P2、P3という3人の友人がいるとしましょう。彼らの間の資金の流れは、以下の図のようになっています。この状態ではまだ資金の流れが最適化されていません。そこで、貸し借りを整理・統合すると、最終的には次のようなシンプルな流れになります。貪欲法(グリーディーアプローチ)による解法この問題は貪欲法を用いて効率的に解くことができます。基本的な考え方は、「各ステップで1人の人物の金額を完全に清算し、残りのn-1人に

平面上に複数の点が与えられたとき、その中から原点(0, 0)に最も近いK個の点を求める問題を考えてみましょう。 例として、点 (3, 3)、(5, -1)、(-2, 4) の3点が与えられ、K = 2 とします。このとき原点に最も近い2点は (3, 3) と (-2, 4) になります。 解決のアプローチ この問題は次の手順で解くことができます。 各点についてユークリッド距離を計算します。原点からの距離は √(x² + y²) で表されますが、大小比較だけであれば平方根の計算は不要なので、x² + y² の値をそのまま使えば十分です。 距離を基準に点のリストをソートします。 ソート後のリスト

本記事では、C++を使って循環片方向リンクリスト（単一循環リンクリスト）から最小値と最大値を検索する方法を解説します。 循環リンクリストの基本構造 循環リンクリストは、最後のノードのnextポインタが先頭ノードを指すデータ構造です。これにより、リスト全体がリング状につながります。また、startポインタによって先頭ノードの位置も管理されます。 新しい要素を挿入するときは、末尾ノードのnextに新ノードをつなぎ、新ノードのnextにstartノードのアドレスを設定します。これで循環構造が維持されます。 最小値・最大値を求めるアルゴリズム 考え方はとてもシンプルです。手順は以下の通りです。 変数

平面上に与えられた点の集合があり、そのすべての点をちょうど一度ずつ通る「単純な閉じた経路（単純閉路）」を見つけたいとします。下の図のような点が与えられた場合、これらの点を適切な順序で結ぶことで閉じたパスを構成できます。 アルゴリズムの考え方 この問題は、凸包を求める際に用いられる「偏角ソート」の考え方を応用することで解くことができます。具体的な手順は以下の通りです。 最も左下にある点（y座標が最小、同一の場合はx座標も最小）を基準点 P として選びます。 残りの n − 1 個の点を、P を中心とした反時計回りの偏角（極角）に基づいてソートします。2つの点の偏角が等しい場合は、P からの

円の中心座標と半径が与えられ、別の点 (x, y) が円の中心を基準としてどの象限に位置するのかを求める問題です。点が円の内部に存在する場合はその象限を出力し、円の外部に存在する場合はエラーとして「点が円の外にある」ことを出力します。円の中心を (h, k)、点の座標を (x, y) とすると、円の方程式は次のように表されます。(x − h)2 + (y − k)2 = r2点と中心の距離の二乗を半径の二乗と比較することで、点の位置を判定できます。判定条件は以下の通りです。(x − h)2 + (y − k)2 > r2 の場合 → 点は円の外側にある(x − h)2 + (y − k)

フリップフロップ(flip-flop)は、順序論理回路の基本要素となるデジタル回路です。フリップフロップにはいくつかの種類があり、本記事では代表的な4種類の特徴と動作、さらに「あるフリップフロップから別のフリップフロップへ変換する」ための具体的な手順を解説します。フリップフロップには主に以下の4種類があります。SRフリップフロップDフリップフロップJKフリップフロップTフリップフロップSRフリップフロップとはSRフリップフロップは、クロック信号の立ち上がりエッジまたは立ち下がりエッジでのみ動作します。一方、SRラッチはイネーブル信号によって動作する点が異なります。SRフリップフロップの回路図を