C++

この記事では、2つの異なる文字列を比較した際に、共通しない文字(どちらか一方にしか存在しない文字)を見つけ出すプログラムについて解説します。 ご存知の通り、文字列とは本質的に文字の配列です。そのため、比較を行う際は、一方の文字列の文字を先頭から順に走査しながら、その文字がもう一方の文字列にも存在するかどうかを確認していきます。 ここで、最初の文字列をA、2番目の文字列をBとすると、まず「A − B」(Aには含まれるがBには含まれない文字)が求められます。同様の手順で「B − A」も計算できます。 この2つの結果を組み合わせると、次の式になります。 ( A − B ) ∪ ( B − A )

はじめに 本記事では、ソートされていない2つの配列から和集合と共通部分（積集合）を求めるC++プログラムについて解説します。 和集合と共通部分とは まず、2つの配列をそれぞれ「A」「B」と呼ぶことにします。 和集合（A ∪ B）とは、2つの配列に含まれるすべての要素を集めた配列のことです。ただし、重複する要素は1度しか現れないものとします。 共通部分（A ∩ B）とは、2つの配列のどちらにも存在する要素だけを集めた配列のことです。 アルゴリズムの流れ 和集合を求める手順 別途配列を用意し、1つ目の配列の全要素をコピーします。 2つ目の配列の要素を先頭から順に走査します。 その要素がすでに和

この記事では、要素がN以下であり、かつ以下の条件を満たす一意な数のペアを見つけるプログラムについて詳しく解説します。2つの数の差の2乗が、それらの最小公倍数(LCM)と等しいこと。2つの数の最大公約数(HCF)が、連続する2つの数の積として表せること。問題を解くためのアプローチこの問題を効率的に解くには、1から始まる連続する2つの数を取り、その積の倍数を順に調べる方法が有効です。その中からペアを特定するために、候補となる2つの数が最初の条件(差の2乗 = LCM)を満たしているかどうかを確認します。具体例：2と3の場合まず、2と3という連続する数を考えてみましょう。その積は6です。6の倍数を順

本記事では、ある整数 X を「重複しない自然数の n 乗の総和」として表現する方法が何通りあるかを求めるプログラムについて解説します。問題の概要例として、X = 100、n = 2 の場合を考えてみましょう。このとき、100 を自然数の2乗（平方数）の和として表す方法は3通り存在します。100 = 102 100 = 62 + 82 100 = 12 + 32 + 42 + 52 + 72アルゴリズムの考え方この問題は再帰を使うことで簡単に解くことができます。基本的な手順は以下の通りです。1 から対象となる数の n 乗根まで順に走査していきます。各ステップでは、自然数（1から開始）の n 乗の

本記事では、タスク間の前提条件（依存関係）が与えられたとき、すべてのタスクを完了できるかどうかを判定するC++プログラムについて解説します。問題の概要例として、3つのタスクと前提条件 [[1, 0], [2, 1], [3, 2]] が与えられた場合を考えてみましょう。（[1,0] は「タスク 1 を実行するには、先にタスク 0 を完了しておく必要がある」ことを意味します）この例では、タスク 0 には前提条件がないため最初に完了できます。次に、タスク 0 が完了しているのでタスク 1 を実行できます。同様に、タスク 2 と 3 も順番に完了できます。したがって、このケースの答えは「True」と

本記事では、文字列の中から特定のパターンを効率的に探し出す「有限オートマトン（Finite Automata）」アルゴリズムを、C++で実装する方法を解説します。 長さ n のテキスト text[0...n-1] と、長さ m のパターン pattern[0...m-1] が与えられたとき、テキスト内にパターンが出現するすべての位置（インデックス）を見つけるのが目的です。 有限オートマトン法の基本的な考え方 このアルゴリズムでは、まず前処理としてパターンから「状態遷移表」を作成します。これは、現在の状態と読み込んだ文字に応じて、次にどの状態へ遷移するかを表す2次元配列です。 遷移表さえ完成し

本記事では、与えられた配列のすべての要素に対する剰余（mod）が同じ値になるような整数「k」を見つけるC++プログラムについて解説します。 問題の概要 例として、次のような配列が与えられたとします。 arr = {12, 22, 32} この場合、条件を満たすkの値は 1、2、5、10 となります。実際に確認してみると、これらの値で各要素を割った余りはすべて等しくなっています。 解法の考え方 まず、配列内の2つの値「x」と「y」（x > y）に注目します。両者の差を「difference」とすると、次の関係が成り立ちます。 (y + difference) % k = y % k この式

