C++

問題の概要文字列 s と、同じ長さの複数の単語を含むリスト words が与えられます。このとき、words 内の各単語をちょうど1回ずつ使用し、間に余計な文字を挟まずに連結してできる部分文字列が、s の中に出現する開始インデックスをすべて求めるのが目的です。たとえば、入力が wordgoodgoodgoodword、単語リストが [word, good] の場合、出力は [0, 12] になります。これは、インデックス 0 から始まる部分文字列が wordgood、インデックス 12 から始まる部分文字列が goodword であり、どちらも条件を満たすためです。解法のアプローチこの問題は、

問題概要 次のような関数が与えられます。 f(x) = (x6 + x2 + 9894845) % 971 任意の x の値に対して f(x) の値を求めるのが課題です。例えば x = 5 を入力した場合、出力は 469 になります。 アプローチ：繰り返し二乗法（バイナリ法） x をそのまま6乗すると値が非常に大きくなり、64ビット整数でもオーバーフローする恐れがあります。そこで、べき乗の計算途中で都度剰余を取りながら値を小さく保つ「繰り返し二乗法」を利用します。この方法なら計算量は指数のビット数に比例する O(log e) で済み、大きな x に対しても高速かつ安全に計算できます。 アルゴリ

C++の継承と多態性（ポリモーフィズム）には興味深い挙動がいくつかあります。本記事では「仮想関数を非仮想関数の内部から呼び出すとどうなるのか」というテーマについて、まず2つのケースを実際のコードで確認し、その後で内部的な仕組みを分析します。 ケース1：仮想関数を一切使わずにプログラムを実行する ケース2：非仮想関数の内部で仮想関数を呼び出してプログラムを実行する ケース1：仮想関数を使わない場合 まずは、virtualキーワードを使用しない次の実装例を見てみましょう。 #include <iostream> using namespace std; class BaseCla

この記事では、C++における興味深いトピックである「派生クラスのメソッドに、基底クラスよりも厳しいアクセス制限を付けた場合の挙動」について解説します。具体的なコード例とその出力結果を通じて、アクセス指定子がどのように機能するのかを詳しく見ていきましょう。例：派生クラスでメソッドをprivateにした場合まずは以下のコードを見てください。基底クラスではpublicとして宣言されている仮想関数display()を、派生クラスではprivateとしてオーバーライドしています。#include <iostream> using namespace std; class BaseClass

この記事では、C++プログラムにおいて変数やオブジェクトがメモリ上のどこに格納されるのかについて詳しく解説します。C++では、オブジェクトを格納できるメモリ領域は大きく分けて次の2つがあります。スタック − ブロック内で宣言されたローカル変数やオブジェクトは、すべてスタック領域に格納されます。main関数も関数の一種であるため、その内部で宣言された要素も同様にスタックに格納されます。ヒープ − new演算子などで動的に確保されたオブジェクトは、ヒープ領域に格納されます。スタックに格納されるオブジェクトブロックや関数内で宣言されたオブジェクトのスコープは、そのオブジェクトが生成されたブロック内に

C++において、メンバ変数やメンバ関数を一切持たない「空のクラス」を定義した場合、そのサイズは果たして0バイトになるのでしょうか。結論から言うと、C++の標準規格ではサイズが0のオブジェクト（クラス）の存在を許していません。その理由は、もしサイズ0のオブジェクトが許されてしまうと、互いに異なる2つのオブジェクトが同一のメモリアドレスを持つ可能性が生じるためです。このため、たとえ空のクラスであっても、必ず最低1バイト以上のサイズを持つことが保証されています。一般的に、空のクラスのサイズは1バイトです。以下のコード例で実際に確認してみましょう。例1：空のクラスのサイズを確認する#include&l

この記事では、動的メモリ割り当てを通じてのみオブジェクトを生成できるC++クラスの作成方法を解説します。スタック上への直接生成はコンパイルエラーとなるよう設計します。 基本アイデア：デストラクタをprivateにする 実現方法は非常にシンプルです。対象クラスのデストラクタをprivateで宣言します。 デストラクタがprivateの場合、スタック領域に生成されたオブジェクトがスコープを抜けるとき、コンパイラは自動的にデストラクタを呼び出してオブジェクトを破棄しようとします。しかし、privateなデストラクタには外部からアクセスできないため、コンパイルエラーが発生します。 一方、new演算子で

