C++

この問題では、サイズ n の配列 arr が与えられます。私たちのタスクは、配列のすべての要素を等しくするために必要な操作回数を求めることです。 ここでいう「操作」とは、最大の重みを持つ要素から、配列内の他のすべての要素へ等しい重みを分配することを意味します。 すべての要素を等しくすることが不可能な場合は、-1 を出力します。 それでは、具体例を使って問題を確認してみましょう。 入力 : arr[] = {7, 3, 3, 3} 出力 : 3 解説 分配操作を行った結果、配列は {4, 4, 4, 4} となり、すべての要素が等しい値に揃います。最大値 7 を持つ要素から他の要素へ重みを分配

この問題では、2次元平面上に配置されたN個の点が与えられます。目的は、自分の「上」「下」「左」「右」のいずれかに少なくとも1つの点が存在するような点の個数を求めることです。 問題の定義 カウント対象となるのは、以下の条件のいずれかを満たす点が少なくとも1つ存在する点です。 上の点：X座標が同一で、Y座標が現在の値より1大きい点 下の点：X座標が同一で、Y座標が現在の値より1小さい点 左の点：Y座標が同一で、X座標が現在の値より1小さい点 右の点：Y座標が同一で、X座標が現在の値より1大きい点 入力例と出力例 まずは具体例で問題を確認しましょう。 Input : arr[] = {{1,

問題概要 この問題では、素数 N が与えられ、素数を法とする原始根(Primitive Root)を求めることが課題となります。 原始根とは — N より小さい数 r のうち、[0, n-2] の範囲のすべての x に対して rx (mod N) の値が互いに異なるような数のことを指します。 例を見て理解しましょう: 入力 : N = 5 出力 : 2 なお、数学的には素数 N を法とする原始根の総個数は φ(N−1)(オイラー関数の値)であることが知られています。本記事では、その中でも最小の原始根を効率よく求める手法を紹介します。 解法アプローチ 1. 素朴な解法(全探索) 最も単純な解法は

問題概要 この問題では、整数 n と素数 p が与えられ、「モジュロ p における平方根」を求めます。ここで、p は 4*i + 3 の形、すなわち p % 4 == 3 を満たす素数である必要があります（i > 1）。 この条件に当てはまる素数には、たとえば 7、11、19、23、31 などがあります。 入出力例 入力 : n = 3, p = 7 出力 : 平方根は存在しません すべての n に対して平方根が存在するとは限りません。n が「平方剰余」でない場合、答えは存在しないため、その判定も行う必要があります。 解法アプローチ①：全探索（線形探索） 最もシンプルな解法は、ループ

問題の概要 この問題では、整数 n と素数 p が与えられ、「n の mod p における平方根（モジュラ平方根）」を求めることを目標とします。 具体例を見てみましょう。 入力 : n = 4, p = 11 出力 : 9 これは、92 = 81 ≡ 4 (mod 11) が成立するためです。つまり 9 は 4 のモジュラ平方根となっています。 解法のアプローチ 本記事では Tonelli–Shanks（トネリ・シャンクス）アルゴリズムを使用します。 Tonelli–Shanksアルゴリズムとは、モジュラ演算において x2 ≡ n (mod p) という形の合同式を満たす x を求めるための

問題の概要この問題では、ソートされていない n 個の整数値からなる配列 arr[] と整数 val が与えられます。求められているのは、ソートされていない配列の中で特定の要素が出現する開始インデックスと終了インデックスを見つけることです。配列内での要素の出現状況に応じて、以下の結果を返します。要素が配列内に2回以上出現する場合 →「開始インデックスと終了インデックス」を返す要素が配列内に1回だけ出現する場合 →「単一のインデックス」を返す要素が配列内に存在しない場合 →「要素は存在しません」と返す具体例を使って問題を確認しましょう。例1入力 : arr[] = {2, 1, 5, 4, 6,

問題概要この問題では、N×Nのサイズを持つ2次元行列と、sum（合計値）およびsize（サイズ）という2つの変数が与えられます。私たちのタスクは、指定された合計値を持つ部分行列を見つけることです。具体的には、要素の合計がsumと等しくなるような、size×sizeのサイズの部分行列を探します。例を使って問題を理解しましょう。入力 : mat[][] = {    {1, 5, 7, 9},    {2, 4, 6, 8},    {1, 2, 5, 6},    {3, 6, 9, 3} } sum = 22 Si

問題概要 この問題では、文字列 str と整数 pow が与えられ、指定されたパワーを持つ部分文字列を見つけることが求められます。 具体的には、パワーの合計が pow と一致する部分文字列を返す必要があります。 文字列のパワーとは、その文字列に含まれる各文字のパワーの総和として定義されます。 各文字のパワーは次のように対応しています:a → 1、b → 2、c → 3 …(アルファベットの出現順に対応) 問題を理解するための例 入力 : string = programming、power = 49出力 : pro 解説 − 部分文字列 pro のパワー:power(p) = 16power

この問題では、N個の正の整数がソートされていない状態で格納された配列 arr[] が与えられます。私たちの課題は、指定された合計値と一致する部分配列を見つけることです。問題を理解するための例入力 : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11 出力 : 部分配列 = {1, 4, 6}説明 −部分配列の合計 = 1 + 4 + 6 = 11解法アプローチ①：ネストしたループを使う単純な方法最もシンプルな解決策は、ネストしたループ（二重ループ）を使用する方法です。外側のループで配列を走査し、内側のループで各開始位置から考えられるすべての部分配列を生成します。それ

問題の概要この問題では、ソートされていないN個の整数で構成される配列 arr[] が与えられます。求められているのは、指定された合計値に等しくなる部分配列（連続する要素の並び）を見つけることです。具体例で問題を確認しましょう。入力 : arr[] = {2, 5, -1, 4, 6, -9, 5}、合計 = 14 出力 : 部分配列 = {5, -1, 4, 6}説明 −部分配列の合計 = 5 + (-1) + 4 + 6 = 14解法アプローチ1：二重ループによる全探索最もシンプルな解法は、ネストされたループ（二重ループ）を使う方法です。外側のループで配列を走査し、内側のループで各開始位置か

問題概要 この問題では、二分木が与えられ、その木に含まれるすべての「左葉（左の子である葉ノード）」の値の合計を求めることが課題となります。 具体例を使って問題を確認しましょう。 入力： 出力：11 説明− 木の左葉ノードは：2, 9 合計 = 2 + 9 = 11 ここで「左葉」とは、親ノードの左の子であり、かつ子を一切持たないノードを指します。上図の例では、ノード2とノード9がこの条件を満たすため、その合計値11が答えになります。 解決アプローチ 1：再帰 最もシンプルな解決策は、木をルートから葉へ向かって走査する方法です。走査の過程で、注目しているノードの左の子が葉ノードであ

問題概要この記事では、C++ を使って二分木の中からすべての右葉ノード(親ノードの右側の子であり、かつ子ノードを持たないノード)を検出し、その値の合計を求める方法を解説します。まず、具体例で問題を確認してみましょう。入力:出力: 8説明:この木の右葉ノードは 1 と 7 合計 = 1 + 7 = 8上図の二分木では、ノード 4 の右の子である「1」と、ノード 6 の右の子である「7」が右葉ノードに該当します。したがって、合計は 1 + 7 = 8 となります。解法1: 再帰によるアプローチ最もシンプルな解決策は、木を根から葉へ向かって再帰的に走査する方法です。各ノードに対して、その右の子が葉ノ

この記事では、n個の整数からなる配列 arr[] が与えられたときに、一意な(重複しない)部分配列の合計値をすべて集め、その総和を求める方法をC++で解説します。ここでいう「部分配列の合計」とは、ある部分配列に含まれる全要素を足し合わせた値のことです。問題の確認まず、具体例を使って問題を理解しましょう。入力: arr[] = {1, 2, 4} 出力: 23解説:配列のすべての部分配列は次のとおりです: (1), (2), (4), (1, 2), (2, 4), (1, 2, 4) 部分配列の合計 = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23解法1:

この問題では、自然数 N が与えられ、N のすべての約数について、それぞれが持つ約数の総和を求め、それらをすべて合計するという課題に取り組みます。 問題の例 入力：N = 12 出力：55 説明： 12 の約数は「1, 2, 3, 4, 6, 12」の 6 個です。各約数の約数の総和は以下のようになります。 1 → (1) = 1 2 → (1 + 2) = 3 3 → (1 + 3) = 4 4 → (1 + 2 + 4) = 7 6 → (1 + 2 + 3 + 6) = 12 12 → (1 + 2 + 3 + 4 + 6 + 12) = 28 合計 = 1 + 3 + 4

この問題では、連結リスト（リンクリスト）が与えられ、偶数の値を持つノードの合計と奇数の値を持つノードの合計をそれぞれ求めることが課題となります。問題の例具体的な入力と出力を見て、問題のイメージをつかみましょう。入力：連結リスト：3 → 2 → 5 → 7 → 1 → 9 出力：evenSum = 2 ; oddSum = 25説明：evenSum = 2（偶数は 2 のみ） oddSum = 3 + 5 + 7 + 1 + 9 = 25解決アプローチ最もシンプルな解法は、リンクリストを先頭から順に走査し、各ノードの値が偶数か奇数かを判定しながら、対応する合計値に加算していく方法です。リスト全体

問題概要 この記事では、正の整数かつ互いに異なる要素からなる2つの配列が与えられ、2つの配列から選んだペアの中で最大の合計を求めるという問題を扱います。 つまり、それぞれの配列から1つずつ要素を選んで作られるペアの中から、合計が最大になる組み合わせを見つけます。 具体例で問題を確認しよう 入力 : arr1[] = {3, 7, 5}, arr2[] = {8, 2, 4} 出力 : 15 説明 − 最大ペアは (7, 8) → 7 + 8 = 15 解き方のアプローチ アプローチ1: ネストしたループによる全探索 最もシンプルな方法は、ループを使ってすべてのペアの合計を調べることです。ネ

この問題では、整数値 N が与えられ、「1² − 2² + 3² − 4² …」という符号が交互に入れ替わる平方数の級数について、第 n 項までの合計を求めることが課題となります。 問題の確認 まず、具体例を見てみましょう。 入力：N = 3出力：6 説明：12 − 22 + 32 = 1 − 4 + 9 = 6 解法1：ループを使うシンプルな方法 最も直感的な解き方は、ループ処理を使う方法です。反復変数 i を 1 から n まで回しながら、次のように処理します。 i が奇数の場合 → 合計（sum）に i2 を加算する i が偶数の場合 → 合計（sum）から i2 を減算する ループ

この問題では、整数値Nが与えられます。私たちのタスクは、n番目の項が n² − (n−1)² となる級数の、第n項までの和を求めることです。 問題の例 入力：N = 3 出力：9 説明： [12 − 02] + [22 − 12] + [32 − 22] = 1 + 3 + 5 = 9 解法のアプローチ この問題を効率的に解くには、級数の一般項を求め、そこから第n項までの和を表す公式を導出します。公式を使って直接計算できれば、計算時間をO(1)に抑えることができます。また、結果が非常に大きな値になる可能性があるため、剰余（mod）を取る必要があります。 まず、級数の第n項の公式を導出してみまし

この問題では、整数値 N が与えられ、級数「√3 + √12 + √27 + …」の最初の n 項までの総和を求めることが課題となります。 この級数は次のように表されます。 √3 + √12 + √27 + √48 + … つまり、これは平方根の数列です。各項は 3 の倍数の平方根になっています。 問題を理解するための例 入力 : N = 3 出力 : 10.3922 説明： √3 + √12 + √27 = 1.7320 + 3.4641 + 5.1961 = 10.3922 解法のアプローチ この問題を効率的に解くには、まず級数の一般項を見つけ、その上で n 項までの総和を公式から計算しま

この問題では、整数値 N が与えられ、級数「1 − 2 + 3 − 4 + 5 − 6 + 7 …」の第 n 項までの合計を求めることが課題となります。 対象となる級数は次のとおりです。 1 − 2 + 3 − 4 + 5 − 6 + 7 − 8 + 9 − 10 … 問題の例 具体例を使って問題を確認してみましょう。 入力 : N = 4 出力 : -2 説明： 1 − 2 + 3 − 4 = -2 解法のアプローチ この問題を解くシンプルな方法は、級数の一般項（規則性）を見つけ出し、n 項までの合計を数式で表すことです。公式を使って合計を計算できれば、計算時間は O(1) にまで短縮できま