C++

数字 1 は正極（N極）を、0 は負極（S極）を表します。各磁石は 10 または 01 のように2つの極を持っています。互いに引き合う磁石同士でグループが形成され、異なる極が向かい合っている磁石は同じグループに属します。ここでは、N個の磁石が与えられます。あなたの課題は、これらの磁石から何個のグループが形成されるかを求めることです。隣り合う2つの磁石が異なる場合、その場所で新しいグループが始まります。このとき、グループのカウントを1つ増やしていきます。具体例を見てみましょう。入力magnets = [10, 01, 01, 01, 10, 01]出力4隣り合う磁石が異なるたびに新しいグループが

問題概要 数値の配列が与えられたとき、要素の合計が3で割り切れるような「サイズ2」および「サイズ3」のグループがいくつあるかを求める問題です。すべての2つの要素の組み合わせ、および3つの要素の組み合わせについて合計を計算し、それが3で割り切れるかどうかを順番に確認していきます。 具体的な例を見てみましょう。 入力 arr = [1, 2, 3, 4] 出力 4 この例では、合計が3で割り切れる組み合わせが4つ存在します。該当する組み合わせは以下の通りです。 [1, 2] [2, 4] [1, 2, 3] [2, 3, 4] アルゴリズム 配列を初期化します。 二重ループを用いて、サイズ2の

問題概要 配列とインデックスの範囲が与えられたとき、その範囲内に含まれる「隣り合っていて値が等しい要素のペア」の総数を求める問題です。一見シンプルですが、配列操作の基礎を確認するのに最適な題材です。 まずは具体例で動きを確認してみましょう。 入力例 arr = [1, 2, 2, 2, 3, 3, 4]lower = 1upper = 5 出力例 3 この例では、インデックス1〜5の範囲にある隣接ペア (2, 2)、(2, 2)、(3, 3) の3組が等しいため、答えは 3 になります。 アルゴリズム 解き方は非常にシンプルで、範囲内を一度走査しながら隣接要素を比較していくだけです。 配列

整数 n が与えられたとき、1 から n までの整数の中に、2進表現した際のセットビット（1になっているビット）の数が奇数となるものがいくつあるかを求める問題を解説します。具体例入力n = 10出力5この場合、1 から 10 までの整数のうち、2進表現でのセットビット数が奇数になるものは 5 個あります。アルゴリズム整数 N を初期化します。2進表現におけるセットビットの数を数える関数を作成します。カウント用の変数を 0 で初期化します。1 から N まで繰り返すループを記述します。各整数についてセットビットの数を数えます。セットビットの数が奇数であれば、カウントを 1 増やします。最後にカウ

はじめに このチュートリアルでは、与えられた2つの点の間に存在する整数座標の点(格子点)の数を求めるプログラムをC++で作成します。 2点を結ぶ線分上の格子点の数は、次の式で求めることができます。 gcd(abs(x1 - x2), abs(y1 - y2)) - 1 ただし、線分が座標軸に平行な場合は特別な扱いが必要です。 x軸に平行な場合(両点のy座標が等しい): 格子点の数は abs(x1 - x2) - 1 y軸に平行な場合(両点のx座標が等しい): 格子点の数は abs(y1 - y2) - 1 つまり、両方の点のy座標が一致していれば線分はx軸に平行となり、x座標が一致していれ

この記事では、方程式 x₁ + x₂ + … + xₙ = k を満たす整数解の個数を求める問題を取り上げます。組み合わせの公式を活用することで、すべての解を列挙することなく効率的に計算できます。 解の個数を求める公式 方程式の整数解は、次の2種類に分けて数えることができます。 非負整数解（0 以上の整数）の個数：C(n + k − 1, k) 正の整数解（1 以上の整数）の個数：C(k − 1, n − 1) 非負整数解の個数は「重複組合せ」（仕切りと玉の並べ方）の考え方から導かれます。また、正の整数解の個数は、各変数にあらかじめ 1 を割り当て、残りの k − n を自由に分配する

文字列が与えられたとき、各文字について「その文字より右側に存在する、より大きい要素（文字）」の数を数える問題を考えてみましょう。まずは具体例を見てみます。入力string = abc出力2 1 0この結果は次のように解釈できます。a の右側には a より大きい文字が 2 つあります。b の右側には b より大きい文字が 1 つあります。c の右側には c より大きい文字は 0 個です。アルゴリズム文字列を初期化します。各文字のカウントを記録するための配列を用意します。二重ループを使って文字列を走査します。一度に 1 文字ずつ取り出し、それ以降のすべての文字と比較します。現在の文字が比較対象の文