本記事では、大圏距離（Great Circle Distance）公式を使用して、ユーザーの位置から約50km以内に存在するタクシー（配車車両）を検索するC++プログラムについて解説します。問題の概要ここでは、配車を必要としているユーザーの氏名と座標情報、および利用可能なすべてのタクシーの座標情報が記録されたJSONファイルが与えられていると仮定します。この問題を解くための手順は以下の通りです。まず、GPS座標（緯度・経度）を double 型の数値に変換します。次に、その数値を「度」から「ラジアン」へ変換します。最後に、大圏距離公式を適用し、ユーザーの現在地から50km以内にあるタクシーを特

この記事では、2つの等差数列に共通して現れる最初の値――いわゆる「衝突点（コリジョンポイント）」――を見つけるC++プログラムについて解説します。問題の概要まず、5つの変数「a」「b」「c」「d」「n」が与えられます。これらの変数をもとに、それぞれn項からなる次の2つの等差数列（算術級数）を作成します。b, b+a, b+2a, …, b+(n−1)ad, d+c, d+2c, …, d+(n−1)cそのうえで、この2つの数列の両方に共通して含まれる最初の値を求めることが目的です。解法のアプローチこの問題は、次の手順で解くことができます。第1の数列の項を先頭から順に1つずつ生成します。生成した

本記事では、二分探索（バイナリサーチ）を活用して、与えられたグラフの最小頂点被覆のサイズを求めるC++プログラムについて解説します。 最小頂点被覆とは？ 最小頂点被覆（Minimum Vertex Cover）とは、グラフのすべての辺が、集合内のいずれかの頂点に接続（インシデント）するような頂点集合のうち、頂点数が最小のものを指します。 例として、以下のグラフを見てみましょう。 2 ---- 4 ---- 6 | | | | | | 3 ---- 5 このグラフの場合、最小頂点被覆は「頂点3」と「頂点4」の2つの頂点から構成されます。グラフ上のすべての辺は、必ず頂

はじめに本記事では、数値の各桁の合計を計算し、その結果が1桁になるまで処理を繰り返すC++プログラムについて解説します。例として、数値14520を考えてみましょう。まず各桁を足すと、1 + 4 + 5 + 2 + 0 = 12となります。しかし12はまだ2桁の数値なので、さらにその桁同士を足し合わせます。すると、1 + 2 = 3となります。3は1桁の数値であるため、これ以上桁の合計を計算することはできません。したがって、3が最終的な答えとなります。解法のアプローチ：デジタルルートの活用この問題を効率的に解くには、「9の倍数の各桁の合計は必ず9になる」という数学的な性質を利用します。9で割り切

はじめに この記事では、指定された点を覆う「最適な長方形」を見つけるためのC++プログラムについて詳しく解説します。 問題の概要 この問題では、ある点の座標 (x, y) と、長さと幅の比 l/b が与えられます。求めるのは、次の条件をすべて満たす長方形の座標です。 与えられた点を内部に含んでいること 寸法が指定された比率 l : b に従っていること 条件を満たす長方形が複数存在する場合は、その中心と与えられた点とのユークリッド距離が最も短いものを選択します。 アルゴリズムのアプローチ この問題は、以下の手順で解くことができます。 比率の最小化： 最大公約数（GCD）を用いて比率

はじめにこの記事では、与えられた配列のすべての要素を掛け合わせた積の、最初の桁（最上位の桁）を求めるプログラムについて解説します。例として、次のような配列が与えられたとします。arr = {12, 5, 16}これらの要素の積は、12 × 5 × 16 = 960 となります。したがって、求める結果、つまり積の最初の桁は「9」になります。アルゴリズム変数 prod を 1 で初期化するループを使い、配列の各要素を順番に prod に掛けていくprod が 10 以上である間、prod を 10 で割り続ける残った一桁の値が、積の最初の桁となるサンプルコード#include <bits/s

