C++

この記事では、C++ STLにおける multiset コンテナの lower_bound() 関数について、実際のコード例を交えながら詳しく解説します。lower_bound()関数とはlower_bound() は、指定したキー値以上の要素がコンテナ内に最初に現れる位置を指すイテレータを返す関数です。具体的には、以下のような動作を行います。引数に渡した値と等しい要素がコンテナ内に存在する場合、そのうち最初の要素へのイテレータを返します。等しい要素が存在しない場合は、渡した値より大きい要素のうち最小のもの（直後に続く要素）へのイテレータを返します。サンプルコード#include <bi

このチュートリアルでは、C++ STL（Standard Template Library）が提供する連想コンテナの一つである multiset について、実際のサンプルプログラムを通して詳しく解説します。 multiset とは multiset は set と非常によく似た連想コンテナです。両者の最大の違いは、multiset は同じ値を持つ要素（重複値）を複数格納できるという点にあります。set では重複した値を挿入しても無視されますが、multiset ではそのまま保持されます。 また、multiset 内部の要素は常に自動的にソートされて管理されるため、検索や範囲操作を効率的に行う

本チュートリアルでは、メニュー方式で動作するシンプルな電卓プログラムをC++で作成する方法を解説します。 このプログラムを使うと、ユーザーは以下の数学演算の中から希望する処理を選択できます。 加算（足し算） 減算（引き算） 乗算（掛け算） 除算（割り算） 最大公約数（HCF/GCD） 最小公倍数（LCM） メニュー方式とは、選択肢を番号付きで画面に表示し、ユーザーが入力した番号に応じて処理を分岐させる方式のことです。switch文と組み合わせることで、直感的に操作できる対話型プログラムを簡単に実装できます。 サンプルコード #include <bits/stdc++.h> us

このチュートリアルでは、C++ STLのset（std::set）を活用して、サイズkのすべての部分配列（サブアレイ）から最大値を取り出し、その合計を求めるプログラムについて解説します。長さNの整数型配列と整数Kが与えられたとき、先頭からK個ずつ範囲をずらしながら（スライディングウィンドウ方式）、それぞれの範囲内での最大値を求め、それらをすべて合計して出力するのが今回の課題です。アルゴリズムのポイントこの問題を効率的に解く鍵となるのが、C++ STLのset<pair<int, int>>です。pair構造の活用： 要素の「値」と「インデックス」をペアで格納することで、

この記事では、C++ STLのmapコンテナが提供するequal_range()関数について、具体的なコード例を交えながらわかりやすく解説します。equal_range()とはequal_range()は、指定したキーと等しいキーを持つ要素の範囲（レンジ）を表す、イテレータのペア（pair）を返すメンバ関数です。返されるペアのうち、firstには下限（lower bound）に相当するイテレータ、secondには上限（upper bound）に相当するイテレータが格納されます。つまり、この関数を使えば、コンテナ内で「指定したキーに一致する要素が存在する範囲」を一度の呼び出しで取得できるのです。

0と1のみで構成される二次元マトリックス（行列）Aがあるとします。ここでいう「操作」とは、任意の行または列を選び、その行・列内のすべての値を反転させること、つまり0を1に、1を0に一括変更することを指します。任意の回数だけ操作を行った後、マトリックスの各行は2進数として解釈され、マトリックス全体のスコアはこれらの数値の総和となります。今回の課題は、このスコアとして考えられる最大値を求めることです。例えば、入力が以下のようなマトリックスだった場合を見てみましょう。001110101100最適な操作を行った結果、出力は 39 になります。これは反転後のマトリックスが次のようになるためです。1111

この記事では、「N 以上の整数の中で最小となる素数回文（プライムパリンドローム）」を C++ で求めるアルゴリズムを解説します。 例えば N = 13 の場合、答えは 101 になります。13 以上の回文数には 22、33、44 などがありますが、これらはすべて 11 の倍数であるため素数になり得ません。そのため、次に現れる素数回文である 101 が答えとなります。 解法のアプローチ 全ての整数を順に素数かつ回文かどうか調べるのは非効率です。そこで、回文を直接生成することで探索範囲を大幅に絞り込みます。手順は以下の通りです。 N が 8 以上 11 以下の場合は、11 を返します（この範囲

