C++

はじめにこの記事では、ユニークな要素のみで構成された配列の中から、XOR（排他的論理和）の結果が0になる一意なトリプレット (x, y, z) の個数を数える方法について解説します。ここで「一意なトリプレット」とは、3つの要素がすべて異なる値であり、同じ3つの数字からなる組み合わせは1つとしてカウントするという意味です。まずは、具体的な入力と出力の例を見てみましょう。入力 : arr[ ] = { 5, 6, 7, 1, 3 } 出力 : 2 説明 : { 5, 6, 3 } と { 6, 7, 1 } の2つのトリプレットのXORが0になります。 入力 : arr[ ] = { 3, 6,

この記事では、グリッド上の2つの固定された点の間を移動する経路の総数を求める問題を取り上げます。具体的には、点Aはグリッドの左上、点Bは右下に固定されており、AからBへ移動する方法が何通りあるかを計算します。問題の入出力例入力 : N = 5 出力 : 252 入力 : N = 4 出力 : 70 入力 : N = 3 出力 : 20この問題は、シンプルな観察によって数式として定式化できます。解法のアプローチグリッド上をAからBへ移動するためには、右方向にちょうどn回、下方向にちょうどn回移動する必要があります。つまり、合計2n回の移動のうち、どの順番で右方向・下方向に進むかを選ぶ組み合わ

括弧を含む文字列が与えられたとき、無効な括弧を取り除くことで得られる、考えられるすべての有効な括弧列を出力する問題を考えてみましょう。まずは具体例から見ていきます。 入力 : str = ()())() 出力 : ()()() (())() 2つの解が存在します ()()() と (())() 入力 : str = (v)())() 出力 : (v)()() (v())() この問題では、バックトラッキングの考え方を用いることで、条件を満たすすべての有効な文字列を出力できます。 解決のためのアプローチ このアプローチでは、BFS(幅優先探索)を使って、開き括弧と閉じ括弧を1つずつ順番に削除

問題の概要 2で余りなく割り切れる整数は「偶数」と呼ばれます。本記事では、数値nが与えられたときに、「各桁の数字の合計が偶数となるn番目の数」を求める方法を解説します。各桁の合計が偶数となる最初の5つの数は、2、4、6、8、11です。具体的な例を見てみましょう。 入力 : n = 5 出力 : 11 説明 : 各桁の合計が偶数となる最初の5つの数は 2, 4, 6, 8, 11 であり、5番目の数は 11 です。 入力 : n = 12 出力 : 24 解決策へのアプローチ ここからは、この問題を解くための2つの異なる手法について詳しく見ていきます。 単純なアプローチ（ナイーブ法） n番目

問題の概要木構造が与えられたとき、ルートからリーフまでのパスの長さが指定された値 k 未満であるようなパスのリーフノードをすべて削除する必要があります。次の例で具体的に確認してみましょう。入力 −K = 4出力 −解説各パスは以下のとおりです。 1. A → B → C → E（長さ = 4） 2. A → B → C → F（長さ = 4） 3. A → B → D（長さ = 3） 4. A → G → H（長さ = 3） 5. A → B → I（長さ = 3） ご覧のとおり、パス 3・4・5 の長さは 3 であり、これは与えられた k（= 4）より短いため、これらのパスのリーフノード（D

問題の概要本記事では、与えられた2進数から1ビットを削除し、残りのビットで表される数が他のすべての選択肢の中で最大になるようにする問題を解説します。入力 : N = 1011 出力: 111 説明: 1ビットを削除する必要があります。「0」のビットを削除すると、いずれかの「1」のビットを削除した場合よりも大きな数になります。111 > 101, 011 入力: 111 出力: 11 説明: すべてのビットが「1」なので、どのビットを削除しても結果は同じになります。解決アプローチ全探索（ブルートフォース）法最も単純な方法は、各ビットを1つずつ削除してみて、それぞれの結果を比較し、最大の結