本記事では、与えられた水平線分と垂直線分の交点同士を結ぶことで形成できる三角形の数を求めるC++プログラムについて詳しく解説します。 問題の概要 例として、次のような線分が与えられた場面を考えてみましょう。この図には3つの交点が存在します。三角形を作るには3つの頂点が必要となるため、これらの点から作れる三角形の数は「3つの点を選ぶ組み合わせ」、すなわち 3C3 = 1 通りとなります。    | ---|--------|--    |        |    |  --|---|

パリティとはこの記事では、与えられた数値Nのパリティを求めるC++プログラムについて解説します。パリティとは、数値を2進数で表したときに含まれる「1」の個数（セットビット数）を指します。2進表現における「1」の個数が偶数であれば「偶数パリティ（Even Parity）」、奇数であれば「奇数パリティ（Odd Parity）」と呼ばれます。効率的なアルゴリズム与えられた数値をNとするとき、以下の手順で演算を行うことで、パリティを高速に求めることができます。y = N ^ (N >> 1)y = y ^ (y >> 2)y = y ^ (y >> 4)y = y

本記事では、マルコフ連鎖（Markov Chain）において、初期状態から出発し、指定された時間が経過した時点で特定の状態へ到達する確率を求めるC++プログラムについて解説します。 マルコフ連鎖とは マルコフ連鎖とは、複数の「状態」と、ある状態から別の状態へ遷移する際の「遷移確率」から構成される確率過程（ランダムプロセス）です。状態間の遷移には単位時間が1単位かかるものとします。マルコフ連鎖の重要な特徴は、「次の状態」が現在の状態のみによって決まり、それ以前の履歴に依存しないというマルコフ性を持つ点です。 マルコフ連鎖は有向グラフとして表現できます。この問題を解くには、与えられたマルコフ連鎖

本記事では、放物線の方程式の係数が与えられたときに、その頂点、焦点、準線を求めるC++プログラムについて解説します。 放物線とは、曲線上のすべての点が「焦点」と呼ばれる1つの点から等距離にある曲線のことです。 放物線の一般方程式は次のとおりです。 y = ax2 + bx + c この方程式に対して、頂点・焦点・準線はそれぞれ次の式で表されます。 頂点(Vertex)：(-b/2a, (4ac − b2)/4a) 焦点(Focus)：(-b/2a, (4ac − b2 + 1)/4a) 準線(Directrix)：y = c − (b2 + 1) × 4a 各要素の意味 頂点（Vertex）

この記事では、与えられたすべての座標点が2本の平行線だけに収まるかどうかを判定するプログラムについて解説します。問題の概要判定の対象となるのは、座標が (i, arr[i]) となるような配列です。例として、次の配列を考えてみましょう。arr = {2,6,8,12,14}この場合、これらの点は2本の平行線上に配置できます。1本目の直線には (1,2)、(3,8)、(5,14) が含まれ、2本目の直線には残りの座標、つまり (2,6) と (4,12) が含まれます。解法のアプローチこの問題は、与えられた点が作る直線の傾きを比較することで解くことができます。ご存知のとおり、点 (a1, b1)

本記事では、与えられたマトリックス（行列）の中に、2つのセルをつなぐパス（経路）が存在するかどうかを判定するC++プログラムについて解説します。ここでは、0・1・2・3のいずれかの値を持つ正方行列が与えられたと仮定します。各値の意味は以下の通りです。0：空白の壁（通過不可）1：スタート地点（ソース）2：ゴール地点（デスティネーション）3：空白セル（通過可能）マトリックス内にはソースとデスティネーションがそれぞれ1つだけ存在します。このプログラムの目的は、上下左右の4方向のみに移動し（斜め移動は禁止）、ソースからデスティネーションへ到達できる経路があるかどうかを確認することです。解決のアプローチ

配列で表現された数値とは 数値を配列として表現する場合、数値の各桁を配列の個々の要素に格納します。配列の長さは数値の桁数と一致し、たとえば4桁の数値であれば配列の長さも4となります。各要素には一桁の数字（0〜9）だけが格納され、配列の末尾の要素には数値の最下位桁が、先頭の要素には最上位桁が保存されます。 例えば、数値351932は {3,5,1,9,3,2} という形で表現されます。 1を加算する仕組み このような数値に1を加算するには、まず配列の最後の要素に1を足し、繰り上がり（キャリー）が発生するかどうかを確認します。最後の桁が9だった場合には繰り上がりが発生し、その要素の値は0になりま