C++

開始時刻と終了時刻が与えられた n 個の異なる活動の中から、一人の人物が時間の重複なく実行できる活動の最大数を選ぶ問題を「活動選択問題（Activity Selection Problem）」と呼びます。本記事では、貪欲法（グリーディ法）を用いてこの問題を解く方法を解説します。貪欲法では、残りの活動の中から「終了時刻が最も早い活動」を順に選んでいきます。ただし、その活動の開始時刻は、直前に選択した活動の終了時刻以降である必要があります。計算量：活動リストが未ソートの場合は O(n log n)、すでに終了時刻でソートされたリストが与えられている場合は O(n) で解けます。活動選択問題の入力と

アダム数（Adam Number）とは？本記事では、与えられた整数がアダム数（Adam Number）であるかどうかを判定するC++プログラムの作成方法を解説します。まずは、アダム数とはどのような数なのかを確認しておきましょう。アダム数とは、ある数 n の2乗と、n の各桁を逆順に並べ替えた数の2乗が、互いに逆順の関係になっている数のことです。具体例として「13」を見てみます。13を逆順にすると「31」になります。・13 × 13 = 169・31 × 31 = 961169 と 961 は互いに逆順の関係にあるため、13 はアダム数であると言えます。アダム数の判定手順与えられた数がアダム数か

ある数値が格納された配列があるとします。この配列の要素の合計を偶数にするために、最小でいくつの数を追加する必要があるかを求めるのが本記事の目的です。ただし、追加する数は0より大きい正の整数でなければなりません。ルールはシンプルです。要素の合計が奇数の場合は1を追加すれば偶数になります。一方、合計がすでに偶数である場合は、0を追加することが許されていないため、最小の正の偶数である2を追加することになります。アルゴリズムaddMinNumber(arr)begin s := 0 for each element e from arr, do s := e + s

本記事では、文字列として与えられたn個の2進数（バイナリ）を加算するC++プログラムの実装方法を解説します。最も簡単なアプローチは、各2進数文字列を10進数に変換して合計し、その結果を再び2進数に戻す方法です。しかし、ここでは変換を介さず、桁ごとの演算を手動で行うことで直接加算を実現する方法を紹介します。まず、2つの2進数文字列を加算するための補助関数を用意します。この関数をn個の2進数に対してn-1回繰り返し呼び出すことで、すべての値の合計を求めることができます。関数の動作は以下の通りです。アルゴリズムaddTwoBinary(bin1, bin2)begin s := 0

問題の概要 本記事では、数値AにN桁を追加して新しい数値を作成する方法を解説します。ただし、各段階で桁を追加した直後に、その数値が別の数値Bで割り切れるという条件を満たす必要があります。 具体例として、「8」から始まる5桁の数を作り、4桁を追加しながら7での割り切りを確認するケースを考えてみましょう。最初に8に4を付け足すと「84」となり、これは7で割り切れます。その後は0を追加しても「840」「8400」「84000」と、いずれも7で割り切れたままです。もし条件を満たす数値が生成できない場合は、-1を返します。 アルゴリズムの考え方 基本的な戦略はシンプルです。各ステップで0から9までの数

この記事では、2つの数に共通する約数（公約数）がいくつあるかを数える方法を解説します。すべての公約数を実際に列挙するのではなく、その「個数」だけを効率的に求めることが目的です。例えば、12と24という2つの数を考えてみましょう。12と24の公約数は、1、2、3、4、6、12の6つです。したがって、答えは6となります。アルゴリズムの考え方すべての公約数を1つずつ調べるのは非効率です。ここで重要なのが、「2つの数aとbの公約数は、必ずgcd(a, b)（最大公約数）の約数になる」という性質です。つまり、gcd(a, b)の約数の個数を数えれば、それがそのまま公約数の個数になります。さらに、約数の個

本記事では、3つ以上の数値の最大公約数（GCD）をC++で求める方法を解説します。2つの数値のGCDを求めるのは簡単ですが、3つ以上の数値を扱う場合はGCDの結合法則を利用します。例えば、{w, x, y, z} のGCDを求めたい場合、以下のように段階的に計算します。まず {gcd(w, x), y, z} を計算次に {gcd(gcd(w, x), y), z) を計算最後に {gcd(gcd(gcd(w, x), y), z)} を計算この手法を配列に適用すれば、任意の個数の数値に対してGCDを簡単に求めることができます。アルゴリズムgcd(a, b)begin    