本記事では、C++においてSTL関数が返すポインタ（イテレータ）からインデックスを求める方法を詳しく解説します。C++には、目的の要素が格納されているメモリ上のアドレスを指すポインタを返す組み込み関数が数多く存在します。しかし、これらの関数が返すのはあくまでメモリ上の位置であり、コンテナ内での実際のインデックスとは直接対応していません。典型的な例がstd::max_element()関数です。この関数はコンテナ内の最大要素を検索できますが、戻り値として返すのはその要素のインデックスではなく、メモリ上のアドレス（イテレータ）です。場合によっては、このアドレスからインデックスを取得したい場面があり

ガウスフィルターとはガウスフィルターは、画像処理の分野で最もよく使われるフィルターの一つです。画像に含まれるノイズを低減したり、画像を滑らかにぼかす（スムージング）ために利用されます。本記事では、C++を使って2次元ガウスカーネル（フィルター係数）を生成する方法を解説します。2次元ガウス分布の数式2次元のガウスカーネルは、以下のガウス分布の式に基づいて計算されます。$$G(x,y)= \frac{1}{2\Pi\:\sigma^{2}}e^{-\frac{x^{2}+y^{2}}{2\sigma^{2}}}$$ここで、x, y はカーネル中心からの距離、σ（シグマ）は分布の広がりを決める標準偏

本記事では、C++のSTL（標準テンプレートライブラリ）関数を使ってテストケースを効率的に生成する方法を解説します。配列を扱うプログラムのテストケースを手動で作成するのは、非常に手間がかかり非効率な作業になりがちです。そこで活躍するのが、C++が標準で提供している2つの便利な関数です。generate()メソッドとはC++のstd::algorithm::generate()は、引数なしで呼び出されるジェネレータ関数（gen）が返す値を、指定した範囲[first, last)内のすべての要素に順番に代入する関数です。この関数は3つのパラメータを受け取ります。first：範囲の先頭位置を指す前方

この記事では、C++のSTLに含まれるcomplexクラスを使ってPointクラスを作成し、幾何学関連の問題に応用する方法を解説します。複素数は、STLのcomplexクラス（#include <complex>）で簡単に扱うことができます。 Pointクラスの定義 complexをpointとして扱うために、complex<double>に「point」という別名（typedef）を付けます。さらに、complexクラスのreal()をx、imag()をyとしてマクロ定義することで、Pointクラスと同様の操作が可能になります。 #include <comple

C++のSTLには、キーと値のペアを格納できる連想コンテナが用意されています。本記事では、その代表格であるmapとunordered_mapの基本的な使い方と、要素を走査（トラバース）する方法を解説します。mapコンテナとはmapは、各要素を「キー」と「値」のペアとして管理する連想コンテナです。内部的にはハッシュマップ的な仕組みで要素が整理されており、同じキーを持つ要素は2つ以上存在できません。この特性を活かすことで、出現回数の集計などが簡潔に実装できます。mapの主なメンバ関数begin()：mapの先頭要素を指すイテレータを返します。end()：最後の要素の次（理論上の末尾）を指すイテレー

本記事では、C++11から導入された「均一初期化（Uniform Initialization）」について詳しく解説します。均一初期化とは、プリミティブ型からアグリゲート（集約体）まで、あらゆる変数やオブジェクトを一貫した同じ構文で初期化できる機能のことです。具体的には、波括弧（{}）で初期化子の値を囲む「ブレース初期化（波括弧初期化）」と呼ばれる記法を指します。この記法により、これまで型ごとに異なっていた初期化の書き方を統一でき、コードの可読性と保守性が向上します。基本構文type var_name{argument_1, argument_2, .... argument_n}動的確保した

