C++

この記事では、C++の標準ライブラリであるChrono（クロノ）ライブラリについて解説します。Chronoライブラリは、日付や時刻を扱うためのライブラリです。タイマーやクロック（時計）の仕組みはシステムによって異なります。そのため、より高い精度で時間を扱いたい場合には、このChronoライブラリを活用すると便利です。Chronoライブラリの特徴：durationとtime_pointの分離Chronoライブラリの大きな特徴は、時間間隔（duration）と時点（time point）を分離して扱う、精度に依存しない設計になっている点です。durationオブジェクトは、「1分」「2時間」「10

C++における文字列比較の基本ここでは、C++で2つの文字列を比較する方法を紹介します。C++にはstringクラスが用意されており、標準ライブラリには文字列比較専用のcompare()関数も存在します。しかし本記事では、==、!=、<、>、<=、>= といった関係演算子を使った比較方法を解説します。これらの演算子は、2つの文字列を先頭から1文字ずつ順番に照合していく仕組みです。それでは、理解を深めるために実際のコードを見てみましょう。サンプルコード#include<iostream> using namespace std; void compareStr

n個の要素を持つ配列Aを考えます。この配列の中から局所最小値（極小値）を見つける必要があります。配列Aにおいて、要素A[x]は、その両隣の要素のどちらとも比較して自分以下である場合に「局所最小値」と呼ばれます。ただし、配列の端にある要素については隣接要素が1つしか存在しないため、その1つとのみ比較を行います。また、局所最小値が複数存在する場合は、そのうちのどれか1つを返せばよいものとします。例えば、配列が [9, 6, 3, 14, 5, 7, 4] の場合を考えてみましょう。このとき局所最小値となるのは 3、5、4 の3つであり、本アルゴリズムはこれらのうちの1つを返します。解法のアプローチ

2つの整数 N と K が与えられたとき、次の式を満たすような「2N個の自然数の順列」を見つける問題を考えてみましょう。 Σ(i=1〜N) |A[2i−1] − A[2i]| + |Σ(i=1〜N) (A[2i−1] − A[2i])| = 2K ここで、K の値は N 以下でなければなりません。たとえば N = 4、K = 1 の場合、出力は「2 1 3 4」になります。この順列に対する式の値は、(|2−1| + |3−4|) + |2−1+3−4| = 2 となり、条件どおり 2K = 2 を満たします。 アルゴリズムの基本的な考え方 発想はとてもシンプルです。まず「1, 2, 3, 4,

正整数 n が与えられたとき、「範囲内のすべての数が合成数であり、かつ範囲の長さがちょうど n となる」ような正整数の範囲を求める問題を考えます。条件を満たす範囲が複数存在する場合は、そのうちのどれか1つを出力すれば構いません。なお、合成数（composite number）とは「1 とその数自身以外に、少なくとも1つの約数を持つ数」のことです。アルゴリズムの考え方範囲の長さが n である以上、先頭の数を a とすると、範囲内の残りの数は a + 1, a + 2, …, a + n − 1 となり、これらがすべて合成数でなければなりません。ここで役立つのが階乗（factorial）の性質です

問題の概要N個の区間が与えられ、それぞれ左端の値Lと右端の値Rを持っているとします。この中から、他のN-1個の区間をすべて完全に包含している区間を見つけ、その0始まりのインデックスを出力してください。そのような区間が存在しない場合は-1を表示します。例えば、L = [2, 4, 3, 1]、R = [4, 6, 7, 9] の場合、出力は3になります。これは、インデックス3にある区間（1〜9）が、他のすべての区間の要素を包含していることを意味します。解法のアプローチすべてのLとRの値が互いに異なるという前提を利用します。まず、最も小さいLを持つ区間と、最も大きいRを持つ区間をそれぞれ特定します

括弧を含まない算術式が与えられたとき、その式から得られるすべての可能な結果を求めることを考えます。例として「1+2*3-4」という式を挙げます。この式は、演算を適用する順序によって次のように複数の解釈が可能です。 1+(2*(3-4)) = 1 + (2 × -1) = -1 (1+2)*(3-4) = 3 × -1 = -3 1+((2*3)-4) = 1 + (6 - 4) = 3 ((1+2)*3)-4 = (3 × 3) - 4 = 5 1+(2*3)-4 = 1 + 6 - 4 = 3 このように、同じ式でも演算の順序によって結果が異なります。本記事では、これらすべての結果を列挙

