C++

このチュートリアルでは、4つの配列から1つずつ要素を選んだとき、そのXOR（排他的論理和）が指定した値xと等しくなる組み合わせ（4つ組）の個数を求めるプログラムについて解説します。具体的には、4つの配列と値xが与えられ、各配列から1つずつ要素を選んで作れるすべての組み合わせの中から、XORの結果がxと一致するものを数えるのが目的です。解き方のアプローチ最もシンプルな方法は、4重のループを使った総当たり（ブルートフォース）です。4つの配列から選べる要素の組み合わせをすべて列挙し、それぞれについてXORを計算します。結果がxと等しければカウントを1つ増やし、最終的なカウントを答えとして返します。サ

このチュートリアルでは、バイナリ配列の接頭辞（プレフィックス）のうち、指定した値 x で割り切れるものの個数を求めるプログラムについて解説します。具体的には、バイナリ配列と整数値 x が与えられ、先頭から各要素までを見たときに構成される2進数（接頭辞）が x で割り切れる箇所がいくつあるかを数えるのが目的です。アルゴリズムの考え方配列を先頭から順に走査しながら、それまでの要素で表される2進数の値を更新していきます。新しい桁が追加されると、これまでの値は「前の値 × 2 ＋ 現在のビット」で表されます。この値が x で割り切れるたびにカウントを1つ増やし、最終的なカウントを結果として返します。実

このチュートリアルでは、グラフ上において始点（ソース）から終点（デスティネーション）まで、ちょうどk本の辺を使って到達できるウォーク（歩行経路）の総数を求めるC++プログラムについて解説します。前提として、グラフ（隣接行列）と始点・終点の値が与えられます。私たちのタスクは、始点から出発して終点に至るまでの経路のうち、正確にk本の辺を通るものをすべて数え上げることです。アルゴリズムの考え方ここでは再帰を用いたシンプルなアプローチを採用します。基本的な考え方は次のとおりです。k = 0 のとき：現在位置が終点と一致していれば、経路は1つと数えます。k = 1 のとき：現在位置から終点へ直接移動でき

はじめに このチュートリアルでは、与えられた配列の中から積がK以下になる部分列(サブシーケンス)の個数を求めるプログラムをC++で解説します。 具体的には、配列と値Kが与えられ、その積がK以下となる空でない部分列が何個存在するかを数えるのが目的です。 アプローチのポイント:対数変換 積をそのまま計算してKと比較すると、値が急激に巨大化しオーバーフローを起こす恐れがあります。そこで本手法では、次のような工夫を行います。 配列の各要素を log2 で対数に変換し、積の問題を和の問題に帰着させる Kも log2(K) に変換し、「積 ≤ K」という条件を「対数の和 ≤ log2(K)」として扱う

このチュートリアルでは、C++ STLのstd::listをコンストラクタを使って作成する方法について解説します。 リスト（list）は、メモリ上に要素を非連続的な形で格納するデータ構造です。内部的には双方向連結リストとして実装されており、vectorと比較して任意の位置への要素の挿入・削除が高速に行えるという特徴があります。 コンストラクタによるリストの初期化 std::listは、コンストラクタに「要素数」と「初期値」を渡すことで、指定した値で満たされたリストを簡単に生成できます。以下の例では、値100で初期化された10個の要素を持つリストを作成しています。 サンプルコード #includ

このチュートリアルでは、C++でpair（ペア）をキーとするunordered_mapを作成する方法について詳しく解説します。unordered_mapは、デフォルトではpair型に対するハッシュ関数を提供していません。そのため、pairをキーとして使用したい場合は、カスタムハッシュ関数を明示的に指定する必要があります。カスタムハッシュ関数の実装例以下のコードでは、hash_pairという構造体を定義し、unordered_mapのテンプレート引数として渡しています。#include <bits/stdc++.h> using namespace std; // 任意のpairに対