本記事では、C++におけるユーザー定義リテラル（User Defined Literals：UDL）の概念について解説します。ユーザー定義リテラルは、C++11から導入された機能です。C++にはもともと組み込み型向けにさまざまなリテラルが用意されていますが、その表現力には限界があります。C++の組み込みリテラルの例31（整数）3.5（double型）4.2F（float型）p（文字）31ULL（unsigned long long型）0xD0（16進数の符号なし整数）pq（文字列）なぜユーザー定義リテラルが必要なのか組み込みリテラルだけでは不十分なケースがあります。たとえば、重量を表す変数を定

1つの2次元行列が与えられたとき、反復アプローチを使ってそれを2Dリンクリストに変換する方法を解説します。変換後のリンクリストでは、各ノードが右方向へのポインタ（right）と下方向へのポインタ（down）を持つ構造になります。例として、次のような入力行列を考えてみましょう。102030405060708090この場合、出力は各行・各列がポインタで連結された2Dリンクリストになります。アルゴリズムの手順この問題は、以下の手順で解くことができます。real_head を NULL で初期化します。サイズ m の配列 head_arr を定義し、各行の先頭ノードを保持できるようにします。i を 0

行列(マトリックス)が与えられたとき、再帰的なアプローチを用いて、それを2Dリンクリストへ変換する方法を解説します。 ここで作成するリストの各ノードは、right(右方向)ポインタとdown(下方向)ポインタの2つのポインタを持ちます。rightポインタは同じ行の次の要素を、downポインタは同じ列の一つ下の行の要素を指します。 問題の概要 例えば、次のような3×3の行列が入力として与えられたとします。 102030405060708090 この場合、出力は次のようになります。各要素がノードとなり、横方向はrightポインタ、縦方向はdownポインタによって連結された、格子状のデータ構造が生成

平衡二分探索木（Balanced BST）と目標値（target sum）が与えられたとき、合計が目標値と等しくなるペアが木の中に存在するかどうかを判定するメソッドを実装することを考えます。この際、二分探索木は不変（immutable）である、つまり木の構造を変更してはいけないという制約があることに注意が必要です。例えば、入力が以下のような木だったとします。この場合、出力は (9 + 26 = 35) となります。解決アプローチこの問題は、ソート済み配列でよく使われる「二ポインタ（Two Pointers）」手法を、二分探索木に応用することで解けます。具体的には、以下の2つの走査を同時に進めて

要素の集合が与えられたとき、どのような並び順(順列)にすればマージソートにとって最悪のケースになるかを見つける問題です。マージソートは漸近的には常に O(n log n) の時間計算量で動作しますが、入力の並び方によっては比較回数が増え、実際の処理に多くの時間がかかることがあります。ここでは、典型的なマージソートアルゴリズムでソートを実行した際に、より多くの比較を必要とする入力順列を求めます。たとえば、入力が [11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26] の場合、出力は [11,19,15,23,13,21,17,25,12,20,16,2

問題の概要 0からN-1の範囲の値を含む、サイズNのソートされていない整数配列が与えられます。この配列を複数の部分（パーティション）に分割し、各部分を個別にソートしたうえで連結したとき、全体がソート済みの長さNの配列になるようにします。このとき実現できる分割数の最大値を求めるのが本記事のテーマです。 各パーティションの中身がソートされていなくても構いません。ただし、N個の要素が0〜N-1の範囲にちょうど1回ずつ現れるため、ソート後の配列では必ず「インデックスと値が一致する」（Arr[i] = i）という性質が成り立ちます。この性質が解法の鍵となります。 解法のアプローチ 各要素を左から順に走

問題の概要 5つの整数 N、A、B、X、Y が与えられます。目標は、1からNまでの範囲の各数について次の条件を確認し、利益を最大化することです。 ある数が A で割り切れる場合、利益が X 増加します。 ある数が B で割り切れる場合、利益が Y 増加します。 ただし、同じ数に対して利益を加算できるのは1回だけです。そのため、AとBの両方で割り切れる数については、XとYのうち大きい方を選ぶのが最適戦略となります。 具体例を見てみましょう。 例1 入力: N=4, A=2, B=3, X=2, Y=3 出力: 最大化された利益は 7 説明: 2と4はA（2）で割り切れるため、利益は0→2→