C++

ブール行列とはブール行列（Boolean Matrix）とは、要素が「0」と「1」の2種類のみで構成される行列のことです。この問題では、m×n のサイズのブール行列 arr[m][n] が与えられます。求解条件は次のとおりです。条件： もし m[i][j] = 1 であるなら、i 行目のすべての要素と j 列目のすべての要素を 1 にする。具体例入力と出力の例を見てみましょう。入力: arr[2][2] =1 00 0出力: arr[2][2] =1 11 0説明： arr[0][0] = 1 であるため、0 行目のすべての要素（arr[0][0] = arr[0][1] = 1）と、0 列目

本題に入る前に、まずこの記事に関連する重要な用語を確認しておきましょう。 前提知識の整理 コピーコンストラクタとは コピーコンストラクタとは、渡されたオブジェクトと全く同じ内容を持つ新しいオブジェクトを生成するための特殊なコンストラクタです。同じクラスの別オブジェクトを引数に受け取り、そのメンバ変数の値を複製します。 仮想関数（virtual関数）とは 仮想関数とは、基底クラス（親クラス）で宣言され、その基底クラスを継承した派生クラス（子クラス）で再定義（オーバーライド）されるメンバ関数のことです。仮想関数を使うことで、ポインタ経由でも実際のオブジェクトの型に応じた関数が呼び出されるようになり

プログラミング言語における演算子（Operator）とは、コンパイラに対して何らかの操作を実行するよう指示するための記号です。alignof演算子は、指定された型の変数に適用されるアライメント（境界調整）を返す演算子です。戻り値はバイト単位で表されます。構文var align = alignof(型)各要素の説明alignof − 入力されたデータ型のアライメントを返すために使用される演算子です。パラメータ（型） − アライメントを取得したいデータ型を指定します。戻り値 − 指定したデータ型のアライメントとして使用される値（バイト単位）です。例1：基本データ型のアライメントを取得する次のプログ

アリコット数列とは アリコット数列(Aliquot Sequence)は、特殊な性質をもった数列です。数列はある整数から始まり、次の項は直前の項の真の約数(その数自身を除く約数)の総和として定義されます。 具体的な例で確認してみましょう。 入力 : 8 出力 : 8 7 1 0 解説 : 8 の真の約数は 4, 2, 1。その和は 7 7 の真の約数は 1。その和は 1 1 の真の約数は存在しないため、その和は 0 完全数・友愛数・社交数との関係 アリコット数列は、以下の3種類の特別な数と深い関わりがあります。 完全数:数列の長さが1(自分自身に戻る)となる数。例:6

フィボナッチ数とは、一般に 0, 1 または 1, 1 の2つの固定された数から始まり、それ以降の各項が直前の2つの項の和となる数列として定義されるものです。例えば、フィボナッチ数列の最初の12項は「0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89」となります。この数列を一般化すると、n番目の項は(n-1)番目の項と(n-2)番目の項の和に等しくなります。これをもとに、フィボナッチ数列のn番目の項を求める漸化式は次のように表せます。Tn = Tn-1 + Tn-2この式を使って5番目の項を求める場合、すでに分かっている3番目と4番目の項を代入して計算します。T5

匿名（anonymous）とは、名前を持たずに定義されたあらゆる存在を指します。名前が付けられていないクラスは、C++では匿名クラス（anonymous class）と呼ばれます。匿名クラスには、次のような特別な性質があります。クラスに名前が存在しないため、コンストラクタは割り当てられません。ただし、メモリブロックを解放するためのデストラクタは用意されています。関数の要素として利用することはできません。すなわち、引数として渡したり、関数から返される値を受け取ったりすることはできません。こうした性質から、匿名クラスは「一度だけインスタンス化したい」「ごく限られた範囲でしか使わない」ようなケースに

「最小ページ数の割り当て（Allocate Minimum Number of Pages）」は、競技プログラミングや技術面接で頻出する古典的なアルゴリズム問題の一つです。この記事では、問題の内容を詳しく解説し、二分探索を用いた効率的な解法をC++のサンプルコードとともに紹介します。 問題文 n冊の異なる本のページ数が与えられます。また、これらの本を割り当てる対象としてm人の学生がいます。本はページ数の昇順に並べられており、各学生には連続した本のみを割り当てることができます。プログラムは、一人の学生が読むことになる最大ページ数を返しますが、その最大値ができるだけ小さくなるような割り当てを行う