このチュートリアルでは、C++でユーザー定義クラスをキーとして使用するunordered_map（ハッシュマップ）を作成する方法について解説します。 std::unordered_mapは、intやstringなどの組み込み型をキーにする場合、標準ライブラリがデフォルトのハッシュ関数を提供しています。しかし、独自に定義したクラスや構造体をキーとして扱いたい場合は、その型に対応したハッシュ関数を自分で用意する必要があります。具体的には、ハッシュ関数を関数オブジェクト（ファンクタ）として定義し、unordered_mapのテンプレート引数の第3引数に渡します。さらに、キーの同値性を判定するために、

このチュートリアルでは、C++においてユーザー定義のクラスや構造体を要素とする std::unordered_set を作成する方法について解説します。通常の int や string などの基本型であれば、標準ライブラリがハッシュ関数を提供しているため、そのまま unordered_set を利用できます。しかし、独自に定義した構造体やクラスにはデフォルトのハッシュ関数が存在しないため、等価比較用の演算子（operator==）とカスタムハッシュ関数を自分で実装する必要があります。実装の手順具体的には以下の2つを準備します。operator== のオーバーロード： 要素同士が同一かどうかを判

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を使用して、2つの配列に共通する要素を見つける方法について解説します。2つの配列の共通要素を求めるには、set_intersection()メソッドを使用します。この関数は、あらかじめソートされた2つの範囲を受け取り、双方に存在する要素だけを出力先のコンテナへコピーします。そのため、呼び出し前に必ずsort()などで配列を昇順に並べておく必要があります。サンプルコード#include <bits/stdc++.h> using namespace std; int main(){ // 配列の定義

この記事では、C++のSTL（標準テンプレートライブラリ）を活用して、2つのvector（ベクター）間に存在する共通要素を見つける方法を解説します。2つのvectorから共通要素を抽出するには、set_intersection()メソッドを使用します。この関数はヘッダーで定義されており、ソート済みの2つの範囲を受け取り、両方に共通して含まれる要素を出力先の範囲へ書き込みます。なお、set_intersection()は入力となる範囲が事前にソートされていることを前提として動作するため、呼び出し前にsort()で各vectorを並べ替えておく必要があります。また、戻り値としては出力範囲の末尾を指

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を使用して、ベクトルの中から最大要素を見つける方法について解説します。ベクトルから最大要素を取得するには、<algorithm>ヘッダーに用意されているmax_element()関数を使用します。この関数は、指定したイテレータの範囲[first, last)の中から最大の要素を指すイテレータを返します。戻り値はイテレータであるため、先頭に間接参照演算子（*）を付けることで、実際の要素の値を取得できます。サンプルコード#include <bits/stdc++.h> using namespace std

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を使用して、ベクトル内の要素の合計を求める方法について詳しく解説します。 ベクトルの要素の合計を計算する場合、STLのnumericヘッダーに含まれているaccumulate()関数を使うのが最もシンプルで効率的な方法です。 accumulate()関数とは accumulate()は、指定された範囲内のすべての要素を順番に加算し、その合計値を返す関数です。第3引数には初期値を指定します。通常は0を指定しますが、この初期値を変更することで、合計に任意の値を加算することもできます。 サンプルコード #include <bi

はじめに 本記事では、C++において、あるクラス型を別のクラス型へ変換する方法について詳しく解説します。 クラス型同士の変換は、演算子オーバーロード（operator overloading）を活用することで実現できます。これにより、あるクラス型のデータを、別のクラス型のオブジェクトに代入できるようになります。 クラス型変換の基本的な仕組み 変換を実現するには、代入演算子「=」をオーバーロードします。具体的には、変換先のクラス側で operator= を定義し、引数として変換元のクラス型のオブジェクトを受け取ります。この演算子関数の中で、変換元オブジェクトから必要なデータを取得し、変換先クラス

