C++

本記事では、C++ STLのstd::merge()関数を使用して、ソート済みの2つの配列を素早くマージ（統合）する方法について解説します。 問題を解く前に、まずはC++ STLにおけるstd::merge()の基本から見ていきましょう。 std::merge()とは？ std::merge()は、C++標準ライブラリ（STL）の<algorithm>ヘッダーファイルで定義されている組み込み関数です。 merge()は、ソート済みの2つの範囲（レンジ）をマージするために使用され、2つのソート済み範囲を結合して、1つのソート済み範囲を生成します。すべての要素が小なり演算子（<

デストラクタ（Destructor）とは、C++のクラスに属する特別なメンバ関数の一つで、クラスのオブジェクトを破棄する役割を担います。 デストラクタが呼び出されるタイミング デストラクタは、プログラム中でオブジェクトがスコープ外に出ったときに自動的に呼び出されます。具体的には、以下のようなケースが該当します。 関数のスコープを抜けるとき プログラムが終了するとき ローカル変数として初期化されたオブジェクトが属するブロックがスコープ外に出るとき delete演算子によってオブジェクトが削除されるとき サンプルコード1：値を返す場合 まず、次のコードを見て、実行結果を予想してみてください

問題概要この問題では、整数値 N が与えられます。1 から N2 までの数値を、各行の要素の合計がすべて等しくなるように、サイズ N×N の2次元行列（マトリックス）に配置して出力することが課題です。具体例を見て問題を理解しましょう。入力： N = 4出力：1 6 11 16 2 7 12 13 3 8 9 14 4 5 10 15この場合、各行の要素の合計はすべて 34 になります。解決アプローチこの問題を解くには、各行の合計が等しくなるように各要素を適切な位置に配置する必要があります。ここでは貪欲法（グリーディー法）の考え方を用いて、行ごとに正しい要素を配置していきます。まず、1 から N

この問題では、3つの整数値 K、N、M が与えられます。目的は、N×M のチェス盤上に、どの2つのナイトも互いに攻撃し合わないように K 個のナイトを配置することです。有効な配置方法が1通りも存在しない場合もあれば、複数の配置方法が存在する場合もあります。プログラムは、考えられるすべての有効な配置パターンを出力できなければなりません。 ナイトと「攻撃」の定義 ナイト（Knight）は、チェスの駒の一種で、ある方向に2マス進んだ後、左右いずれかに1マス移動するという特徴的な動きを持ちます。チェス盤上であれば、どの方向にも移動可能です。 攻撃（Attack）とは、ある駒が1回の有効な移動によって、

この記事では、同じ直線上に並ぶ n 個の点の座標が与えられたとき、その中から k 個の要素を選んで配置し、選ばれた要素どうしの最小距離が最大になるようにする問題を解説します。これは「aggressive cows（アグレッシブ・カウ）問題」としても知られる古典的な最適化問題で、二分探索と貪欲法を組み合わせることで効率的に解くことができます。 問題の概要と入出力例 入力：array = {3, 5, 6, 9, 1, 8}、k = 3 出力：4 配列をソートすると {1, 3, 5, 6, 8, 9} となります。ここで 1・5・9 の3点を選ぶと、隣接する要素間の距離はそれぞれ 4 になり、こ

「パイプと貯水槽（Pipes and Cisterns）」の問題は、公務員試験や就職試験など各種の適性試験で非常によく出題される定番テーマです。一見難しそうに感じますが、基本の考え方さえ身につければ決して苦手な分野ではありません。この記事では、基本ルールの確認から実際の解き方まで、例題を交えながらわかりやすく解説します。 パイプと貯水槽の問題とは？ このタイプの問題は、タンク（貯水槽）に水を入れるパイプや水を排出するパイプが登場し、「全部で何時間で満タンになるのか」「逆に空になるのか」を求めるものです。 まず、押さえておきたい基本ポイントを整理しましょう。 パイプには「給水管（注入口）」

この記事では、整数 n が与えられたとき、n 未満にあるすべてのピアポント素数(Pierpont Prime)を求めて出力する方法を解説します。 ピアポント素数とは ピアポント素数とは、次の形式で表される特殊な素数のことです。 p = 2i × 3k + 1 ここで p は素数、i と k は非負の整数です。つまり「2 のべき乗と 3 のべき乗の積に 1 を加えた数」が素数となるとき、その数をピアポント素数と呼びます。たとえば 13 = 22×31+1、19 = 21×32+1、37 = 22×32+1 であり、これらはすべてピアポント素数です。 入力例と出力例 入力: n = 50 出力:

問題概要この問題では、N個のインデックス位置を表す n 個の要素からなる配列 arr[] と、C個の磁石が与えられます。目的は、最も近い2つの磁石の間の距離ができるだけ大きくなるように、すべての磁石を配置することです。入力例array = { 1, 4, 6, 12, 28, 44 }、C = 4出力例11解法のアプローチこの種の「最大化したい最小値を求める」問題は、二分探索（バイナリサーチ）を用いることで効率的に解くことができます。基本的な考え方は次のとおりです。まず、仮の最大距離 mid を固定します。その距離 mid 以上の間隔を保ちながら、C個の磁石をすべて配置できるかどうかを判定しま

問題の概要この問題では、配列 arr[] と2つの整数 M および K が与えられます。与えられた配列の要素を使って新しい配列を作成することが求められます。新しい配列のサイズは M であり、かつサイズが K より大きい任意の部分配列には、すべて同じ要素が含まれていてはいけません。そして、作成した配列の要素の合計として可能な最大値を出力します。入力例入力 − arr[] = {1, 2, 4, 5, 7 }, M = 5, K = 2説明 − 条件を満たす配列は {7, 7, 5, 7, 7} となります。この配列では、サイズが2より大きい部分配列にすべて同じ要素が並ぶことはありません。解決策の