正の整数 N が与えられたとします。この数の桁を任意の順序に並べ替え(元の順序も含む)、先頭の桁が 0 以外になるようにします。そのうえで、並べ替えた結果が 2 の累乗になるような並べ方が存在するかどうかを判定します。たとえば、数値が 46 の場合、答えは true となります。 解法の考え方 この問題は、以下の手順に従って解くことができます。 count というメソッドを定義します。引数として x を受け取ります。 ret := 0 で初期化します。 x が 0 でない間、次の処理を繰り返します。 ret := ret + 10 ^ (x の最下位桁) x := x / 10 r

問題概要数列 X1, X2, ..., Xn が「フィボナッチ型」であるとは、次の条件を満たすことを指します。n >= 3 であるすべての i + 2 <= n に対して、Xi + Xi+1 = Xi+2 が成り立つここで、正整数からなる狭義単調増加配列 A が与えられたとき、A の中に含まれる最も長いフィボナッチ型部分列の長さを求めます。該当する部分列が存在しない場合は 0 を返します。たとえば、配列が [1,2,3,4,5,6,7,8] の場合、答えは 5 になります。このとき最も長いフィボナッチ型部分列は [1,2,3,5,8] です。解法アプローチ：動的計画法(DP)この問

問題概要 N 山のバナナがあり、i 番目の山には piles[i] 本のバナナが入っています。警備員は外出中で、H 時間後に戻ってきます。ココは 1 時間あたり K 本というバナナを食べる速度を自由に決めることができます。毎時間、彼女はどれか 1 つの山を選び、その山から K 本のバナナを食べます。もし山に残っているバナナが K 本未満であれば、その山をすべて食べきり、その時間内にはそれ以上何も食べません。 ココはできるだけゆっくりバナナを食べたいのですが、同時に警備員が戻ってくる前にすべてのバナナを食べ終えたいとも考えています。このとき、H 時間以内にすべてのバナナを食べ切ることができる最

問題の概要 AlexとLeeという2人のプレイヤーが、石の山を使ったゲームを行います。山は一列に並んでおり、その数は必ず偶数、各山には piles[i] 個の石が入っています。ゲームの目的は、最終的に相手より多くの石を手にすることです。石の総数は奇数であるため、引き分けは発生しません。Alexが先手となり、2人は交互に手番を進めます。各ターンでプレイヤーは、列の先頭または末尾にある山を丸ごと1つ取らなければなりません。これを山が無くなるまで繰り返し、最後に多くの石を持っていたプレイヤーの勝利です。両者が常に最適な手を選ぶと仮定したとき、「Alexが勝つかどうか」を判定するのがこの問題です。

問題の概要people という配列が与えられ、i 番目の人の体重が people[i] で表されるとします。各ボートには同時に最大2人まで乗せることができ、ただし搭乗者の体重の合計は limit 以下でなければなりません。この条件のもと、すべての人を運ぶために必要な最小のボート数を求めるのがこの問題のゴールです。たとえば、入力が [3, 2, 1, 2]、limit が 3 の場合、答えは 3 となります。具体的な割り当ては [(1, 2), (2), (3)] のようになります。解法のアプローチ：ソート＋両端ポインタこの問題は、貪欲法（グリーディ法）と両端ポインタ（Two Pointers）

本記事では、R行C列の2次元グリッドを時計回りの渦巻き（スパイラル）状に巡回し、すべてのマスを訪問した順に座標を求める問題「スパイラル行列 III」をC++で解く方法を解説します。 問題の概要 R行C列の2次元グリッドを考えます。スタート地点は (r0, c0) で、最初は東向きに面しています。グリッドの北西の角は第1行・第1列に位置し、南東の角は最終行・最終列にあります。 私たちは時計回りの渦巻き状に歩きながら、グリッド内のすべてのマスを訪問します。途中でグリッドの境界外に出た場合でも、そのまま外側を歩き続け、後で再びグリッド内に戻ることがあります。 求めるのは、訪問した順番に並べたグリッド