文字列から「:」「?」「\」「/」「<」「>」「|」「*」といった禁止文字（ファイル名などに使用できない記号）を取り除く関数の作り方について解説します。例えば、次のようなケースが考えられます。 入力: str = Hello: Welco*me/ to Tu>torials point|. 出力: Hello Welcome to Tutorials point. 説明: 入力文字列に含まれていた禁止文字がすべて削除され、新しい文字列には禁止文字が残っていません。 入力: str = How/ are y*ou doing? 出力: How are you doing 解決

問題の概要 この問題では、指定された範囲LからRの間にあるすべてのビットがセット（1）になっている数の値を求めます。具体的な例を見てみましょう。 入力: L = 1, R = 5 出力: 62 説明: LとRを2進数で表すと 0..0111110 となります 入力: L = 1, R = 4 出力: 30 説明: LとRを2進数で表すと 0..11110 となります 解法へのアプローチ この問題に対して、シンプルな全探索（ブルートフォース）と、ビット演算を活用した効率的なアプローチの2つの方法を紹介します。 方法1: 全探索（ブルートフォース） このアプローチでは、指定された範囲を順番に走査

本記事では、点の集合を最も適切な直線で表現する方法について解説します。点の集合の座標 (x, y) が与えられたとき、最良の直線 y = mx + c を求めることがゴールです。つまり、傾き m と切片 c の値を見つけるだけです。まずは例を見てみましょう。入力: no_of_points = 4 x1 = 2, y1 = 3, x2 = 5, y2 = 6, x3 = 1, y3 = 3, x4 = 4, y4 = 5 出力: m = 0.8, c = 1.85 説明: 求めた m と c の値を任意の点 (xi, yi) に対する方程式 y = mx + c に代入すると、すべての点をで

本記事では、1からn（入力値）までの数のうち、2から10までのどの数でも割り切れない数を求める問題について解説します。まずは具体例でイメージをつかみましょう。入力 : num = 14 出力 : 3 説明 : 割り切れない数は 1、11、13 の3つです。 入力 : num = 21 出力 : 5 説明 : 割り切れない数は 1、11、13、17、19 の5つです。解決策へのアプローチ単純な方法最も素直な方法は、1からnumまでの各数値について、2から10までのいずれかの数で割り切れるかを順番にチェックしていくことです。割り切れない場合はカウントを増やします。しかし、この方法は1つひとつの数

この記事では、「整数 N が与えられたとき、それをできるだけ多くの素数の和として表現する」という問題を扱います。まずは具体的な例を見てみましょう。入力: N = 7出力: 2 2 3説明: 7は「2 + 2 + 3」と表せます。これが最大個数の素数による表現です。入力: N = 17出力: 2 2 2 2 2 2 2 3解法のアプローチ数を素数の和で表す方法として、N からある素数を引き、その差が素数になっているかを確認するアプローチが考えられます。差が素数であれば、N は2つの素数の和として表せることになります。しかし今回は「最大個数」の素数で表現する必要があるため、最も小さい素数である2と

疑似2進数とは疑似2進数(pseudo-binary number)とは、0と1という2進数の数字のみで構成される数値のことです。例として、00、11、10、100、111、1011などが挙げられます。このチュートリアルでは、ある数値Nをできるだけ少ない個数の疑似2進数の合計として表現する方法を解説します。以下に、数値を疑似2進数の合計として表した具体例を示します。入力 : 23 出力 : 11 + 11 + 1 説明 : 23 = 11 + 11 + 1、つまり疑似2進数(11、11、1)の合計は23になります。 入力 : 50 出力 : 10 + 10 + 10 + 10 + 10解法の

問題概要本記事では、ある数値を別の数値の累乗の組み合わせで表現できるかどうかを判定する問題について解説します。2つの整数 x と y が与えられ、x の各累乗はそれぞれ一度しか使用できないという条件のもとで、y を x の累乗の和と差で表せるかを判定します。入力: x = 4, y = 11 出力: true 説明: 4^2 − 4^1 − 4^0 = 11 となるため、y は x の累乗で表現できます。 入力: x = 2, y = 19 出力: true 説明: 2^4 + 2^1 + 2^0 = 19 となるため、y は x の累乗で表現できます。 入力: x = 3, y = 14

