C++

はじめに このチュートリアルでは、C++を使って0と1の個数が等しい最大の部分配列を見つけるアルゴリズムを解説します。与えられた配列の中から、0と1が同数ずつ含まれる最長の連続した部分配列を求める、定番のアルゴリズム問題です。 アルゴリズムの考え方 この問題を効率的に解くポイントは、配列内のすべての 0 を -1 に置き換える ことです。そうすることで、「0と1の個数が等しい部分配列を探す」という問題を「合計が0になる部分配列を探す」問題に言い換えられます。さらに、累積和とハッシュマップ（unordered_map）を組み合わせることで、計算量 O(n) という高速な処理が可能になります。 プ

問題概要 長さ n の整数配列と正の整数 k が与えられたとき、「要素数が k 個以上の連続する部分配列」の中から合計が最大となるものを求めます。全探索では非効率ですが、カダネのアルゴリズムとスライディングウィンドウを組み合わせることで、O(n) の時間計算量でこの問題を効率的に解くことができます。 アルゴリズムの手順 プログラムの流れは以下の通りです。 配列を初期化します。 サイズ n の max_sum 配列を用意し、max_sum[0] = a[0] とします。 カダネのアルゴリズムを使い、「各インデックスで終わる部分配列の最大合計」をすべて求めて max_sum 配列に保存します。

OpenCVでカラー画像を扱う際、ピクセルごとの値にアクセスできると、画像処理の幅が大きく広がります。本記事では、C++を使用してBGR形式のマルチチャンネル画像からピクセル値を読み取る方法を解説します。 まず、blue_Channel、green_Channel、red_Channel という3つの変数を宣言します。これらの変数は、読み取ったピクセル値を保存するために使用され、後述のforループ内で活用します。次に、画像を読み込むための行列として color_image_Matrix を宣言します。 ピクセル値を読み取る基本構文 ピクセル値の読み取りには、Matクラスの at<Vec

画像から特定の部分を切り出したい場合、まず対象となる領域を特定し、その領域を元の画像から別の行列（Mat）へコピーする必要があります。これがOpenCVにおけるROI（Region of Interest：関心領域）の基本的な仕組みです。 ROIの基本的な考え方 この例では、冒頭で2つのMat行列が宣言されています。その後、「image_name.jpg」という名前の画像が「image1」行列に読み込まれます。特に注目すべきは次の行です。 image2 = image1(Rect(100, 100, 120, 120)); この一行が、画像内の指定された領域を切り出し、「image2」行列に格

ラテン方格（ラテン方陣）とは、特別なパターンを持つ行列のことです。まずはいくつかの例を見ながら、そのパターンを確認していきましょう。1 2 2 1 1 2 3 3 1 2 2 3 1 1 2 3 4 4 1 2 3 3 4 1 2 2 3 4 1上記の例のように、ラテン方格はさまざまなサイズで生成されます。しかし、これらの行列のパターンを注意深く観察すると、前の行の最後の数字が、次の行の最初の要素として現れるという規則性があることがわかります。これこそがラテン方格に隠されたパターンです。この記事では、入力として与えられた n に対して、このような行列を生成するプログラムを作成します。アルゴ

ある整数Nと、M個の数字からなる配列が与えられます。このとき、与えられたM個の数字を使って作成できるN桁の数のうち、5で割り切れるものの個数を求めるのが本記事のテーマです。まず、入力と出力の例を見ながら、問題の内容を確認していきましょう。入力 −N = 2 M = 3 arr = {5, 6, 3}出力 −2この場合、5で割り切れるN桁の数は「35」と「65」の2つです。続いて、別の例を見てみます。入力 −N = 1 M = 7 arr = {2, 3, 4, 5, 6, 7, 8}出力 −1配列の中で5で割り切れる1桁の数は「5」だけなので、答えは1となります。つまりこの問題は、「与えられた

3つの整数 x、y、n が与えられたとき、x の倍数と y の倍数をすべて統合して昇順に並べたリストを作り、その中から n 番目の値を求める問題です。まずは具体例で確認してみましょう。 入力例 x = 2 y = 3 n = 7 出力例 10 考え方 2 の倍数(最初の7個)は「2, 4, 6, 8, 10, 12, 14」、3 の倍数(最初の7個)は「3, 6, 9, 12, 15, 18, 21」です。 これらを統合し、重複を除いて昇順にソートすると「2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 18, 21」となります。このリストの7番目の値は 10 です。 アルゴ