N人の人たち（番号は1、2、…、N）がおり、全員を任意のサイズの2つのグループに分割したいと考えます。ただし、それぞれの人は他の人を嫌っている場合があり、嫌いな相手とは同じグループに入ることができません。すなわち、dislikes[i] = [a, b] は、番号aと番号bの人を同じグループに入れてはならないことを意味します。この条件下で、全員を2つのグループに分割できるかどうかを判定するのが本記事のテーマです。 たとえば、入力がN = 4、dislikes = [[1,2],[1,3],[2,4]] の場合、出力は true となり、グループは [1,4] と [2,3] に分けられます。

問題概要負でない整数からなる配列 A があるとします。すべての連続する部分配列 B = [A[i], A[i+1], ..., A[j]]（i ≤ j）に対して、B に含まれる全要素のビットごとのORを計算し、A[i] | A[i+1] | ... | A[j] という結果を得ます。このとき、得られる可能性のある結果の個数を求めるのが目的です。ただし、同じ結果が複数回現れた場合は、最終的な答えには1回だけカウントします。例えば、入力が [1,1,2] の場合を考えてみましょう。部分配列は [1]、[1]、[2]、[1,1]、[1,2]、[1,1,2] の6通りあり、それぞれのORの結果は 1、

ランレングス符号化（Run-Length Encoding）されたシーケンスを順に走査するイテレータの作成を考えてみましょう。イテレータは RLEIterator(int[] A) を呼び出すことで初期化されます。ここで A はシーケンスのランレングス符号化を表しており、すべての偶数インデックス i において、A[i] は非負の整数値 A[i+1] がシーケンス中に繰り返される回数を示します。このイテレータは次の1つの関数をサポートします。 next(int n)：次の n 個の要素（n ≥ 1）を消費し、その中で最後に消費した要素を返します。消費できる要素がもう残っていない場合は、代わりに

問題の概要整数の配列 A が与えられます。各要素 A[i] に対して、x = -K または x = K のどちらか一方を選び、その値を A[i] に加算します（各要素につき1回のみ）。この操作をすべての要素に適用すると、新しい配列 B が得られます。求めるのは、B の最大値と最小値の差として実現できる最小値です。例として、入力が A = [0, 10]、K = 2 の場合を考えてみましょう。このとき B = [2, 8] となるため、出力は 6 になります。解法のアプローチこの問題は、以下の手順で解くことができます。ret := 0、n := 配列 A のサイズ と初期化する配列 A を昇順に

問題概要 ある選挙では、i 番目の票が時刻 times[i] に候補者 persons[i] へ投じられたものとします。ここで、次のようなクエリ関数 TopVotedCandidate.q(int t) を実装することが求められます。この関数は、時刻 t の時点で選挙をリードしていた人物の番号を返します。時刻 t ちょうどに投じられた票もクエリの結果に含まれます。また、同点の場合は、同数の票を持つ候補者のうち最も新しい票を獲得した候補者が勝者となります。 例えば、TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]) で初期化し、q(3

整数型の配列が与えられ、その要素を昇順に並べ替えることを考えます。たとえば、配列が [5,2,3,1] であれば、結果は [1,2,3,5] となります。 この問題はクイックソートのアルゴリズムを使うことで効率的に解けます。クイックソートは平均計算量 O(n log n) の高速なソート手法で、基準値（ピボット）を軸に配列を分割しながら、再帰的に整列を進めていくのが特徴です。 解決のための手順 partition（分割）メソッドを作成します。引数として配列・low・high を受け取ります。 pivot := low と初期化します。 i を low から high - 1 まで繰り返します

問題の概要配列 A が与えられたとき、それを left と right という 2 つの部分配列に分割することを考えます。分割は以下の条件を満たす必要があります。left 部分配列のすべての要素は、right 部分配列のすべての要素以下であるleft と right はどちらも空であってはならないleft のサイズは可能な限り小さくするこのような分割を行った後の left の長さを求めます。なお、条件を満たす分割が存在することは保証されています。例えば、入力が [5,0,3,8,6] の場合、出力は 3 になります。このとき left は [5,0,3]、right は [8,6] となるため