原価（仕入れ値）の求め方 販売価格と、利益または損失の割合（%）が分かっている場合、次の公式を使って商品の原価（仕入れ値）を逆算することができます。 利益が出ている場合の計算式 原価 = 販売価格 × 100 ÷（100 ＋ 利益率） 損失が出ている場合の計算式 原価 = 販売価格 × 100 ÷（100 − 損失率） C++での実装例 #include<iostream> using namespace std; // 利益率から原価を計算する関数 float priceWhenProfit(int sellPrice, int profit) { return (s

問題の概要ソート済みの配列（要素数 n）が与えられたとき、「その要素より小さい要素の数」と「その要素より大きい要素の数」が等しくなる要素（イコールポイント）が配列内に存在するかどうかを調べる問題を考えます。イコールポイントが複数存在する場合は、最初に出現するインデックスを返し、該当する要素が存在しない場合は -1 を返します。例えば、配列 A = [1, 1, 2, 3, 3, 3, 3, 3] の場合、イコールポイントはインデックス 2 の要素 A[2] = 2 です。この要素より小さい要素は「1」のみ（1個）、大きい要素は「3」のみ（1個）で、その数が等しいためです。アルゴリズムの考え方こ

2つの二分木が与えられたとき、両方の木を前順(先行順)で走査した際に最初に一致しない葉ノードを見つける問題を考えます。すべての葉が一致している場合は、何も出力しません。問題の例次のような2つの二分木があるとします。この場合、前順走査の順序で葉を比較していくと、最初に一致しない葉は 11 と 15 になります。アルゴリズムの考え方この問題は、スタックを用いた反復的な前順走査(preorder traversal)を2つの木に対して同時に実行することで解けます。ポイントは以下の通りです。木ごとに独立したスタックを用意するスタックの先頭が葉ノードになるまで、子ノードをプッシュし続ける両スタックの先頭

x軸上にn個の点があり、点同士の間で許可された遷移（移動）のリストが与えられているとします。この遷移のみを使って、開始地点から最終地点に到達できるかどうかを判定するのが本記事のテーマです。例えば、点x1と点x2の間に遷移が存在する場合、点xからx1とx2の間の任意の中間点へ移動することも、直接x2へ移動することもできます。問題の例n = 5、遷移が「0から2」「2から4」「3から5」の3つである場合を考えてみましょう。このとき、出力は「YES」になります。なぜなら、0→2→3→5 という経路が存在するからです。アルゴリズムの考え方この問題を解くための手順は以下の通りです。ペアのリストを、各ペア

N個の要素からなる配列を考えます。各要素は0または1のいずれかです。この中から1つの0を1に置き換えることで、最も長い連続した1のシーケンスを得られる位置を見つけるのが本記事のテーマです。例えば、配列が arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] の場合、答えとなるインデックスは9です。インデックス9の0を1に置き換えることで、最大の連続する1のシーケンスが実現します。アルゴリズムの考え方この問題を効率的に解くには、次の3つのインデックスを追跡する必要があります。現在のインデックス(curr)直前の0のインデックス(pz)前々回の0のインデックス

問題の概要 ある数 n が与えられたとき、n 以下の最大の「特殊素数」を求めることを考えます。特殊素数とは、桁を一つずつ付け加えて構成したとき、その過程で現れるすべての数（先頭からの接頭辞）が素数となる数のことです。 たとえば 379 は、3・37・379 のいずれも素数であるため特殊素数です。一方、途中の数に素数でないものが含まれる数は、特殊素数とはみなされません。 アルゴリズムの考え方 ここではエラトステネスの篩（ふるい）を使用します。まず n までの素数表（篩配列）を作成し、その後、N から順に数を減らしながら以下の手順で判定を行います。 その数が素数かどうかを確認する 素数であれば