桁の合計が10になる数には、次のようなものがあります。19, 28, 37, 46, 55, 64, 73, 82, 91 ...この数列をよく観察すると、隣り合う数がすべて9ずつ増加していることがわかります。ただし、9ずつ増やしていく過程では、桁の合計が10にならない数も途中に現れます。それでも、桁の合計が10になる数はすべてこの方法で漏れなく見つけられます。そこで、9ずつ増加させながら各数の桁の合計をチェックするループを作成すれば、n番目の数を効率よく求めることができます。以下に入力例と出力例を示します。入力例3 7出力例37 73アルゴリズム整数 n を初期化します。カウンターを0で初期

数字 {0, 1, 2, 3, 4, 5} のみを使用して作られる数を小さい順に並べると、次のような数列になります。0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, ...この数列は、最初の6つの数字をもとに、「既存の数 × 10 ＋ 各数字」というシンプルなパターンを繰り返すことで生成できます。具体的な生成過程を見てみましょう。1 * 10 + 0 = 10 1 * 10 + 1 = 11 1 * 10 + 2 = 12 1 * 10 + 3 = 13 1 * 10 + 4 = 14 1 * 10 + 5 =

丁寧数（ポライト数）とは 丁寧数（polite number）とは、2つ以上の連続する正の整数の和として表すことができる正の整数のことです。 丁寧数の列は以下のようになります。 3, 5, 6, 7, 9, 10, 11, 12, 13, 14 ... なお、2の累乗（1, 2, 4, 8, 16 ...）は連続する正の整数の和として表せないため、丁寧数には含まれません。この性質が、後述する公式で対数（底2）が使われる理由になっています。 n番目の丁寧数を求める公式 n番目の丁寧数を求めるには、次の公式を使用します。 n + log2(n + log2(n)) C++の標準ライブラリにある

はじめに N乗根とその計算結果が与えられたとき、numberN = result を満たす元の数値を求める必要があります。本記事では、C++を使ってこの問題を解く方法を解説します。 具体例 入力 result = 25 N = 2 出力 5 52 = 25 となるため、上記の例では出力は 5 になります。 入力 result = 64 N = 3 出力 4 43 = 64 となるため、上記の例では出力は 4 になります。 アルゴリズム この問題は、1から順番に整数を試し、その数のN乗が結果と一致するかを確認するシンプルな線形探索（全探索）で解くことができます。 カウンタ変数 i を 1

本記事で扱う数列は「2, 12, 36, 80, 150, …」です。 この数列をよく観察すると、n 番目の項が n2 + n3 という式で表せることに気づきます。実際に確認してみましょう。 n = 1 のとき: 12 + 13 = 1 + 1 = 2 n = 2 のとき: 22 + 23 = 4 + 8 = 12 n = 3 のとき: 32 + 33 = 9 + 27 = 36 n = 4 のとき: 42 + 43 = 16 + 64 = 80 n = 5 のとき: 52 + 53 = 25 + 125 = 150 このように、各項は「n の 2 乗と n の 3 乗の和」になっている

本記事では、数列 1, 11, 55, 239, 991, … のN番目の項をC++で求める方法を解説します。この数列をよく観察すると、各項は次の一般項（公式）で表せることがわかります。n番目の項 = 4n − 2n − 1実際に確認してみましょう。n = 1 のとき： 41 − 21 − 1 = 4 − 2 − 1 = 1n = 2 のとき： 42 − 22 − 1 = 16 − 4 − 1 = 11n = 3 のとき： 43 − 23 − 1 = 64 − 8 − 1 = 55このように、公式が数列のすべての項と一致していることが確認できます。アルゴリズム項数 N を初期化します。数列の一