この問題では、Xで割り切れる最小のK桁の数を求めます。まず、数式 10(k-1) を使ってK桁の最小の数を求め、その数がXで割り切れるかどうかを確認します。割り切れない場合は、次の数式を使って正確な答えを導き出します。(min + X) − ((min + X) mod X)具体例として、「29で割り切れる5桁の数」を求めてみましょう。5桁の最小の数は10000ですが、これは29で割り切れません。そこで上記の数式を適用すると、次のようになります。(10000 + 29) − ((10000 + 29) mod 29) = 10029 − 24 = 10005求められた数10005は、実際に29

覆面算（暗号算術）パズルとは？ 覆面算（Crypt-Arithmetic Problem）とは、単語を構成する各アルファベットに0〜9の数字を割り当て、算式が正しく成立するようにするパズルです。異なる文字には必ず異なる数字が対応し、10進法の数字は0〜9の10種類しかないため、使用できる文字は最大10種類という制約があります。 典型的な例として、「BASE」と「BALL」という2つの単語が与えられ、その足し算の答えとして「GAMES」が与えられるケースがあります。各文字に適切な数字を割り当てれば、BASE＋BALL＝GAMES という等式が実際に成立します。 入力と出力 入力 このアルゴリズ

はじめにこの記事では、最初のn個の自然数（1からnまで）の二乗和を求める方法について解説します。例えば、n = 4 の場合、計算結果は 1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30 となります。基本的なアプローチとしては、1からnまで繰り返すforループを使用し、各ステップで項の二乗を計算して合計に加算していく方法があります。このプログラムの計算量は O(n) です。しかし、O(1) の定数時間で解きたい場合は、次の級数の公式を利用できます。Σk² = n(n + 1)(2n + 1) / 6この公式を使えば、ループ処理を行わずに一発で答えを求めることが可能で

この記事では、文字列をn回繰り返し連結して出力するC++プログラムの作成方法を解説します。連結回数nはユーザーからの入力として受け取ります。C++では+演算子や+=演算子を使うことで、std::string型の文字列を非常に簡単に連結できます。考え方はシンプルで、空の結果用文字列を用意し、ループで入力された文字列をn回追加していくだけです。それでは、実際のコードを見ていきましょう。アルゴリズムconcatStrNTimes(str, n)begin     res := 空の文字列     i を 1 から n ま

文字列から母音（a、e、i、o、u）を取り出して数えるには、文字列内の各文字を順番に調べていく必要があります。ここでは、ポインタを使って文字列を先頭から末尾まで移動しながら処理を行う方法を紹介します。そのためには、C言語形式の文字列（Cスタイル文字列）を使用します。文字列がポインタ str によって指されている場合、最初は *str が1文字目を保持しています。ポインタ str をインクリメントすると、*str は次の文字を指すようになり、これを繰り返すことで文字列全体を走査できます。各文字が [a, e, i, o, u] または大文字の [A, E, I, O, U] のいずれかに該当すれ

本記事では、級数 1/1! + 2/2! + 3/3! + 4/4! + …… + n/n! の総和を求めるC++プログラムを紹介します。項数 n はユーザーからの入力として受け取ります。この問題は、階乗を計算する関数を作成し、ループの各ステップで階乗を求めるという素朴な方法でも解くことができます。しかし、階乗の計算は単純な加算に比べて処理コストが高い操作です。そこで本記事では、前回計算した階乗の値を次のステップで再利用する効率的なアプローチを取り上げます。例えば、3! = 3 × 2 × 1 であり、4! = 4 × 3! です。つまり、3! を変数に保存しておけば、それに 4 を掛けるだけ