本記事では、与えられた行列（2次元配列）の中から、指定された合計値（SUM）と等しくなる要素のペアを検索するプログラムについて解説します。まずは具体的な例を見てみましょう。入力 : matrix[n][m] = { { 4, 6, 4, 65 }, { 56, 1, 12, 32 }, { 4, 5, 6, 44 }, { 13, 9, 11, 25 } }, SUM = 20 出力 : ペアが存在します。 説明 : 行列内に存在する 9 と 11 の合計が 20 となり、条件を満たすためです。 入力 : matrix[n][m] = { {

この記事では、与えられた行列（2次元配列）の中から、合計が最大となる2つの要素のペアを見つける方法について詳しく解説します。入力 : matrix[m][n] = { { 3, 5, 2 }, { 2, 6, 47 }, { 1, 64, 66 } } 出力 : 130 説明 : 要素64と66のペアによる最大合計は130です。 入力 : matrix[m][n] = { { 55, 22, 46 }, { 6, 2, 1 }, { 3, 24, 52 } } 出力 : 107 説明 : 要素55と52のペアによる最大合計は107です。解決

この記事では、重複のない要素を含む配列から、絶対値が同じである正の値と負の値のペアを見つけ、ソートされた順序で出力する方法を解説します。入力 : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88} 出力 : -1 1 -12 12 -56 56 入力 : arr[] = {30, 40, 50, 77, -51, -50, -40} 出力 : -40 40 -50 50解決アプローチの概要まず思い浮かぶのが総当たり（ブルートフォース）法ですが、これに加えて、計算量を大幅に削減できる効率的な手法（ハッシュマップを利用した方法）もあります。ここでは両方

本記事では、除算アルゴリズムを用いて符号なし整数の割り算を行う方法について解説します。除算アルゴリズムには、紙の上で手計算として行われるものと、デジタル回路に実装されるものがあります。除算アルゴリズムは大きく「低速除算アルゴリズム」と「高速除算アルゴリズム」の2種類に分類され、低速除算アルゴリズムにはリストアリング法、非実行リストアリング法、SRT法、非リストアリング法などが含まれます。 このチュートリアルでは、0 < 除数 < 被除数 を前提として、リストアリング（Restoring）除算アルゴリズムについて詳しく見ていきます。 解法のアプローチ ここでは、商を格納するレジスタQ

拡張行列（エクスパンディングマトリックス）とは、サイズが一定の倍率で増加し続ける行列のことです。本記事では、この拡張行列を題材とした問題について解説します。 ここでは、サイズが2倍ずつ拡大していく文字行列を扱います。元の行列のサイズがN×Nである場合、拡張後の行列は2N×2Nになります。座標(i, j)に存在する文字列が与えられたとき、その左隣、すなわち(i, (j - N - 1)%N)に存在する文字列を返すことが求められます。 拡張行列の仕組み まず、初期段階の拡張行列を視覚化して理解を深めましょう。 元の行列 -> [ a, b ] [ c, d ]、2×2行列 { a, b, c

問題の概要 二分探索木（BST）が与えられ、特定のキーからルートに至るパス上のノードの値を反転することが求められます。 たとえば次のようなイメージです。 解決のためのアプローチ このアプローチでは、まず空のキューを用意してルートから探索を開始します。木を辿りながら経路上のノードの値を順番にキューへプッシュしていき、目的のキーを持つノードが見つかったら、再帰の帰り道でキューの先頭から順に値を書き戻します。こうすることで、パス上のノードの値がきれいに反転されます。 C++での実装例 #include <bits/stdc++.h> using namespace std; stru

この記事では、行数と列数の値が与えられたとき、1行目・1列目・最終行・最終列に「1」を、それ以外の要素には「0」を出力するボックス状のパターンを作成する方法を解説します。出力イメージ入力：rows = 5, columns = 4出力： 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1入力：rows = 8, columns = 9出力： 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0