C++

この記事では、2次元配列 mat[n][m] が与えられたときに、「位置要素」の数を求める問題を解説します。ここでいう「位置要素」とは、その要素が属する行または列における最大値もしくは最小値に該当する要素のことを指します。入力例mat[][] = {2, 5, 7} {1, 3, 4} {5, 1, 3}出力例8説明上記の行列では、2, 5, 7, 1, 4, 5, 1, 3 の8つの要素が位置要素に該当します。たとえば1行目の最大値は7、最小値は2であるため、どちらも位置要素としてカウントされます。解法アプローチ最もシンプルな解き方は、次の手順に従う方法です。各行の最大値・最小値をあらかじめ

問題の概要 この問題では、次のような形式で表されるn個の変数を持つ線形方程式が与えられます。 coeff1(var1) + coeff2(var2) + … + coeffn(varn) = value この線形方程式の解が全部でいくつ存在するのかを求めるのが目的です。 入出力例で問題を理解する まずは具体的な例を見てみましょう。 入力 coeff[] = {3, 1}, value = 4 出力 1 説明 方程式：3x + y = 4 解：x = 0, y = 4 解法のアプローチ 最もシンプルな解き方は、方程式の値を段階的に評価していく方法です。各係数をvalueから順に引いてい

要素数 N の配列 arr[] が与えられたとき、合計が偶数となる部分配列（連続部分配列）の個数を求める問題について解説します。 問題の例 入力 arr[] = {2, 1, 3, 4, 2, 5} 出力 28 この配列において、合計が偶数となる連続部分配列は全部で 28 個存在します。（元記事の列挙には非連続の部分配列（部分列）が混在していましたが、ここでは標準的な定義である「連続部分配列」としてカウントしています。） 解法 1：ブルートフォース法（全探索） 最も直感的な方法は、すべての部分配列の合計を計算し、偶数かどうかを判定することです。計算量は O(N^2) となります。 アルゴリ

この記事では、同じサイズの2つの行列 mat1 と mat2 が与えられたとき、一方の行列を操作してもう一方と等しくするために必要な変換の回数を求める方法を解説します。 問題の概要 許可されている変換操作は以下の3ステップです。 2つの行列のどちらか一方を選ぶ 選んだ行列から1つの行または列を選ぶ 選んだ行または列のすべての要素に1を加える 入力例 mat1[][] = {{1, 2}, {2, 1}} mat2[][] = {{2, 3}, {4, 3}} 出力例 3 解説 以下のように3回の操作で2つの行列を一致させることができます。 1

この問題では、サイズNの3つの配列 s1[]、s2[]、s3[] が与えられ、それぞれN個の三角形を表しています。与えられたN個の三角形の中から「一意な三角形」の数を見つけることが課題です。三角形が一意であるためには、そのすべての辺が他のどの三角形とも一致しない必要があります。つまり、同じ辺の組み合わせを持つ三角形が他に存在してはいけません。入力例s1[] = {1, 5, 3} s2[] = {2, 3, 2} s3[] = {4, 2, 5}出力例1説明辺が 1、2、4 の三角形だけが一意です。残りの2つの三角形は、辺をソートするとどちらも {2, 3, 5} という同じ組み合わせになるた

この記事では、3つの整数値 L、R、k が与えられたときに、指定された範囲 [L, R] 内で約数がちょうどk個である数の個数を求める方法を解説します。なお、約数のカウントには「1」と「その数自身」も含まれます。入力例と出力例入力a = 3, b = 10, k = 3出力2説明3から10の範囲内で、約数がちょうど3個である数は次の通りです。 4 : 約数 = 1, 2, 4 9 : 約数 = 1, 3, 9解法アプローチ最もシンプルな解決策は、範囲内の各数について約数の個数を順番に数えていくことです。しかし、ここには重要な数学的な性質があります。約数の個数が奇数になるのは、その数が完全平方数