概要数値が与えられたとき、その2進表現における「先行ゼロ」(最上位の1より手前に並んでいる0)の個数を求めます。ここでは、全体のビット幅を32ビット(unsigned int)と仮定します。例入力:5出力:295の2進表現は 00000...00101 です。有効なビットは下位3桁のみなので、先行ゼロの個数は 32 − 3 = 29 個となります。アルゴリズム数値 n を初期化します。n の2進表現を求めます。合計ビット数(32)から2進表現の桁数を引きます。結果を返します。C++での実装以下は、上記アルゴリズムをC++で実装した例です。#include <bits/stdc++.h&g

このチュートリアルでは、n分木（n-ary tree）の各ノードについて、そのサブツリーに含まれる葉ノード（リーフノード）の数を求めるプログラムを作成します。葉ノードとは、子を一切持たないノードのことです。n分木が与えられたとき、すべてのノードを根とみなしたサブツリーそれぞれに対して、含まれる葉ノードの数を計算します。まずは具体例を見てみましょう。入力N = 8 tree = [[2, 3], [], [4, 5, 6], [7, 8], [], [], [], []]出力1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->

整数 N が与えられたとき、順列（permutation）を最悪ケースで完全に推測し切るまでに必要な移動回数を求める問題を考えます。この移動回数は単純な階乗ではなく、「1 から N までの各 i に対して i × (N − i) を計算して合計し、最後に N を加える」ことで求められます。 具体例 入力 9 出力 129 N = 9 の場合、i = 1 のときは 1 × 8 = 8、i = 2 のときは 2 × 7 = 14、i = 3 のときは 3 × 6 = 18 … というように計算を進めていきます。これらをすべて合計すると 120 になり、さらに N の値である 9 を加えると、答え

ステッピング数（Stepping Number）とは、隣り合う桁同士の差がすべて1となっている数のことです。この記事では、桁数を表す整数 n が与えられたとき、n 桁のステッピング数が全部で何個あるかを数える方法を解説します。 具体例 まずは例を見てみましょう。 入力 2 出力 17 2桁の数のうち最小は10、最大は99です。この範囲には 10, 12, 21, 23, …, 89, 98 のように、合計17個のステッピング数が存在します。 アルゴリズム ここでは、n桁のすべての数を順番に調べるシンプルな全探索アプローチを紹介します。手順は以下の通りです。 桁数 n を初期化します。 カウ

配列とターゲット要素のインデックスが与えられたとき、その要素より右側に存在する、指定された要素よりも大きい値を持つ要素の個数を数える問題を考えてみましょう。まずは具体例から見ていきます。問題の例入力：arr = [2, 3, 5, 1, 4, 2, 6] index = 3出力：3この例では、ターゲットとなるインデックス 3 の要素は 1 です。その右側には 4、2、6 の 3 つの要素が存在し、これらはすべて 1 より大きいため、答えは 3 となります。アルゴリズム配列とターゲット要素のインデックスを初期化します。インデックスが配列の長さ以上の場合は、無効な入力として -1 を返します。指定

n分木（n-aryツリー）と1つの数値が与えられたとき、その数値より大きい値を持つノードの個数を数える問題を考えてみましょう。まずは具体例から見ていきます。入力例tree = [[4], [1, 2], [3, 5]] n = 2出力例3この例では、n（= 2）より大きい値を持つノードが3つ存在するため、答えは3となります。アルゴリズムn分木を初期化します。カウント用の変数を0で初期化します。現在のノードの値がnより大きい場合は、カウントを1増やします。現在のノードの子ノードをすべて取得します。各子ノードに対して同じ関数を再帰的に呼び出し、条件を満たすノードを数えます。最終的なカウントを返しま

