C++

この問題では、整数が継続的に読み込まれていくデータストリームが与えられます。目的は、要素を読み込みながら、その時点までの要素群に対して中央値を計算していくプログラムを作成することです。 中央値とは 中央値(Median)とは、ソートされた数列(昇順・降順のいずれでも可)において中央に位置する要素のことです。 要素数が奇数の場合：中央値は中央の要素そのもの 要素数が偶数の場合：中央値は中央に位置する2つの要素の平均値 具体例で理解する 入力として「3, 65, 12, 20, 1」が与えられた場合、各入力の時点での中央値は次のように変化していきます。 Input - 3 : sequence

このチュートリアルでは、二分木においてXOR(排他的論理和)が奇数になる隣接ノードのペアの数を求めるプログラムについて解説します。 隣接ノードとは、親ノードとその直接の子ノードの組み合わせを指します。与えられた二分木に対して、隣接する2つの要素のXOR値が奇数になるペアがいくつあるかを数えるのが今回のタスクです。 XORが奇数になる条件 まず押さえておきたい重要な性質として、XORの結果が奇数になるのは、2つの値のうち片方が奇数でもう片方が偶数の場合だけです。同じ偶奇(パリティ)を持つ2つの値のXORは必ず偶数になります。 奇数 XOR 偶数 → 奇数 奇数 XOR 奇数 → 偶数 偶数 X

はじめに この記事では、配列内の要素ペアのうち、2進表現においてKビットだけ異なるペアの総数を求めるC++プログラムについて解説します。 具体的には、整数の配列と整数Kが与えられたとき、任意の2つの要素を比較し、異なるビットの数がちょうどK個になるペアがいくつ存在するかを計算します。 解決のアプローチ この問題は、XOR(排他的論理和)の性質を利用することでシンプルに解けます。 配列内のすべてのペア(arr[i], arr[j])について、2つの値のXORを計算します。 XORの結果に含まれる「1」のビット数(セットビット数)を数えます。これは2つの要素間で異なるビットの数に一致します。 セ

このチュートリアルでは、配列の中から指定されたXOR値を持つペアの数を求めるプログラムについて解説します。具体的には、整数の配列とターゲットとなる値が与えられ、その2つの要素のXOR（排他的論理和）がターゲット値と一致するペアがいくつ存在するかをカウントするのが課題です。アルゴリズムの考え方全てのペアを総当たりで調べる方法（O(n²)）もありますが、ここではハッシュマップ（unordered_map）を活用することで、時間計算量O(n)で効率的に解く手法を紹介します。基本的なアイデアは以下の通りです。XORの性質を利用します。ある要素 a に対して「a ^ b = x」が成り立つとき、「b =

このチュートリアルでは、文字列に含まれる回文部分文字列の個数を求めるプログラムについて解説します。文字列が与えられ、その中に含まれる回文部分文字列のうち、長さが2以上のものを数えるのが課題です。単一の文字も回文とみなせますが、この実装では2文字以上の回文を対象としています。アルゴリズムの考え方(動的計画法)この問題は動的計画法(DP)を用いることで効率的に解くことができます。ここでは2つの2次元配列を使用します。P[i][j]:部分文字列 str[i..j] が回文であれば true となる真偽値テーブルdp[i][j]:部分文字列 str[i..j] に含まれる回文部分文字列の個数まず、長さ

本記事では、回文の2乗が回文となる数（スーパー回文）の個数を求めるC++プログラムについて詳しく解説します。スーパー回文とは？まず、2つの整数 L と R が与えられます。私たちのタスクは、この範囲 [L, R] 内に存在するスーパー回文の個数を求めることです。スーパー回文とは、その数自身が回文であり、さらにその2乗も回文となっている特別な数のことです。例えば、「3」は回文であり、その2乗「9」も回文なので、3はスーパー回文です。アルゴリズムの考え方範囲内のすべての数を1つずつ調べるのは非効率です。そこで、次のようなアプローチを取ります。回文を生成してから判定することで、探索範囲を大幅に絞り込

このチュートリアルでは、与えられた文字列の中に含まれる回文部分列の総数を求めるプログラムについて解説します。 入力として1つの文字列が与えられ、その文字列から作り出せる回文部分列がいくつあるかを数えるのが課題です。 回文部分列とは? 部分列(subsequence)とは、元の文字列から0個以上の文字を削除し、残りの文字の順序を保ったまま作られる文字列のことです。このうち、前から読んでも後ろから読んでも同じになるものを回文部分列と呼びます。 例として、文字列「abcb」を考えてみましょう。この文字列には次の6つの回文部分列が存在します。 a b(先頭) c b(末尾) bb(先頭と末尾のb)