この記事では、C++を使用してテキストファイルの内容を単語ごとに読み込む方法を解説します。実装は非常にシンプルで、ファイル入力ストリーム（fstream）を使うだけで実現できます。基本的な流れは以下のとおりです。まず、ファイル名を指定してファイルストリームでファイルを開きます。次に、抽出演算子（>>）を使って単語を1つずつ読み取り、wordという文字列変数に格納します。最後に、読み取った単語を順番にコンソールへ出力していきます。C++の>>演算子は、デフォルトで空白文字（スペース・改行・タブなど）を区切りとして自動的に分割してくれるため、特別な文字列処理を書かなくても単

はじめに本記事では、競技プログラミングで役立つC++の便利なテクニックを多数紹介します。これらをマスターすれば、コードを書く時間を大幅に短縮でき、実装の効率も向上します。それでは、一つずつ見ていきましょう。1. %演算子を使わずに奇数・偶数を判定する数値と1のビットAND演算を行うだけで判定できます。結果が0でなければ奇数、0なら偶数です。すべての奇数は最下位ビット（LSb）が1になっているため、AND演算によって他のビットがマスクされ、簡単に判定できます。if ((n & 1) != 0) { // 奇数 } else { // 偶数 }2. シフト演算子による高速な

本記事では、アリコート和（Aliquot Sum）とは何かを解説します。アリコート和とは、ある数 n の約数のうち、n 自身を除いたすべての約数の総和のことです。例えば、数値が 20 の場合、その約数は (1, 2, 4, 5, 10) となるため、アリコート和は 22 になります。興味深い点として、アリコート和がその数自身と等しくなる場合、その数は「完全数」と呼ばれます。例えば 6 の場合、約数は (1, 2, 3) であり、アリコート和は 1 + 2 + 3 = 6 となるため、6 は完全数です。それでは、以下のアルゴリズムを使ってアリコート和を求める方法を見ていきましょう。アルゴリズムg

本記事では、C++を使ってNまでの交互素数（1つおきの素数）をすべて出力する方法を解説します。交互素数とは、Nまでの素数を小さい順に並べたとき、1つ飛ばしで選んだ素数のことです。例えば N = 15 の場合を考えてみましょう。15までの素数は {2, 3, 5, 7, 11, 13} であり、これらから1つおきに選ぶと、交互素数は {2, 5, 11} となります。それでは、この問題をどのように解けばよいのか見ていきましょう。アルゴリズムの考え方まずエラトステネスの篩を用いてNまでの素数をすべて求めます。その後、ブール型のフラグ変数を使って素数を走査し、フラグが立っているときだけ出力することで

算術平均とは、いわゆる「数値の平均」のことです。本記事では、C++を使って複数の数値から算術平均を求める方法を解説します。ここで作成する関数は、数値の集合（配列）とその要素数を受け取ります。処理内容はシンプルで、各要素をすべて足し合わせ、最後に要素数で割るだけです。算術平均の基本式算術平均は次の式で表されます。算術平均 = （全要素の合計） ÷ （要素数）アルゴリズムarithmeticMean(dataset, n)まず、処理の手順を擬似コードで確認しましょう。begin    sum := 0    for each element e from d

本記事では、C++において複素数に対してasin()関数を使用する方法を解説します。C++では、<complex>ヘッダーファイルをインクルードすることで複素数を扱うことができます。実は、このヘッダーファイルには複素数専用のasin()関数も用意されています。これは通常のasin()関数の複素数版であり、複素数の逆正弦（アークサイン）を求めるために使用されます。関数の基本仕様複素数版のasin()関数は、入力パラメータとして複素数を受け取り、その逆正弦（アークサイン）の計算結果を複素数として返します。戻り値もまた複素数となる点に注意してください。サンプルコード以下の例を見て、具体的

本記事では、C++で複素数に対してatan()関数を使用する方法を解説します。C++では、<complex>ヘッダファイルをインクルードすることで複素数を扱うことができます。このヘッダファイルには、通常のatan()関数の複素数版であるatan()関数も用意されており、複素数の逆正接（アークタンジェント）を求めるために使用されます。 この関数は複素数を入力パラメータとして受け取り、その逆正接の結果を複素数として返します。具体的な動作を理解するために、以下のサンプルコードを見てみましょう。 サンプルコード #include<iostream> #include<co