問題概要 この問題では、3つの整数 L、R、k が与えられます。目的は、与えられた範囲 [L, R] 内に存在する「約数の個数がちょうど k 個」である数をすべて数えることです。なお、1 とその数自身も約数としてカウントします。 具体例で問題を確認しましょう。 入力 a = 3, b = 10, k = 4 出力 2 説明 範囲 3〜10 の中で約数がちょうど 4 個ある数は以下の通りです。 6 : 約数 = 1, 2, 3, 6 8 : 約数 = 1, 2, 4, 8 解法アプローチ 最もシンプルな解法は、範囲内の各数について約数の個数を実際に数え上げる方法です。具体的には、[a,

この記事では、文字値で構成される行列（2次元配列）と、検索対象となるパターンが与えられたとき、そのパターンが行列の中で水平方向と垂直方向のどちらに存在するのかを判定する問題を解説します。問題の例具体的な入力と出力を見てみましょう。入力mat[][] = { { r, a, m }, { a, m, c }, { w, f, t } } Pattern : raw出力verticalこの例では、パターン「raw」は1列目に上から下へ向かって「r → a → w」と並んでいるため、垂直方向に存在すると判定されます。解法アプローチ最も単純な解法は、行列のN行すべてに対して長さ

この問題では、直角三角形の一辺を表す整数 a が与えられます。その辺を持つ直角三角形が存在するかどうかを判定し、存在する場合は残りの2辺と各角度を求める必要があります。入力例a = 5出力例辺 : 5, 12, 13角度 : 67.38, 22.62, 90説明直角三角形の3辺は 52 + 122 = 132 という関係を満たします。これらの辺の値から、角度は sin-1(5/13) および 90 − sin-1(5/13) として求められます。解法アプローチ最もシンプルな解法は、ピタゴラスの定理（三平方の定理）を利用することです。直角三角形の3辺は必ず次の関係を満たします。a2 + b2 =

この問題では、直角三角形の一辺を表す整数 a が与えられます。その一辺を持つ直角三角形が成り立つかどうかを判定し、成り立つ場合には残りの2辺を求めることが課題です。入出力の例入力a = 5出力Sides : 5, 12, 13説明52 + 122 = 132 という関係が成立するため、残りの2辺は 12 と 13 であることがわかります。解法のアプローチこの問題の最もシンプルな解法は、三平方の定理（ピタゴラスの定理）を利用することです。直角三角形の3辺は必ず次の関係を満たします。a2 + b2 = c2ここで、a と b は直角を挟む2辺、c は斜辺を表します。この定理をもとに、与えられた a

この記事では、N個の整数からなる配列 arr[] が与えられたとき、2つの要素の合計値がその配列内にすでに存在するようなペアを見つけるアルゴリズムを解説します。つまり、「ペアの合計値 = 配列内のいずれかの値」となる組み合わせをすべて抽出するのが目的です。問題の理解：入力例と出力例具体的な例を使って問題を確認しましょう。入力arr[] = {1, 2, 4, 6, 7}出力(1, 6), (2, 4)説明ペア (1, 6) の場合：合計値は 7 であり、7 は配列内に存在します。ペア (2, 4) の場合：合計値は 6 であり、6 も配列内に存在します。解法アプローチ1: 全探索（ブルートフォ

この問題では、双方向連結リスト（doubly linked list）とある値 sum が与えられます。求められているのは、連結リスト内からデータの合計が sum と一致するペアをすべて見つけ出すことです。具体例で問題を確認してみましょう。入力head − 2 <-> 5 <-> 6 <-> 9 <-> 12 x = 11出力(2, 9), (5, 6)解説ペア (2, 9) の合計値は 11 ペア (5, 6) の合計値は 11解法アプローチ 1：ネストしたループによる全探索最もシンプルな解法は、連結リスト全体を走査し、要素を1つずつ取り出しな

この記事では、三角形の周囲の長さ（外周）とは何か、三角形の種類ごとの周囲の長さの公式、そしてC++でそれらを求めるプログラムの書き方について詳しく解説します。周囲の長さ（Perimeter）とは周囲の長さとは、図形の外側を1周したときの総距離のことです。基本的には、図形を構成するすべての辺の長さを足し合わせたものになります。三角形の周囲の長さ三角形は3つの辺を持つ図形であるため、その周囲の長さは3辺の長さの合計として求められます。公式：周囲の長さ = すべての辺の合計周囲の長さ = x + y + z三角形の周囲の長さを求めるC++プログラムサンプルコード#include <iostre

この問題では、0と1のみで構成される n×m のサイズのバイナリ行列 bin[][] が与えられます。求めるのは、行列内の 1 から形成される図形の周囲長(ペリメーター)です。周囲長とは、図形を四方すべてから取り囲む外周の長さのことです。例えば、値が1のセルが1つだけある場合、その周囲長は 4 となります。入出力例入力bin[][] = [1, 0] [1, 0]出力6説明セル (0,0) と (1,0) がつながっており、縦2・横1の長方形を形成しています。したがって、周囲長は 2+2+1+1 = 6 となります。解法アプローチこの問題のシンプルな解き方は、行列内のすべて

この記事では、正の整数Nが与えられたときに、その数の「Politeness（礼儀正しさ）」をC++で求める方法を解説します。 Polite Number（礼儀正しい数）とは？ Polite Numberとは、2つ以上の連続する整数の和として表すことができる数のことです。 数のPolitenessは、その数を連続する整数の和で表現できる方法の総数として定義されます。 例で問題を理解する 入力： n = 5 出力： 1 説明：2 + 3 = 5 が唯一の連続する整数の和であり、これ以外の表し方は存在しないため、答えは1になります。 解法アプローチ 1. シンプルな解法（全探索） 最も単純なアプロー

この問題では、無限に続くソート済みの数値で構成される配列が与えられます。私たちのタスクは、その無限配列の中から指定された要素の位置を見つけることです。問題を理解するための例入力arr[] = {2, 4, 6, 8, 9, 12, 14, 17, …}, ele = 9出力4説明要素 9 は配列のインデックス 4 の位置に存在するため、出力は 4 となります。解決アプローチソート済みの配列から要素を効率的に検索するには、二分探索（バイナリサーチ）を使用します。しかし、この問題では配列の終端が不明であるため、通常の二分探索アルゴリズムを少し修正して使う必要があります。具体的な手順は以下の通りです

この問題では、2つの整数 num1 と num2 が与えられ、それぞれを2進数で表したときに初めて値が異なるビット、すなわち最も左側にある相違ビットの位置を求めます。 ビット同士を比較するためには、両者のビット長を揃える必要があります。これには、ビット数が少ない方の数値の先頭に0を補う（桁合わせを行う）方法が用いられます。 入出力例で問題を理解する 入力 num1 = 4, num2 = 7 出力 2 説明 4の2進表現は「100」、7の2進表現は「111」です。 左端のビットはどちらも「1」で一致していますが、左から2番目のビットは「0」と「1」で異なっています。したがって、求める位置は2と

この問題では、ある数字 N が与えられ、その数字が「4」と「7」のみで構成される数列の中で何番目に位置するかを求めることが課題となります。 4と7だけを使って作られる数列は、次のように並びます。 4, 7, 44, 47, 74, 77, 444, … 入力例と出力例 問題を理解するために、具体的な例を見てみましょう。 入力 N = 5 出力 74 説明 数列の5番目までの要素は次の通りです。 4, 7, 44, 47, 74… つまり、5番目の数は 74 であることが分かります。 解法アプローチ：数列のパターンに着目する この問題に対するシンプルかつ効率的な解法は、数列に潜む規則性(パターン

この記事では、2進数表現においてセットビット（値が1になっているビット）が1つだけ存在する整数 N が与えられたとき、その唯一のセットビットの位置を求める方法を解説します。数値にセットビットが1つだけ含まれる場合はその位置を返し、それ以外の場合は「無効な数値」であることを出力します。 具体例で問題を確認してみましょう。 入力 N = 32 出力 6 説明 32 を2進数で表すと「100000」となり、セットビットは6番目（最上位）に1つだけ存在します。 解法のポイント 先に進む前に、押さえておくべき重要な性質があります。それは、「ある数値が2の冪乗であるとき、かつそのときに限り、セットビットは

この問題では、二分探索木（BST：Binary Search Tree）の先行順走査（プレオーダートラバーサル）を表す配列 preOrder[] が与えられます。求めるのは、この先行順走査の情報だけをもとに後行順走査（ポストオーダートラバーサル）を導き出すことです。入出力例で問題を理解しよう入力preOrder[] = {5, 2, 4, 7, 12}出力{4, 2, 12, 7, 5}解決アプローチ最もシンプルな解法は、与えられた先行順走査から実際にBSTを構築し、その木に対して後行順走査を行うことです。確かにこの方法でも正しい答えは得られますが、木を明示的に構築しなくても済む、より効率的な