問題の概要2つの文字列XとYが与えられたとき、Xの部分列のうち、Yの部分文字列（連続する一部分）として現れるものの中で最も長いものの長さを求めます。例えば、X = ABCD、Y = BACDBDCD の場合、出力は 3 になります。これは「ACD」がXの部分列であり、同時にYの部分文字列でもある最長の文字列だからです。動的計画法によるアプローチこの問題は動的計画法（DP）を使うことで効率的に解けます。Xの長さをn、Yの長さをmとすると、(m+1)×(n+1) のサイズのDPテーブルを作成します。DP[i][j] は「X[0…j] の部分列のうち、Y[0…i] の部分文字列となっているものの最大

C++における文字列比較の基本C++では、標準ライブラリに用意されている std::string クラスを使うことで、文字列を簡単に扱うことができます。文字列同士を比較する際には、compare() 関数が便利です。この関数は、2つの文字列の文字を先頭から1文字ずつ順番に照合し、不一致があれば非ゼロの値を返します。戻り値の意味は以下のとおりです。0：2つの文字列が完全に一致している正の値：呼び出し元の文字列（s1）が引数の文字列（s2）より辞書順で大きい負の値：呼び出し元の文字列（s1）が引数の文字列（s2）より辞書順で小さいなお、比較では大文字と小文字が区別される点に注意してください。例えば

異なる文字が格納された行列（マトリックス）が与えられます。ある文字を起点として、現在の文字より1つ大きい連続した文字（例：a→b→c→d）をたどりながら、最長のパスの長さを見つけることが課題です。移動は、縦・横・斜めを含む8方向の隣接セルに対して可能です。 例えば、下図のような行列が与えられ、開始文字を「E」とします。 この行列で開始文字「e」から探索すると、最長の連続パスの長さは5となります。 アルゴリズムの考え方 最長パスを見つけるには、深さ優先探索（DFS）アルゴリズムを使用します。DFSの実行中には、同じ部分問題が何度も発生することがあります。このような部分問題を繰り返し計算しないよ

本記事では、競技プログラミングで活躍するC++の実用的なテクニックを多数紹介します。これらを覚えておくと、コードを書く時間を大幅に短縮でき、コンテスト中の貴重な時間を問題の考察に充てられるようになります。それでは、一つずつ見ていきましょう。 1. %演算子を使わずに奇数・偶数を判定する 数値と1のビットANDを取るだけで判定できます。結果が0以外なら奇数、0なら偶数です。すべての奇数は最下位ビット（LSb）が1になっているため、AND演算で他のビットがマスクされ、簡単に判定できるという仕組みです。 if ((n & 1) != 0) { // 奇数 } else {

この記事では、C++で複素数を作成・利用する方法を解説します。C++では、複素数の実部（real）と虚部（imaginary）をメンバ変数として持つ独自の複素数クラスを定義できます。さらに、クラスを操作するためのメンバ関数を複数用意することで、複素数の入力・表示・演算を自在に扱えるようになります。ここでは、複素数型のクラスを1つ作成し、複素数を正しい形式で表示する関数や、2つの複素数を加算・減算するメソッドなどを実装したサンプルを紹介します。複素数クラスの実装例#include<iostream> using namespace std; class complex{ in

問題の概要スタック内の最大要素を常に把握できるスタックを実装したいとします。最大値の取得はO(1)時間で行える必要があり、さらに制約として、追加で使用できる記憶領域もO(1)に限定されます。つまり、最大値専用のもう一つのスタックや配列を用意するような、O(n)の追加メモリを消費する手法は使えません。アルゴリズムの考え方ユーザー定義のスタッククラスを作成し、現在の最大値をメンバ変数として保持します。新しい最大値が挿入される際には、スタック本体には変換後の値を格納することで、追加メモリなしで最大値を復元できるようにします。各操作は次のように動作します。peek操作： 先頭要素が現在の最大値より大き

はじめにC++の標準テンプレートライブラリ（STL）に含まれるsort()関数を使うと、配列を簡単に昇順に並べ替えることができます。この記事では、sort()関数の基本的な使い方をサンプルコードとともに解説します。例えば、配列 A = [52, 14, 85, 63, 99, 54, 21] を並べ替えると、出力は [14, 21, 52, 54, 63, 85, 99] となります。sort()関数とはsort()関数は、<algorithm>ヘッダーファイルで定義されている標準関数です。第1引数に並べ替え範囲の先頭を指すイテレータ（またはポインタ）、第2引数に範囲の末尾を指すイ