C++

この記事では、C++を使って集合上に定義できる反射関係（reflexive relation）の総数を求める方法について解説します。問題設定としては、整数 n が与えられたとき、n 個の自然数からなる集合上に存在する反射関係の個数を求めるというものです。 反射関係とは 集合 A 上の関係 R が反射的であるとは、「A に属するすべての要素 a に対して、順序対 (a, a) が必ず R に含まれる」という条件を満たすことを意味します。数式で表すと次のようになります。 (a, a) ∈ R （∀ a ∈ A） 具体的な入出力の例を見てみましょう。 入力 : x = 1 出力 : 1 説明 : 集

この記事では、与えられた数列の中から、すべての要素が指定した値Xより大きいセグメント（部分配列）の個数を求める方法を解説します。重なり合うセグメントは1回だけカウントし、隣接する2つの要素やセグメントは別々に数えないものとします。まずは、この問題の基本的な例を見てみましょう。入力 : arr[ ] = { 9, 6, 7, 11, 5, 7, 8, 10, 3}, X = 7 出力 : 3 説明 : { 9 }, { 11 }, { 8, 10 } が X=7 より大きい要素だけを持つセグメントです 入力 : arr[ ] = { 9, 6, 12, 2, 11, 14, 8, 14 },

この記事では、方程式を満たす6つ組（セクステュプレット）の個数を求めるアルゴリズムについて解説します。例として、次の方程式を満たす a、b、c、d、e、f の組み合わせがいくつ存在するかを求める問題を取り上げます。( a + b + c ) * e / d = fまず、この式を次のように変形してみましょう。( a + b + c ) = ( f * d ) / e入力例と出力例入力 : arr [ ] = { 1, 3 } 出力 : 4 説明 : 　・( a, b, c, e, f ) = 1、d = 3 　・( a, b, c, d, e ) = 1、f = 3 　・( a, b, c )

この記事では、N分木(N-ary tree)において、指定されたノードの兄弟ノードの数を求める方法について詳しく解説します。ユーザーから与えられたキーの値を持つノードの兄弟を探し、該当するノードが存在しない場合は -1 を出力します。利用できるアプローチは以下の一つです。シンプルなアプローチこのアプローチでは、すべてのノードを順番に走査し、その子ノードの中にユーザーが指定した値と同じ値を持つものが存在するかどうかを確認します。存在する場合は、「その親が持つ子ノードの総数 − 1(指定されたノード自身)」を答えとして返します。コード例 #include <bits/stdc++.h>