ほぼ完全数（Almost Perfect Number）とは？ほぼ完全数（Almost Perfect Number）は、「最小不足数（least deficient number）」や「わずかに不足した数（slightly defective number）」とも呼ばれる特殊な数です。その約数の総和（1とその数自身を含む）が 2n-1 に等しくなる数を指します。本記事では、与えられた数がほぼ完全数であるかどうかを判定するアルゴリズムを、具体例を交えながら解説します。具体例で理解するまず、例を見ながら概念を確認しましょう。入力：16出力：Yes説明：16の約数は 1, 2, 4, 8, 16

この問題では、2つの数値の交互のビットを使って新しい数値を生成します。具体的には、2番目の数値から1番目のビットを、1番目の数値から2番目のビットを、再び2番目の数値から3番目のビットを、1番目の数値から4番目のビットを…というように、LSB（最下位ビット）側から順に交互にビットを取り出していきます。 まず、例を使って問題をより深く理解しましょう。 入力 : n = 6, m = 10 出力 : 2 説明 : 6 のビット表現 = 0110 10 のビット表現 = 1010 0 1 1 0 （n = 6） ^ ^ ← この位置のビットを採用 1 0 1 0 （m =

文字列とは文字の配列です。この問題は、文字列の各要素を「大文字と小文字が交互に現れるように」並べ替えることを目的としています。 問題の概要 「交互 小文字・大文字 文字列ソート」とは、大文字と小文字が混在し、順序がバラバラの文字列が与えられたとき、それを大文字と小文字が交互の位置に配置され、かつそれぞれがソート済みの順序になっている状態に並べ替える問題です。 具体例を見て理解を深めましょう。 入力 : aFegrAfStRzsV 出力 : AaFeRfSgVrstz 説明 : 大文字 : A F R S V 小文字 : a e f g r s t z 大文字と小文字はそれぞれ昇順に整列されてい

単方向連結リスト(シングルリンクリスト)は、「データ」と「次の要素へのポインタ」の2つの部分から構成される線形データ構造です。 奇数・偶数が交互に並ぶ連結リストとは? 奇数・偶数交互連結リストとは、あるノードのデータが偶数であれば、その隣のノードのデータは奇数になるように並んだ連結リストのことを指します。 本記事では、既存の単方向連結リストを、以下のいずれかの形式に並べ替える問題を扱います。 先頭が偶数の場合:1番目が偶数、2番目が奇数、3番目が偶数…という順序で並べる 先頭が奇数の場合:1番目が奇数、2番目が偶数、3番目が奇数…という順序で並べる 具体例で理解しよう 例として、次の連

リンクリスト（連結リスト）は、要素そのものに加えて次のノードへのポインタも保持する線形データ構造です。本記事で扱う「交互ソート（alternate sort）」とは、リンクリストを以下のような順序で並べ替えることを指します。1番目のノードには最小値、2番目のノードには最大値、3番目のノードには2番目に小さい値、4番目のノードには2番目に大きい値……というように、最小値と最大値を交互に配置していきます。問題の例具体例を見てみましょう。 8要素を昇順に並べると「1, 3, 4, 8, 21, 67」です。求められる出力は、このソート済み列の先頭から1つ、末尾から1つと交互に値を取り出して構成します

交互ソートとは交互ソートとは、整数配列の要素を「最大値・最小値・2番目に小さい値・2番目に大きい値…」という順序で並べ替える手法です。つまり、大きい値と小さい値が交互に出力されるような並び方になります。具体例を見てみましょう。入力 : 4 1 8 2 9 3 7 出力 : 9 1 8 2 7 3 4 説明 : 配列を昇順にソートすると「1 2 3 4 7 8 9」になります。 これを交互ソートの形式に並べ替えると、まず最大値の9、 次に最小値の1、続いて8、2、7、3、4 の順に出力されます。この概念を理解したところで、解決策を考えてみましょう。最もシンプルなアプローチは、まず配列を通常通りソ