今回扱う数列は「1, 17, 98, 354, …」です。この数列を注意深く観察すると、n 番目の項が「4乗の累積和」で表されていることがわかります。具体的なパターンを見てみましょう。1 = 1^4 17 = 1^4 + 2^4 98 = 1^4 + 2^4 + 3^4 354 = 1^4 + 2^4 + 3^4 + 4^4 ...つまり、n 番目の項は「1 から n までの各整数の4乗をすべて足し合わせた値」になります。アルゴリズム求めたい項番号 n を用意します。結果を格納する変数を 0 で初期化します。1 から n まで繰り返すループを作成します。現在の数の4乗を結果に加算してい

K桁のN番目の回文数を求めるにはK桁のN番目の回文数を求める場合、最初のK桁の数から順に1つずつ確認し、N番目の回文数が見つかるまで反復処理する方法が真っ先に思い浮かびます。しかし、この単純なアプローチは非常に非効率です。ぜひ一度ご自身でも試してみてください。ここでは、K桁のN番目の回文数を効率的に求める方法を紹介します。効率的なアプローチの考え方回文数は「前半部分」と「後半部分」の2つに分けることができます。そして、前半部分の数字を逆順に並べ替えたものが後半部分と一致するという性質を持っています。つまり、前半部分さえ決まれば、回文全体が一意に定まるというわけです。K桁のN番目の回文数の前半部

はじめに本記事では、C++を使ってn番目の五角数（Pentagonal Number）を求めるプログラムの作成方法を解説します。五角数とは、点や小石を正五角形の形に並べたときに表される数のことです。図形的なイメージを掴みたい場合は、Wikipediaなどの解説記事を参考にすると理解が深まります。五角数とは五角数は、以下の漸化式・公式によって定義されます。n番目の五角数 = (3 × n² − n) ÷ 2この公式に従うと、五角数は次のような数列になります。1, 5, 12, 22, 35, 51, 70, 92 ...アルゴリズム整数 n を初期化します。上記の公式を使って n 番目の五角数を

「スマート数（Smart Number）」とは、3つ以上の異なる素因数を持つ整数のことです。この記事では、与えられた数 N に対して、N 番目のスマート数を求めるアルゴリズムとその C++ 実装を解説します。スマート数の列は以下のように始まります。30, 42, 60, 66, 70, 78...例えば、最初のスマート数である 30 は、素因数として 2・3・5 の3つの異なる素数を持っているため、スマート数と判定されます。アルゴリズム求めたい番号 N を初期化します。カウント用の変数 count を 0 で初期化します。ある数が素数かどうかを判定する関数を作成します。ある数がスマート数かどう

0より大きい数は自然数と呼ばれます。自然数とは、次のような正の整数のことです。1, 2, 3, 4, 5, 6, 7...アルゴリズム出力したい自然数の個数 n を初期化します。1から n まで繰り返すループを作成します。現在の数値を出力します。反復変数を1ずつ増やします。C++での実装例以下は、上記のアルゴリズムをC++で実装したコードです。#include <bits/stdc++.h> using namespace std; void printNaturalNumbers(int n) { for (int i = 1; i <= n; i++) {

バイナリ行列（0と1だけで構成された行列）が与えられたとき、各セルから最も近い「1」のセルまでの最小距離を求める問題について解説します。 ここでの距離はマンハッタン距離、すなわち「行の差の絶対値 ＋ 列の差の絶対値」として定義されます。 入力例と出力例 入力 0 0 1 1 1 0 0 0 0 出力 1 1 0 0 0 1 1 1 2 この出力は、行列内のすべてのセルについて、そのセルから最も近い「1」までの距離を表しています。元々「1」であるセルの距離は当然 0 になります。 アルゴリズム 基本となるアプローチは全探索（ブルートフォース）です。手順は以下の通りです。 指定したサイズの

数値 n が与えられたとき、n より小さい最も近い素数を求める問題について解説します。この問題は、n - 1 から順に素数かどうかをチェックしていけば、簡単に答えを見つけることができます。まずは具体例を見てみましょう。入力例と出力例入力:10出力:710 未満の数の中で最も近い素数は 7 であるため、出力は 7 となります。アルゴリズム解法の手順は以下の通りです。数値 n を初期化します。n - 1 から 1 まで逆順にループを回します。最初に見つかった素数を返します。n 未満に素数が存在しない場合は -1 を返します。C++での実装上記のアルゴリズムを C++ で実装したコードが以下です。#