C++

本記事では、整数の配列が与えられたときに、その配列に含まれる素数の個数をC++で求める方法を解説します。素数とは、1とその数自身でのみ割り切れる数のことです。つまり、約数がちょうど2つしかない数を指します。配列の先頭要素から末尾要素まで順番に素数かどうかを判定し、素数が見つかるたびにカウントを増やしていきます。ある数Nが素数かどうかを判定するには、2からN/2までの範囲にある数でNが割り切れるかどうかを確認します。1つでも割り切れる数が存在すればNは素数ではなく、どこでも割り切れなければNは素数です。具体例で理解しましょう。入力 − arr[]= { 1,2,3,4,5,6,7,8,9 }出力

サイズNの整数型配列が与えられます。変数LとRは、1以上N以下の範囲(L ≥ 1、R ≤ N)を定義します。この記事の目的は、範囲[L, R]内に存在する要素のうち、その範囲での最小値と同じ値を持つ要素がいくつあるかを求めることです。 解決のアプローチ まず、範囲L〜R内の要素を走査して最小値を求めます。 次に、同じ範囲を再度走査し、手順1で求めた最小値と等しい要素が見つかるたびにカウントを1ずつ増やします。 具体例で確認してみましょう。 例1 入力: arr[] = { 1,2,3,0,3,2,0,1 }、N=8、L=2、R=5 出力: 範囲内の最小値の出現回数 − 1 説明: 範囲L(

縦の長さL、横の幅B(L≥B)の長方形が与えられたとします。この記事では、L×Bの長方形の中にいくつの正方形が含まれているかを効率的に求める方法を解説します。 上の図は3×2の長方形の例です。この長方形には、2×2の正方形が2個、1×1の正方形が6個含まれています。 合計:6+2=8個 規則性を見つける まず、正方形だけで構成されたB×Bの図形について考えてみましょう。 サイズL×Bの長方形には、必ずL×B個の1×1の正方形が含まれます。 含まれる最大の正方形のサイズはB×Bです。 L=B=1の場合:正方形の数=1 L=B=2の場合:正方形の数=1+4=5(2×2が1個、1×1が4個) L

三角形の周囲長 P が与えられたとき、同じ周囲長を持つ直角三角形が何通り作れるかを求めるのが本記事の目的です。なお、周囲長とは三角形の3辺の長さをすべて足し合わせた合計値のことです。 三角形の辺を a、b、c とすると、求めたい直角三角形は次の2つの条件を満たす必要があります。 周囲長の条件: a + b + c = P ピタゴラスの定理: a2 + b2 = c2(a、b、c のいずれの組み合わせに対しても成立) 探索は、a を 1 から p/2 まで、b を a+1 から p/3 まで変化させながら行い、c = p − a − b(a + b + c = p から導かれます)として求め

問題の概要 整数 n と p が与えられたとき、合同式 x2 ≡ 1 (mod p) を満たす x のうち、x が範囲 [1, N] に含まれるものがいくつあるかを求めるのがこの記事の目的です。 最も基本的なアプローチは、1 から N までの各整数を順番に x として調べ、「(x × x) % p == 1」が成立するかどうかを判定し、条件を満たすたびにカウントを 1 増やしていくというものです。 それでは、具体的な例を使って理解していきましょう。 入力例 1 入力：n = 5、p = 2 出力：解の個数 = 3 説明：範囲 1〜5 の間で各値を確認します。 12 = 1 % 2 =

整数 N が与えられます。この記事の目的は、以下のルールに従って数値を 1 に減らすために必要なステップ数をカウントすることです。数値が 2 のべき乗である場合、その半分の値に減らします。それ以外の場合は、N から「N 未満で最も近い 2 のべき乗」を引いた値に減らします。アルゴリズムの考え方ステップ 1: まず、ceil(log2(N)) と floor(log2(N)) が同じ結果を返すかどうかを確認することで、N が 2 のべき乗かどうかを判定します。真であれば N = N / 2 とし、操作回数を 1 増やします。ステップ 2: ステップ 1 の判定が偽であった場合、N から「N 未満

問題概要整数 n が与えられます。この課題の目的は、以下の2つの条件を満たすトリプレット（3つの数の組み合わせ）を見つけ出し、その個数を求めることです。a2 + b2 = c21 ≦ a ≦ b ≦ c ≦ nこの問題は、1 ≦ a ≦ n および 1 ≦ b ≦ n の範囲で二重ループを実行することで解くことができます。各ループ内で c を計算し（c = sqrt(a² + b²)）、両方の条件を満たす場合にカウントを増やしていきます。具体例を使って理解しましょう。入力 ： N = 5出力 ： トリプレットの個数 ： 1説明 ：a=3、b=4、c=5 のとき、両方の条件が満たされます。入力

問題の概要整数型の配列 Arr[] と、範囲を定義する2つの変数 a・b が与えられます。この記事の目的は、3つの要素の合計が範囲 [a, b] の間に収まるトリプレット（3要素の組み合わせ）の個数を求めることです。解法には3重の for ループを使用します。arr[i] + arr[j] + arr[k] が a 以上かつ b 以下を満たすたびにカウントを1増やします。添字の範囲は 0 <= i <= n-2、i < j < n-1、j < k < n です。ここで n は配列 Arr[] の要素数を表します。具体例で確認してみましょう。入力例1入力 −

整数型の配列 Arr[] が与えられます。この記事の目的は、3つの要素の積が指定された数 p に等しいトリプレット（3つ組）の個数を数えることです。値が同一のトリプレットでも、使用する要素が異なれば別々にカウントします。例えば、配列 [1,2,3,1,2] における (1,2,3) と (3,1,2) は値の並びこそ同じですが、参照している要素が異なるため、別個のトリプレットとして扱います。具体的な例で確認しましょう。入出力例例1入力 − arr[]= { 1,2,3,2,4,1,5 }, p=4出力 − トリプレットの個数: 3説明 −Triplet 1 [ 1,2,3,2,4,1,5 ]

N個の要素からなる配列が与えられたとき、「同じ値を持ち、かつインデックスが異なる」ペア (i, j) の数を求めるのが本記事の目的です。つまり、Arr[i] == Arr[j] かつ i ≠ j を満たす組み合わせを数えます。これは現実の問題にも応用できます。たとえば、N個の手袋の中から同じサイズの手袋同士でペアを作る場面を考えてみましょう。売れるのはペアになった手袋だけであり、片方だけでは価値がありません。そこで、一致する要素を見つけてはペアとして取り除いていく処理が必要になります。基本的な考え方二重ループを用いて、外側のループを 0 ≤ i < n−1、内側のループを i <

問題概要 コーディングコンテストにN人の参加者がいるとします。ここで、1人の参加者が最大1人の相手としかペアを組めないという条件のもとで、考えられるペアの作り方(ペアリング)の総数を求めるのが目的です。 つまり、1つのペアは最大2人で構成され、参加者は誰ともペアを組まずに単独で参加することも許容されます。 漸化式によるアプローチ この問題は、次のような漸化式(再帰関係)で解くことができます。 n = 0 または n = 1 のとき:残っている人がいない、または1人だけのため、count = 1(全員が単独という1通りのみ) n ≥ 2 のとき:ある1人に注目すると、その人は「単独で残る」か

範囲 [l, r] と整数 k が与えられます。求めたいのは、l 以上 r 以下の数のうち、「その数の逆順 − その数」の絶対値が k の倍数になっているものの個数です。この条件は、l から r まで順番に各数の逆順を計算し、元の数との差の絶対値が k で割り切れるかどうか(差 % k == 0)を確認することで判定できます。条件を満たしたらカウントを1つ増やします。具体例で見てみましょう。入力 − L=21, R=25, K=6出力 − 条件を満たす数の個数 − 2説明 −各数とその逆順、そして差は以下の通りです。 21 → 12, |21−12|=9, 9%6≠0 22 → 22, |22

整数型の配列 Arr[] が与えられたとします。この記事のゴールは、考えられるすべてのトリプレット（三つ組）の中で「積」が最小になる組み合わせの個数を数えることです。具体的には、i < j < k を満たし、arr[i] * arr[j] * arr[k] が最小値となるトリプレットを対象にします。解決の手順としては、まず i < j < k の条件下で実現可能な最小の積を求め、それを minprod として記録します。その後、積が minprod と一致するトリプレットをすべて数え上げます。具体例で理解しよう入力 − arr[] = { 1, 2, 3, 2, 4,

N個の要素からなる配列が与えられたとき、i ≠ j を満たすペア (Arr[i], Arr[j]) のうち、Arr[i] + Arr[j] の和が完全平方数（perfect square）となるものの個数を求めるのが本記事の目的です。 この問題は、各ペアの和を計算し、その平方根が整数（床関数の値）と一致するかどうかを判定することで解けます。具体的には、sqrt(Arr[i]+Arr[j]) − floor(sqrt(Arr[i]+Arr[j])) == 0 が成り立てば、その和は完全平方数であると分かります。 具体例で確認してみましょう。 例1 入力：Arr[] = { 4, 3, 2, 1,

問題の概要N個の要素からなる配列が与えられたとき、積が2の累乗（1, 2, 4, 8, 16, …）になるようなすべてのペア（Arr[i], Arr[j]）の個数を求めます。ここで i ≠ j とします。つまり、Arr[i] × Arr[j] が2の累乗となるインデックスの組み合わせをカウントするのが目的です。判定には対数を利用します。ある正の整数 prod が2の累乗であるかどうかは、log2(prod) が整数かどうかで確認できます。具体的には、ceil(log2(prod)) と floor(log2(prod)) が等しければ、prod は2の累乗であると判断できます。入出力例入力：

N個の要素からなる配列 arr[] が与えられたとき、指定された条件を満たすすべての有効なペア (Arr[i], Arr[j]) の個数を求めることがゴールです。 有効なペアの条件 Arr[i] == Arr[j](2つの要素の値が等しい) Arr[i] + Arr[j] の和が偶数である i + j < 120 を満たす さらに i != j(同一インデックス同士の組み合わせは不可) 注意: (Arr[i], Arr[j]) と (Arr[j], Arr[i]) は同じペアとして1回だけカウントします。 それでは、具体例を使って理解を深めましょう。 入力例1 Arr[]= { 3,

問題の概要 数値の配列 Arr[] が与えられます。目的は、考えられるすべてのペアの中で「最大の差」と等しい差を持つペアが何通りあるかを数えることです。条件は i != j であり、arr[x] − arr[y] が取り得る最大値になるような組み合わせを探します。 解き方はシンプルです。まず最大差(maxdiff)を求め、その後で差が maxdiff と一致するすべてのペアをカウントします。 入出力例1 入力: arr[] = { 1, 2, 3, 2, 4, 1, 5 } 出力: 最大差を持つペアの選び方の数 ― 2 説明: 配列の最小値は1、最大値は5なので、最大差 = 5 − 1 = 4

3つの整数型配列 A[]、B[]、C[] が与えられます。この記事の目的は、A[i] < B[j] < C[k] という条件を満たす要素の組み合わせ（トリプレット）が全部でいくつ存在するかを求めることです。3つの配列はいずれも同じ要素数 N を持ちます。最も基本的な解法は、各配列を順番に走査しながら「A[i] < B[j] かつ B[j] < C[k]」という条件を判定し、条件を満たすたびにカウントを1ずつ増やしていくというものです。具体例を使って理解していきましょう。入力例と出力例入力：A[]={1,4,5}　B={0,2,3}　C={0,6,7}出力： トリプレット

4つの整数 L、R、A、B が与えられます。この問題の目的は、範囲 [L, R] 内に存在する、A または B（あるいはその両方）で割り切れる数の個数を求めることです。解き方はシンプルで、L から R まで順番に走査し、各数値について「number % A == 0」または「number % B == 0」が成り立てばカウントを1つ増やしていきます。具体例を使って理解を深めましょう。入力 − L=10, R=15, A=4, B=3出力 − A または B で割り切れる数の個数 − 2説明 −数値 12 は 3 と 4 の両方で割り切れます。 数値 15 は 3 でのみ割り切れます。 合計個数

問題の概要 ソートされていない、重複のない要素からなる整数配列が与えられます。この課題のゴールは、配列をソートしたときに発生するクロスライン（交差線）の総数を求めることです。 クロスラインとは、配列の各要素を縦線として表現したとき、ソートの過程で線と線が交差する回数のことです。言い換えると、これは配列内の転倒（インバージョン）、すなわち「手前の要素が後ろの要素より大きい」というペアの個数を数える問題と同じものです。 Arr[] = { 1,2,4,3,5 } の場合：下図のように3本のクロスラインが存在します。 Arr[] = { 1,2,3,4,5 } の場合：すでにソート済みのため、クロ