本記事では、C++のSTLにおけるlist begin()関数とlist end()関数の機能と具体的な使い方について解説します。STLにおけるlist（リスト）とはlistは、シーケンス内の任意の位置に対して定数時間での挿入・削除を可能にするデータ構造です。listは双方向連結リストとして実装されており、非連続的なメモリ割り当てが可能です。配列やvector、dequeと比較すると、コンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮するのが特徴です。その一方で、要素への直接アクセス（ランダムアクセス）は低速である点に注意が必要です。また、listはforwar

この記事では、C++ STLのlistコンテナが提供するunique()関数の機能と使い方について解説します。 STLにおけるlistとは listは、シーケンス内の任意の位置に対して定数時間O(1)での挿入・削除を可能にするコンテナです。内部的には双方向連結リストとして実装されており、メモリは非連続的に確保されます。そのため、配列やvector、dequeと比べて、コンテナ内の任意の位置への要素の挿入・抽出・移動が高速に行えるという大きな特徴があります。一方で、先頭や末尾以外の要素への直接アクセス（ランダムアクセス）は遅いという欠点があります。また、listはforward_listとよく似

この記事では、C++ STLにおけるdeque（デック）のresize()関数の機能と具体的な使い方について、サンプルコードと実行結果を交えながら詳しく解説します。deque（両端キュー）とはdequeは「Double Ended Queue（両端キュー）」の略で、シーケンスコンテナの一種です。先頭と末尾の両端から要素の追加・削除ができる点が最大の特徴です。通常のキュー（queue）データ構造では、データの挿入は末尾からのみ行い、削除は先頭からのみ行います。バス停の行列をイメージすると分かりやすいでしょう。新しい人は列の末尾に並び、先頭にいる人から順に乗車して列から外れていきます。一方、deq

本記事では、C++のSTLにおけるlistコンテナのinsert()関数の機能と使い方について詳しく解説します。 STLのlistとは listは、シーケンス内の任意の位置に対して定数時間での挿入と削除を可能にするコンテナです。listは双方向連結リストとして実装されており、非連続的なメモリ割り当てを行います。配列、vector、dequeと比較して、コンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮します。一方で、要素への直接アクセス（ランダムアクセス）は低速です。listはforward_listと似ていますが、forward_listは単方向連結リストで

C++ STLにおけるdequeのpush_back()関数の機能と具体的な使い方について、構文やパラメータ、サンプルコードを交えながら詳しく解説します。 deque（デック）とは dequeは「Double Ended Queue（両端キュー）」の略称で、コンテナの両端から要素の追加・削除が可能なシーケンスコンテナです。 通常のキュー（queue）データ構造では、データの挿入は末尾からのみ、削除は先頭からのみ行えます。バス停の行列をイメージすると分かりやすいでしょう。行列に人は末尾からしか加わらず、先頭にいる人から順番に乗車していきます。一方、dequeではこの挿入と削除が両端のどちらからで

本記事では、C++ STLにおけるdeque front()関数およびback()関数の機能について詳しく解説します。 Deque（両端キュー）とは Deque（Double Ended Queue、両端キュー）とは、コンテナの両端で要素の挿入・削除が可能なシーケンスコンテナのことです。通常のキュー（待ち行列）データ構造では、データの挿入は末尾からのみ行い、削除は先頭からのみ行います。バス停の行列を例に考えてみましょう。人は行列の末尾にしか並ぶことができず、先頭にいる人から順に乗車していきます。一方、両端キューでは、データの挿入も削除も両端のどちらからでも行うことができます。 deque fr

C++のstd::deque（両端キュー）における back() 関数は、コンテナの末尾（最後）の要素を参照するためのメンバ関数です。戻り値は参照型のため、取得した要素を読み取るだけでなく、直接書き換えることも可能です。 構文 dequename.back() back() は引数を一切取らず、呼び出しにかかる計算量は O(1) と非常に高速です。 使用例 入力： Deque − 11 12 13 14 15出力： 15 入力： Deque − C H O I C E出力： E 処理の手順 まず deque を宣言して初期化する 次に deque の内容を出力する その後、back(