このチュートリアルでは、和の方程式の非負整数解の個数を求めるプログラムをC++で作成します。扱う方程式は x + y + z = n です。数値 n が与えられたとき、この方程式を満たす非負整数解(x, y, z がすべて 0 以上の整数)がいくつ存在するかを求めます。まずは具体例を見てみましょう。入力2出力6この場合の解は以下の6通りです。0 0 2 0 1 1 0 2 0 1 0 1 1 1 0 2 0 0アルゴリズム数値 n を初期化します。解の個数を数える変数 count を 0 に初期化します。3つの数値のすべての組み合わせを調べるため、三重のネストしたループを記述します。現在の組み

問題の概要本記事では、直線の方程式 y = mx + c を満たす順序付き点ペアの数を求める問題を解説します。配列と、傾き m、切片 c が与えられたとき、配列の要素から選んだ順序付きペア（i, j）のうち、arr[j] = m × arr[i] + c を満たすものの個数を数えます。まずは具体例を見てみましょう。入力例arr = [1, 2, 3] m = 1 c = 1出力例2この例では、直線 y = x + 1 上に乗る点のペアとして (1, 2) と (2, 3) の2組が該当します。アルゴリズム考え方はシンプルで、取り得るすべてのペアを総当たり（ブルートフォース）で調べる方法です。手

NとKという2つの整数が与えられたとき、最初のN個の自然数の中から選んだペアのうち、その合計がKで割り切れるものの個数を求めます。まずは具体例を見てみましょう。入力例N = 3 K = 2出力例1この場合、合計がK（=2）で割り切れるペアは1つだけです。該当するペアは (1, 3) です。アルゴリズムこの問題は、以下の手順で解くことができます。NとKを初期化します。1からNまでの自然数を生成し、配列に格納します。カウント用の変数を0で初期化します。二重ループを使って、配列内のすべてのペアを列挙します。各ペアの合計値を計算します。合計値がKで割り切れる場合は、カウントを1増やします。最後にカウン

配列が与えられたとき、要素の合計が2の累乗（1, 2, 4, 8, 16, ...）になるペアの個数を求める問題を解説します。まずは具体例を見てみましょう。例入力arr = [1, 2, 3]出力1この配列では、合計が2の累乗になるペアは1つだけです。該当するのは (1, 3) のペアで、合計が4になります。アルゴリズム解法の流れは以下のとおりです。配列をランダムな数値で初期化します。カウント用の変数を0で初期化します。二重ループを使って、配列内のすべてのペアを列挙します。各ペアの合計値を計算します。ビットAND演算（&）を使って、合計が2の累乗かどうかを判定します。合計が2の累乗であ

配列が与えられたとき、ビット単位OR（Bitwise OR）の結果が奇数になるペアの個数を求める問題を解説します。まずは具体例を見てみましょう。入力：arr = [1, 2]出力：1この配列では、ビット単位ORが奇数になるペアは1つだけで、そのペアは (1, 2) です。実際に「1 | 2」を計算すると 3 となり、奇数であることが確認できます。ポイント：ORが奇数になる条件ビット単位ORの結果が奇数になるのは、「少なくとも一方の値が奇数である場合」です。これは、奇数の最下位ビット（LSB）が 1 であり、OR演算ではどちらか一方でも 1 なら結果も 1 になるためです。この性質を理解しておく

問題の概要 配列が与えられたとき、「合計が最大となるペア」がいくつ存在するかを求める問題です。まずは具体例で確認しましょう。 入力 arr = [3, 4, 5, 2, 1, 2, 3, 4, 1, 5] 出力 1 この配列でペアの合計が最大になるのは 5 + 5 = 10 です。合計が 10 になるペアは (5, 5) の 1 組のみのため、答えは 1 となります。 アルゴリズム 考え方はシンプルで、以下の手順に従います。 配列を用意します。 最大合計(maxSum)を INT_MIN で初期化します。 二重ループですべてのペアを調べ、ペアの合計の最大値を求めます。 ペアの個数を数えるため

C++を使ったことがある人なら、「回文（パリンドローム）」という言葉を耳にしたことがあるでしょう。この記事では、「N番目の偶数長回文数」について、具体例を交えながらすべて解説します。 回文とは、逆から読んでも元と同じになる数字や単語のことです。数字だけでなく、文字を反転してもつづりが変わらない単語も回文と呼ばれます。例えば以下の通りです。 数字 = {1, 121, 131, 656, 1221, 1551} 単語 = {saas, malayalam, level, mom} 一見複雑に見えますが、実際にプログラムで実装すると非常にシンプルです。それでは、回文について詳しく見ていきましょう。