このチュートリアルでは、C++ を使って「ある整数の約数のうち、完全平方数であるもの(完全平方約数)」の個数を求めるプログラムを解説します。 ここでいう完全平方約数とは、与えられた数 n の約数の中で、1, 4, 9, 16 のようにある整数の 2 乗として表せる数のことを指します。 アプローチ 以下の手順で問題を解きます。 i を 1 から √n まで順に調べ、n が i で割り切れるかどうかを確認します。 n が i で割り切れる場合、i 自身が完全平方数であればカウントを 1 増やします。 同時に、ペアとなる約数 n / i も確認し、これが完全平方数であれば(i ≠ n/i の場合の

はじめにこの記事では、与えられた配列の中から「要素の合計が3の倍数になる」サイズ2または3のグループがいくつ作れるかを求めるC++プログラムを解説します。問題の概要整数の配列が与えられたとき、以下の条件を満たすグループの総数を数えます。グループのサイズは2つまたは3つの要素グループ内の要素の合計が3で割り切れること例として、配列 {3, 6, 7, 2, 9} を考えます。この場合、条件を満たすグループは8通り存在します。アルゴリズムのポイントすべての組み合わせを総当たりで調べると計算コストが大きくなりますが、各要素を3で割った余り(0・1・2)ごとの出現回数を数えれば、組み合わせの数を数式で

本記事では、指定された条件を満たすN桁の数値の個数を求めるプログラムについて解説します。具体的には、整数Nが与えられたとき、次の条件を満たすN桁の数値がいくつ存在するかを求めます。数値 + 逆順(数値) = 10N − 1例えばN = 4の場合、104 − 1 = 9999となるため、「数値とその逆順の和が9999になるような4桁の数」がいくつあるかを数えることになります。考え方この問題にはシンプルな数学的な性質があります。Nが奇数の場合: 条件を満たす数値は1つも存在しないため、答えは0になります。Nが偶数の場合: 各桁のペア(先頭と末尾、2桁目と末尾から2番目…)の和が必ず9になる必要があ

このチュートリアルでは、有向グラフにおいて指定された2つの頂点（始点と終点）をつなぐ経路（パス）が全部で何通り存在するかを求めるC++プログラムについて解説します。入力として有向グラフが与えられ、その中から2つの頂点間に成立しうるすべての単純経路（同じ頂点を2度通らない経路）の本数を数えるのが課題です。アルゴリズムの考え方：DFSとバックトラッキングこの問題は、深さ優先探索（DFS）にバックトラッキングを組み合わせることで解けます。手順は次の通りです。始点から探索を開始し、現在の頂点に「訪問済み」の印を付けます。現在の頂点が終点と一致していれば、経路数を1つ増やします。終点でなければ、隣接する

はじめにこのチュートリアルでは、m×n行列（グリッド）の左上から右下まで移動する際の、取り得るすべての経路の総数を求めるC++プログラムについて解説します。m×nの行列が与えられたとき、左上のセルから右下のセルへ到達するすべての移動経路を数えることが課題です。なお、移動は「右」または「下」のいずれかの方向のみ許されるものとします。アルゴリズムの考え方この問題は再帰を使ってシンプルに解くことができます。セル(m, n)に到達する経路の数は、「上隣のセル(m-1, n)に到達する経路の数」と「左隣のセル(m, n-1)に到達する経路の数」の合計になります。最上行または最左列にあるセルには、それぞれ

問題の概要 本記事では、変形ナイト（Modified Knight）が到達できるすべての位置の数を求めるC++プログラムについて解説します。 前提として、8×8のチェス盤が与えられます。私たちのタスクは、指定された手数において、変形ナイトが到達できるマスの総数を計算することです。 変形ナイトの移動パターン 標準的なチェスのナイトは「縦2・横1」「縦1・横2」の8方向にしか移動できません。しかし、この記事で扱う変形ナイトは、それに加えて斜めに隣接するマス（例：左上・右下など）への移動も許容しており、合計12方向へ移動することができます。 アルゴリズムの考え方 この問題は深さ優先探索（DFS）

本記事では、C++プログラミングにおいてゼロ除算（0による割り算）の例外を適切に処理する方法を、具体的なコード例とともに解説します。数学においてゼロによる除算は未定義の演算です。そのため、プログラム内でゼロ除算が発生すると、実行時エラーや予期しない動作につながる可能性があります。ユーザー側でエラーが発生しないよう、事前に適切な例外処理を実装しておくことが重要です。1. runtime_errorクラスを使用する方法C++の標準ライブラリには、実行時エラーを表すstd::runtime_errorクラスが用意されています。ゼロ除算を検出した時点でこの例外をスローし、呼び出し元で捕捉するのが最も基

このチュートリアルでは、積がK未満となる部分列(サブシーケンス)の個数を求めるプログラムについて解説します。問題設定は次のとおりです。非負の整数からなる配列と値kが与えられたとき、配列の要素を選んで構成できる部分列のうち、要素の積がk未満になるものの総数を求めます。動的計画法によるアプローチこの問題は動的計画法(DP)を使うことで効率的に解けます。ここでは、dp[i][j] を「先頭からj個の要素の中から選んだ部分列のうち、積がi未満になるものの個数」と定義します。遷移は次のように考えます。まず、j番目の要素 arr[j-1] を部分列に含めない場合の数は dp[i][j-1] です。次に、含

本チュートリアルでは、指定された範囲内にある数値のうち、「最小の約数(最小の素因数)」が K と一致するものの個数を求めるC++プログラムについて解説します。 問題の概要 範囲 [a, b] と整数 K が与えられたとき、この範囲に含まれる数値の中で「最小の約数が K であるもの」を数えるのが目的です。 ある数 n の最小の約数が K になるためには、次の2つの条件を満たす必要があります。 n が K で割り切れること 2 以上 K 未満のいずれの整数でも n が割り切れないこと また重要な点として、K が素数でない場合、条件を満たす数は存在しません(合成数が「最小の約数」となることはな

このチュートリアルでは、C++を使って「行列（マトリックス）の中で降順にソートされている列の数」を求めるプログラムについて解説します。 ここでは、ある行列が与えられたとき、その中から要素が降順（大きい値から小さい値へ）に並んでいる列を数えることが課題となります。 アルゴリズムの考え方 基本的なアプローチはシンプルです。各列について、下の行から上の行へ向かって隣り合う要素を順番に比較していきます。もし「上の要素が下の要素より小さい」という箇所がひとつでも見つかれば、その列は降順ではないと判断できます。最後まで問題なく確認できた列だけをカウントします。 サンプルコード #include <b

このチュートリアルでは、行列（マトリックス）の中から「ソート済みの行」がいくつあるかを数えるC++プログラムについて解説します。具体的には、m×n のサイズの行列が与えられ、その中から昇順または降順のいずれかで整列されている行をすべてカウントするのが課題です。アルゴリズムのポイント各行に対して以下の2つの判定を行い、どちらかに該当すればカウントします。昇順の判定：各行を左から右へ走査し、隣接する要素が常に増加していれば昇順とみなします。降順の判定：各行を右から左へ走査し、隣接する要素が常に減少していれば降順とみなします。計算量は O(m×n) となり、行列の全要素を一度ずつ確認するだけで効率的

はじめに本記事では、「総和がkで割り切れる部分配列(サブ配列)の個数を求める」プログラムについて解説します。具体的には、整数の配列と値kが与えられたとき、連続する部分配列のうち、その要素の合計がkで割り切れるものがいくつ存在するかを数えます。アルゴリズムのポイントすべての部分配列を素朴に調べるとO(n²)の計算量が必要になりますが、累積和(プレフィックスサム)と剰余演算を組み合わせることで、O(n + k)まで計算量を抑えられます。考え方の核心は次の通りです。先頭から順に累積和を計算し、それをkで割った余りごとに出現回数を記録する。累積和の差が部分配列の総和に相当するため、同じ余りを持つ2つの

このチュートリアルでは、素数の長さを持つ回文部分文字列の個数を求めるプログラムについて解説します。文字列が1つ与えられ、その中から「回文になっている」かつ「長さが素数である」すべての部分文字列を数えるのが課題です。解決のアプローチこの問題は、次の2つの処理を組み合わせることで効率よく解決できます。素数判定： エラトステネスの篩（ふるい）を使い、文字列の長さ以下の素数をあらかじめすべて求めておきます。回文判定： 各素数の長さ j について、すべての開始位置 i から長さ j の部分文字列を取り出し、両端から中央に向かって文字を比較して回文かどうかを確認します。C++での実装例#include &