この問題では、二分木(binary tree)が与えられ、その全ノードをジグザグ状(ZigZag)に出力することが求められます。 まず、具体例を使って問題を確認しましょう。 上記の二分木をジグザグ走査すると、各ノードは次の順序で出力されます。 3 5 1 8 7 0 4 1層目は左から右、2層目は右から左…というように、レベルが変わるごとに走査の向きが交互に反転するのがジグザグ走査の特徴です。 解法の考え方 この問題を解くには、二分木をレベル順(幅優先)で走査し、各レベルが終わるたびに走査の向きを反転させます。 ここでは、「現在のレベル用(c

問題の概要 この記事では、2次元行列（マトリックス）のすべての要素を対角線に沿った順序、いわゆる「ジグザグ（対角）トラバーサル」で出力する方法を解説します。 まず、具体例を使って問題を理解しましょう。次のような3×3の行列が与えられたとします。 1 2 3 4 5 6 7 8 9 出力 − 1 4 2 7 5 3 8 6 9 対角トラバーサルのパターン 行列をジグザグ形式で出力する際には、どのようなパターンで要素が並ぶのでしょうか。下の図のように、要素は左下から右上へ向かう斜めのラインごとに順番に出力されます。

この問題では、二分木が与えられ、その木をジグザグ（鋸歯状）レベル順で走査して出力することが求められます。ポイントは、この走査をたった1つのキューだけを使って実現することです。問題の例まず、具体例で問題を理解しましょう。以下のような二分木を考えます。出力：3 1 7 2 8 9 5ご覧のとおり、第1レベルは左から右へ、第2レベルは右から左へ、第3レベルは再び左から右へと、レベルごとに方向を交互に入れ替えながらノードを出力しています。解決アプローチ：単一キュー＋区切りフラグ通常、ジグザグ走査には2つのスタックや双方向キュー（deque）を使う方法が知

ゼロ初期化（Zero initialization）とは、C++においてオブジェクトの初期値をゼロに設定することを指します。明示的な初期化子が与えられなかった場合でも、変数が予測可能な状態で始まることを保証する重要な仕組みです。 構文 T{}; char array[n] = ; 波括弧 {} を用いた初期化や、空文字列による文字配列の初期化が、ゼロ初期化に該当します。 ゼロ初期化が行われる主なケース 静的記憶域期間（static）またはスレッドローカル記憶域期間（thread_local）を持つ名前付き変数が、プログラム起動時にゼロで初期化される場合。 クラス型ではない基本的な型（int、

Zバッファ（デプスバッファ）とはZバッファ（Z-buffer）は「デプスバッファ（Depth Buffer）」とも呼ばれる、隠面消去（hidden surface removal）に用いられる手法です。各ピクセルごとに奥行き（深度）情報を記録し、視点から最も近い表面だけを描画することで、正しい前後関係を持つ画像を実現します。隠面検出（Hidden Surface Detection）とは複数のオブジェクトやサーフェスを含むシーンでは、他のオブジェクトの背後に隠れた部分が存在します。画像を正しく表示するためには、こうした見えない面を取り除く必要があります。この識別・解決の課題は「隠面問題（hid

Zアルゴリズムは、文字列の中に特定のパターンが出現する位置を線形時間で検索するためのアルゴリズムです。文字列の長さを n、検索したいパターンのサイズを m とすると、計算にかかる時間は O(m+n) のオーダーに収まります。 Zアルゴリズムでは、「Z配列」と呼ばれるデータ構造を利用してパターンの出現位置を効率よく見つけます。 Z配列とは Z配列は、元の文字列と同じ長さを持つ配列です。各要素には、文字列の i 番目の位置から始まる部分文字列のうち、文字列そのものの接頭辞（プレフィックス）と一致する最長の長さが格納されます。 例えば、文字列 aabxaabxcaabxaabxay の場合、各位置に

この記事では、n個の要素からなる整数型配列と整数値kが与えられたとき、「セットビット(値が1になっているビット)の数がkと一致する要素」だけを抜き出し、それらすべてのXOR(排他的論理和)を求める方法を解説します。 問題の例 入力 array = {2, 12, 44, 103, 17} , K = 3 出力 44 まず、各要素を二進数で表し、セットビットの数を確認してみましょう。 2 → 二進数「10」→ セットビット数:1 12 → 二進数「1100」→ セットビット数:2 44 → 二進数「101100」→ セットビット数:3 103 → 二進数「1100111」→ セットビット数:

任意の型の変数が与えられ、その値に対して関数 log1p() を使った計算結果を求めることを考えます。log1p() は引数「a」を受け取り、戻り値を返す解析関数です。この関数は log(1 + x)、つまり自然対数を計算するものであり、x が非常に小さな値の場合でも通常の log(1+x) 計算よりも高い精度で結果を得られる点が大きな特徴です。構文double log1p (double x); // 引数 x の範囲は [-1, ∞) float log1p (float x);戻り値の型 − 引数が -1 より大きい場合は非ゼロの値を返します。引数が -1 以下の場合は非数値（NaN）を

この問題では、N×N の行列と複数のクエリが与えられます。各クエリには、元の行列から切り出す部分行列の左上と右下の座標が含まれており、その部分行列に含まれるすべての要素のXOR（排他的論理和）を求めることが課題です。具体例を使って問題を確認しましょう。入力arr[][] = {{1, 2, 3} {4, 5, 6} {7, 8, 9}} クエリ: {0,0, 2,2}, {1, 2, 2, 2}出力1 15解説クエリ 1 : 1^2^3^4^5^6^7^8^9 = 1 クエリ 2 : 6^9 = 15解法のアプローチ：累積XOR（プレフィックスXOR）行列この問題を効率的に解くには、あらかじめ

問題概要 この問題では、整数配列 arr[] と、配列上の範囲 L から R を指定するクエリが与えられます。目的は、L から R までの部分配列（サブアレイ）のXORを計算して出力することです。 具体例で問題を確認してみましょう。 入力: array = {1, 4, 5, 7, 2, 9}、L = 1、R = 5 出力: 13 説明: 求める値は 4 ^ 5 ^ 7 ^ 2 ^ 9 の計算結果である 13 です。 解決のための考え方 この問題を効率的に解くには、次のXORの性質を利用します。 同じビット位置の複数のビットをXORするとき、1 の個数が奇数であれば結果は 1、偶数であれば結

XOR暗号とはXOR暗号（XOR暗号化）は、データを暗号化する手法の一つで、総当たり攻撃（ブルートフォース攻撃）によって解読することが困難な暗号方式として知られています。総当たり攻撃とは、ランダムに暗号鍵を生成し、それが正しい鍵と一致するかどうかを順番に照合していく攻撃手法のことです。XOR暗号はこの手法に対して一定の耐性を持っています。暗号化の仕組みXOR暗号を実装する手順は非常にシンプルです。まず、暗号鍵として任意の1文字を定義します。次に、暗号化したい文字列のすべての文字と、この暗号鍵との間でXOR（排他的論理和）演算を行います。これにより、文字列内のすべての文字が暗号化されます。XOR