本記事では、正方形の一辺の長さが与えられたときに、その正方形の外接円の面積を求める方法について解説します。まず、理解を深めるために基本的な定義をおさらいしましょう。 基本用語の定義 正方形：すべての辺の長さが等しい四角形のことです。 外接円：多角形のすべての頂点に接する円のことです。 面積：二次元図形の広がりの大きさを数量的に表したものです。 外接円の面積の求め方 正方形の外接円の面積を計算するには、円と正方形それぞれのパラメータの間にある関係を見つける必要があります。 下の図のように、正方形のすべての頂点が円に接しています。この図から読み取れる重要な性質は、正方形の対角線の長さが円の直径

この記事では、指定された辺の長さを持つn辺の正多角形の面積を求める問題を取り上げ、図形の面積を計算する公式を導出し、それに基づいたプログラムを作成します。まず、内容を理解しやすくするために、基本事項をおさらいしましょう。基本事項のおさらいn辺の正多角形とは、すべての辺の長さが等しいn個の辺を持つ多角形のことです。例えば、正五角形や正六角形などが挙げられます。面積とは、二次元の図形が占める広がりの大きさを数量的に表したものです。面積公式の導出正多角形の面積を求めるには、図形を構成する個々の三角形の面積を求め、それに辺の数nを掛けます。正多角形は、中心を共有する頂点としてn個の二等辺三角形に分割で

このプログラムでは、与えられた頂点の座標をもとに、多角形の面積を求めます。本題に入る前に、理解を深めるために基本的な用語をおさらいしておきましょう。 基本用語のおさらい 面積 面積とは、2次元の図形が占める広がりの大きさを数量的に表したものです。 多角形 多角形とは、一定の数の辺で構成される閉じた図形のことです。 頂点の座標 頂点の座標とは、2次元平面上における点の位置を示す値のことです。例えば (0, 0) のように表されます。 面積を求める数式 多角形の各頂点の座標が分かっていれば、次の「靴紐公式」と呼ばれる数式を使うことで、その面積を計算できます。 Area = ½ [(x1

ここでは一つの問題を取り上げます。ある配列 arr が与えられたとき、その配列が以下の条件をすべて満たす形で2つの部分に分割できるかどうかを判定する必要があります。両方の部分配列の要素の合計が等しくなること5の倍数であるすべての要素は、必ず同じグループに属すること3の倍数だが5の倍数ではないすべての要素も、必ず同じグループに属すること上記以外の要素は、どちらのグループに配置しても構わないこと例として、配列の要素が {1, 4, 3} である場合を考えてみましょう。この場合は分割が可能です。なぜなら、{1, 3} の合計（4）と {4} の合計（4）が等しく、さらに5の倍数・3の倍数に関するグル

問題の概要 長さ n のバイナリ文字列(0と1だけで構成された文字列)と整数 k が与えられます。この文字列を k回連結したあと、連結結果の中に現れる連続する「0」の最大個数を求めるのが本記事の目的です。 たとえば、バイナリ文字列が 0010010、k = 2 の場合、連結後の文字列は 00100100010010 となり、この中で最も長い連続する0は中央の「000」の部分、つまり 3個 です。 解法のアプローチ この問題は、連結後の巨大な文字列を実際に作らずとも、元の文字列の性質だけから答えを導き出せます。ポイントは次の2つです。 文字列がすべて「0」の場合: 答えは単純に n × k に

2つの整数 N と P が与えられ、P が N 個の未知の整数の積であるとします。このとき、これらの整数のGCD（最大公約数）を求める必要があります。ただし、同じ積 P になる整数の組み合わせは複数存在し得るため、その中で最も大きなGCDを求めることが目標です。例として、N = 3、P = 24 の場合を考えてみましょう。積が24になる3つの整数の組み合わせには {1, 1, 24}、{1, 2, 12}、{1, 3, 8}、{1, 4, 6}、{2, 2, 6}、{2, 3, 4} などがあり、それぞれのGCDは 1, 1, 1, 1, 2, 1 となります。したがって、この場合の答えは 2

n×n のサイズで与えられた行列を、種類を問わず対角行列へ変換するのが本記事のテーマです。C++による実装方法を、考え方・アルゴリズム・サンプルコード・実行結果まで含めてわかりやすく解説します。 対角行列とは？ 対角行列とは、n×n の正方行列のうち、対角成分（行番号と列番号が一致する要素）以外のすべての要素が 0 である行列を指します。対角成分自体には任意の値を入れることができます。 下図は、非対角成分を 0 に変換するイメージです。 | 1 2 3 | | 1 0 3 | | 4 5 6 | → | 0 5 0 | | 7 8 9 |