本記事では、グラフに含まれるシンクノード（沈み込みノード）の数を求める問題について、その考え方と具体的な解法を詳しく解説します。まず問題設定を確認しましょう。N個のノード（1からNまで）とM個のエッジを持つ有向非巡回グラフ（DAG: Directed Acyclic Graph）が与えられます。このとき、グラフ内に存在するシンクノードの総数を求めることが目標です。シンクノードとは、出ていくエッジ（出力辺）を一切持たないノードのことです。つまり、そのノードから他のノードへ向かう矢印が1本も存在しないノードを指します。入力例と出力例入力：n = 4, m = 2 Edges[] = {{2, 3

本記事では、方程式 x + y + z ≤ n を満たす解の個数を求めるアルゴリズムについて解説します。この問題では、変数 x・y・z と上限値 n からなる方程式が与えられ、その条件を満たす解が全体でいくつ存在するかを求めることが課題となります。まずは具体的な入力例と出力例を見てみましょう。入力: X = 1, Y = 1, Z = 1, n = 1 出力: 4 入力: X = 1, Y = 2, Z = 3, n = 4 出力: 3この問題は、各変数を式から分離しながら (x, y)、(y, z)、(x, z) のすべての値の組み合わせを走査し、それぞれが方程式を満たしているかどうかを確

本記事では、方程式 n = x + n ⊕ x の解の個数を求める方法を解説します。つまり、与えられた n に対して、この等式を満たす x の値がいくつ存在するかを求める問題です。ここで「⊕」はXOR(排他的論理和)演算を表します。 それでは、具体例を挙げながら、n = x + n ⊕ x の解の個数について詳しく見ていきましょう。 全探索(ブルートフォース)による解法 最もシンプルなのが全探索(ブルートフォース)のアプローチです。与えられた n に対して、x の候補として 0 から順に整数を代入し、等式が成り立つかどうかを1つずつ確認していきます。なお、x の範囲は 0 以上 n 以下に限定

この記事では、モジュラ方程式（剰余方程式）の解とは何かを詳しく解説し、その解の個数を求めるプログラムをC++で作成します。まずは基本的な例から見ていきましょう。Input : X = 30 Y = 2 Output : 4, 7, 14, 28 Explanation : 30 mod 4 = 2 (equals Y),     30 mod 7 = 2 (equals Y),     30 mod 14 = 2 (equals Y),     30 mod 28 = 2 (

地点XとYの間にはn個の中間駅があるとします。ここで、「どの2つの停車駅も隣り合わない」という条件のもとで、s個の駅に停車する列車の配置方法が何通りあるかを求める問題を考えてみましょう。この記事では、停車駅の組み合わせ数を求めるためのアプローチを段階的に詳しく解説します。この問題は、本質的には組合せ論の問題であり、s個の停車駅の選び方の総数を求めることになります。 問題を解くアプローチ まず具体例として、中間駅が8個あり、そのうち3個の駅に停車させたい場合を考えてみます。 n = 8, s = 3 このとき、列車が停車できない駅は(n − s)、つまり5個残ることになります。 停車できない

この記事では、C++を使って「ビット単位OR(論理和)がK以上となる部分配列の個数」を求める問題の解き方を解説します。整数の配列 arr[] と整数 K が与えられたとき、ORの値が K 以上になる部分配列が全部でいくつ存在するかを数えます。 入力: arr[] = {1, 2, 3}, K = 3 出力: 4 各部分配列のビット単位OR: {1} = 1 {1, 2} = 3 {1, 2, 3} = 3 {2} = 2 {2, 3} = 3 {3} = 3 → ORが3以上となる部分配列は4個 入力: arr[] = {3, 4, 5}, K = 6 出力: 2 解法へのアプローチ ここ

本記事では、C++を用いて「合計が指定された範囲に収まる部分配列の個数」を求める問題を解説します。正の整数からなる配列 arr[] と範囲 {L, R} が与えられたとき、合計が L 以上 R 以下に収まる部分配列の総数を計算します。 まず、問題の具体的な例を見てみましょう。 入力 : arr[] = {1, 4, 6}, L = 3, R = 8 出力 : 3 条件を満たす部分配列は {1, 4}, {4}, {6} の3つです。 入力 : arr[] = {2, 3, 5, 8}, L = 4, R = 13 出力 : 6 条件を満たす部分配列は {2, 3}, {2, 3,

この記事では、C++を使用して「合計がK未満となる部分配列（サブ配列）の個数」を求める方法を解説します。問題設定としては、配列 arr[] と整数 K が与えられ、その中から要素の合計が K より小さくなる部分配列をすべて見つけ出します。以下に具体例を示します。 入力 : arr[] = {1, 11, 2, 3, 15} K = 10 出力 : 4 該当する部分配列 : {1}, {2}, {3}, {2, 3} 解決のためのアプローチ ここでは、この問題を解くための2つの異なる手法を紹介します。 方法1：総当たり法（Brute Force） このアプローチでは、考えられるすべての部分配列

はじめに この記事では、C++を使って「合計がk^m（m ≥ 0）の形式となる部分配列の個数」を求める方法について詳しく解説します。配列arr[]と整数Kが与えられたとき、合計がK^m（mは0以上の整数）、すなわちKの非負のべき乗と等しくなる部分配列の数を求める必要があります。 入力: arr[] = { 2, 2, 2, 2 } K = 2 出力: 8 以下のインデックスを持つ部分配列が有効です: [1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3], [3, 4], [1, 4] 入力: arr[] = { 3, -6, -3, 12 } K

はじめに本記事では、C++を使って「最大要素と最小要素が等しい部分配列」の個数を求める問題を解説します。まずは、問題の具体例から見ていきましょう。入力 : array = { 2, 3, 6, 6, 2, 4, 4, 4 } 出力 : 12 説明 : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4}, {4,4,4} が、最大値と最小値が一致する部分配列として成立します。 入力 : array = { 3,3,1,5,1,2,2 } 出力 : 9 説明 : {3}, {3}, {1}, {5}, {1}, {2}, {2}

C++を使ったことがある方なら、「部分配列（サブアレイ）」という概念と、それがいかに便利であるかをご存じでしょう。C++では多くの数学的問題を効率的に解くことができます。本記事では、C++を用いて「奇数をちょうどm個含む部分配列」の数を求める方法について、基礎から詳しく解説します。 問題の定義 この問題では、与えられた配列と整数mに対して、「奇数をちょうどm個含む」部分配列が全部でいくつ作れるかを求めます。以下に具体的な例を示します。 入力 : array = { 6, 3, 5, 8, 9 }, m = 2 出力 : 5 説明 : 奇数をちょうど2個含む部分配列は { 3, 5 }、{ 6,

この記事では、C++を使って「合計が指定された範囲 [L, R] 内に収まる部分配列（サブ配列）の個数」を求める問題を解説します。正の整数からなる配列 arr[] と範囲 {L, R} が与えられ、その合計が L 以上 R 以下となる部分配列の総数を計算するのが目標です。まず、問題の具体例を見てみましょう。入力 : arr[] = {1, 4, 6}, L = 3, R = 8 出力 : 3 該当する部分配列は {1, 4}, {4}, {6} の3つです。 入力 : arr[] = {2, 3, 5, 8}, L = 4, R = 13 出力 : 6 該当する部分配列は {2, 3

部分配列（サブ配列）とは、配列から連続した形で取り出される一部分のことです。例えば、配列 [5, 6, 7, 8] を考えた場合、(5)、(6)、(7)、(8)、(5, 6)、(6, 7)、(7, 8)、(5, 6, 7)、(6, 7, 8)、(5, 6, 7, 8) のように、10個の空でない部分配列が存在します。 本記事では、C++で「各要素の合計が奇数となる部分配列」の個数を求める方法について詳しく解説します。奇数和を持つ部分配列の個数を求めるには複数のアプローチがありますので、まずは具体的な例から確認していきましょう。 入力 : array = {9,8,7,6,5} 出力 : 9

この記事では、各箱のサイズが格納された配列が与えられ、「大きい箱が小さい箱の2倍以上のサイズであれば、その小さい箱を大きい箱の中に収めることができる」という条件のもとで、最終的に外から見える箱の数を求める問題を解いていきます。問題の例入力 : arr[] = { 1, 3, 4, 5 } 出力 : 3 サイズ1の箱を、サイズ3の箱の中に入れます。 入力 : arr[] = { 4, 2, 1, 8 } 出力 : 11つ目の例では、サイズ1の箱をサイズ3の箱に収められるため、残る見える箱は3つになります。2つ目の例では、箱同士の組み合わせ次第ですべての箱を入れ子にできるため、最終的に見える箱は

問題概要 n人の人たちがいる場面を考えます。それぞれの人は「単独で行動する」か「誰かとペアを組む」かのどちらかを選べます。このとき、これらの人々をグループ分けする方法が全部で何通りあるのかを求めるのが、本記事のテーマです。 入出力の例 入力：3 出力：4 説明：[{1}, {2}, {3}]、[{1, 2}, {3}]、[{1}, {2, 3}]、[{1, 3}, {2}] 　　　この4通りが、3人を分類するすべての方法です。 入力：6 出力：76 解法のアプローチ この問題は、次の漸化式（対合数・電話番号と呼ばれる数列）を利用することで効率よく解くことができます。 A[n] =

N分木（N-aryツリー）が与えられたとき、その木を走査できる方法が全部で何通りあるかを求める問題について解説します。例として以下のような木を考えてみましょう。上記の木の場合、答えは 192 となります。この問題を解くには、組み合わせ論に関する基礎知識が必要です。すべての経路について可能な順列の組み合わせを考慮することで、答えを求めることができます。解法のアプローチこのアプローチでは、レベル順走査（幅優先探索：BFS）を行いながら、各ノードが持つ子の数を調べます。そして、その子の数の階乗を答えに掛け合わせていくだけで計算できます。あるノードに子が n 個ある場合、それらの子を訪問する順序は n