C++

はじめにこのチュートリアルでは、ラグランジュの四平方定理について解説します。ラグランジュの四平方定理とは、「すべての自然数は、高々4つの非負整数の平方の和で表すことができる」という有名な定理です。例えば、7 = 1×1 + 1×1 + 1×1 + 2×2 のように表せます。以下のコードでは、与えられた数 n に対して、この定理を満たす4つの数の組み合わせをすべて求めます。コード例それでは、実際のコードを見てみましょう。#include <bits/stdc++.h>using namespace std;void printSquareCombinations(int n) {&n

ラグランジュ補間とは、既知の複数のデータ点をすべて通る多項式を求めるための補間手法の一つです。このチュートリアルでは、ラグランジュの補間公式を使って、任意の点における値を計算するC++プログラムを作成します。 複雑なロジックを考える必要はありません。公式をそのままコードに変換するだけで実装できます。それでは、コードを見ていきましょう。 ラグランジュ補間の公式 n個のデータ点 (x₀, y₀), (x₁, y₁), …, (xₙ₋₁, yₙ₋₁) が与えられたとき、点 x における y の値は次の公式で求められます。 P(x) = Σᵢ [ yᵢ × Πⱼ≠ᵢ ( (x − xⱼ) / (xᵢ

このチュートリアルでは、C++を使って ab と ba のうち、どちらの値が大きいかを判定するプログラムを作成します。指数の値をそのまま計算すると桁数が膨大になり、オーバーフローのリスクがあります。そこで対数（log）を活用することで、安全かつ効率的に大小を比較できます。それでは、具体的な手順を見ていきましょう。解決の手順変数 a と b の値を初期化します。両辺の対数を取ります。b × log a と a × log b をそれぞれ計算します。計算した2つの値を比較します。a × log b の方が大きければ、「ba の方が大きい」と出力します。b × log a の方が大きければ、「ab

このチュートリアルでは、C++を使ってN桁の数値の中から最大の偶数と奇数を求めるプログラムを作成します。一見複雑に思える問題ですが、実は非常にシンプルな数学的な性質を利用することで、効率的に解くことができます。解法の考え方N桁の最大の数は、すべての桁が9で埋められた数値です。この性質を利用すると、以下の手順で偶数と奇数をそれぞれ求められます。桁数 n を初期化します。最大の奇数は pow(10, n) - 1 で求められます（例：n=3なら999）。最大の偶数は、その奇数から1を引いた値、つまり odd - 1 になります（例：n=3なら998）。すべての桁が9の数値は必ず奇数になるため、そこ

はじめに このチュートリアルでは、与えられた整数 n 以下の数のうち、すべての桁が偶数である最大の数を求めるプログラムをC++で作成します。例えば n = 43 の場合、「3」という奇数の桁を含むため条件を満たさず、答えは 42 となります。 解法のアプローチ もっともシンプルな方法は、n から順に数を減らしながら各桁を調べていく力まかせ（ブルートフォース）な探索です。手順は以下の通りです。 整数 n を初期化します。 i = n からループを開始します。 現在の数 i の各桁がすべて偶数かどうかを判定します。 条件を満たす場合は、その数を返して終了します。 満たさない場合は、i を1減ら

このチュートリアルでは、与えられた数字の桁をたった1回入れ替える（スワップする）だけで作れる最大の偶数を求めるプログラムを、C++で作成していきます。 数値が偶数かどうかは最後の桁で決まるため、「最後の桁」と「それ以外の位置にある偶数の桁」を入れ替えるのが基本の考え方です。それでは、具体的な手順を見ていきましょう。 アルゴリズムの手順 対象となる数字を文字列形式で用意します。 先頭の桁から順に走査し、最後の桁の値以下となる偶数の桁を探します。 条件を満たす偶数の桁が見つかった時点で、走査を終了します。 偶数の桁が1つも存在しない場合は、入れ替えができないため元の数字をそのまま返します。 見つ

このチュートリアルでは、与えられた配列の中から2つの要素間の最大の差（最大ギャップ）を求めるプログラムをC++で作成します。アプローチは非常にシンプルで、配列内の最大値と最小値を見つけ、その差を計算するだけです。 解決の手順 配列を初期化します。 配列内の最大値と最小値を見つけます。 「最大値 − 最小値」を計算して返します。 サンプルコード それでは、実際のコードを見てみましょう。 #include <bits/stdc++.h> using namespace std; int findLargestGap(int arr[], int n) { int m

このチュートリアルでは、x で割り切れる最大の k 桁の数を求めるプログラムを C++ で実装する方法を解説します。 解き方の手順 この問題は、以下のシンプルな手順で解くことができます。 変数 x(割る数)と k(桁数)を初期化します。 pow(10, k) - 1 を計算します。これは k 桁で表せる最大の数です(例:k = 3 なら 999)。 上記の値から x で割った余りを引きます。そうすることで、x で割り切れる最大の k 桁の数が求められます。 コード例 実際のコードを見てみましょう。 #include <bits/stdc++.h> using namespace

はじめにこのチュートリアルでは、指定された3つの数値すべてで割り切れる、N桁の最大の数を求めるプログラムをC++で作成します。一見すると総当たりで調べたくなりますが、最小公倍数(LCM)を利用することで、効率的に答えを導き出せます。その考え方と実装方法を順番に見ていきましょう。解決手順問題を解くための手順は以下の通りです。3つの数値と桁数nを初期化します。3つの数値の最小公倍数(LCM)を求めます。N桁の最大の数(999...9)を求めて保存します。その最大の数がLCMで割り切れる場合は、そのまま答えとして返します。割り切れない場合は、最大の数から剰余を引いた数を答えとして返します。なぜLCM

このチュートリアルでは、「Nより小さい数のうち、桁の和がNの桁の和よりも大きくなる最大の数」を求めるプログラムをC++で作成します。 問題の例 例えば、N = 75 の場合を考えてみましょう。75の桁の和は 7 + 5 = 12 です。このとき、75未満の数の中で桁の和が12を超える最大の数は 69(6 + 9 = 15)となります。 解決手順 桁の和を求める関数を作成します。 Nを初期化します。 n - 1 から 1 まで順に調べるループを記述します。 現在の数の桁の和とNの桁の和を比較します。 現在の数の桁の和の方が大きければ、その数を返します。 条件を満たさなければ、次の数へ進みま

このチュートリアルでは、与えられた整数 x 以下で、セットビット（2進数表記において1になっているビット）の数が最大 k 個となる最大の数を求めるプログラムをC++で作成します。 問題のポイント セットビットとは、数値を2進数で表したときに値が1となっているビットのことです。例えば、65は2進数で「1000001」と表されるため、セットビットは2個あります。 解き方の手順 整数 x と k を初期化します。 x のセットビットの数を求めます。 セットビット数から k を引いた回数だけループを実行します。 各ループで、x の値を x & (x - 1) で更新します。 最終的な

はじめに このチュートリアルでは、C++を使って「N以下の整数の中で、Kで割り切れる最大の数」を求めるプログラムを作成します。剰余演算子(%)を活用することで、わずか数行のコードで効率よく解くことができる問題です。 解き方の手順 整数 n と k を初期化します。 剰余演算子(%)を使って、n を k で割った余りを求めます。 余りが 0 の場合、n はすでに k で割り切れているため、そのまま n を返します。 余りが 0 以外の場合は、n から余りを引いた値(n − 余り)を返します。 サンプルコード それでは、実際のコードを見てみましょう。 #include <bits/s

このチュートリアルでは、「m個の1」と「m-1個の0」で構成される2進数の中から、与えられた数 n 未満の最大の数を求めるプログラムをC++で作成します。まずは、問題を解決するための手順を見ていきましょう。解法のアプローチ変数 bits を 2、result を 1、i を 1 で初期化します。i が n 未満である間、次の処理を繰り返します。i を (pow(2, bits) - 1) * pow(2, bits - 1) の計算結果で更新します。更新後の i が n 未満であれば、result をその値で上書きします。bits のカウントを1つ増やします。最後に result を返します。

このチュートリアルでは、数字を1回だけ入れ替える（スワップ）ことで作れる最大の数を求めるプログラムをC++で作成します。 アルゴリズムの手順 問題を解くための手順は以下の通りです。 数値nを初期化します。 整数を文字列に変換します。 文字列の末尾から先頭に向かって走査するループを作成します。 それまでに見つかった最大の桁とそのインデックスを記録します。 現在の桁が記録中の最大桁より小さい場合は、開始インデックスを現在のインデックスに、終了インデックスを最大桁のインデックスに更新します。 ループ終了後に開始インデックスが-1のままなら、入れ替えは不要なのでnをそのまま返します。 それ以外

このチュートリアルでは、C++を使って「n以下の数のうち、すべての桁が素数（2・3・5・7）で構成される最大の数」を求めるプログラムを作成します。 一桁の素数は 2、3、5、7 の4つだけです。そのため、答えとなる数はこれらの数字だけで構成されている必要があります。それでは、問題を解くための手順を見ていきましょう。 解法の手順 数値nの各桁を先頭から順に走査するループを作成します。 現在の桁が素数でない場合： その桁が「2」以下である間、インデックスiを1つずつ減らします（桁の繰り下がり処理）。iが負になった場合は0に戻します。 現在のインデックスの値を、元の桁より小さい最大の素数の桁に

このチュートリアルでは、配列内の数字を組み合わせて作ることができる数の中から、2・3・5のすべてで割り切れる最大の数を求めるプログラムをC++で作成します。 まずは、問題を解くための条件と手順を順番に見ていきましょう。 2・3・5の倍数になるための条件 ある整数が2・3・5のすべてで割り切れるためには、次の2つの条件を満たす必要があります。 末尾が0であること：2と5の公倍数は10の倍数なので、数の末尾は必ず0になります。 各桁の合計が3の倍数であること：3の倍数かどうかは、各桁の数字の総和で判定できます。 アルゴリズムの手順 配列を初期化します。 配列に0が含まれているかを確認します。

はじめにこのチュートリアルでは、配列に対して最大k回のスワップ（要素の交換）を行ったときに実現できる最大の順列を求めるプログラムを、C++で作成していきます。この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。左から順に「その位置に置くべき最大の数」を1回のスワップで移動させていく、というのが基本的な考え方です。解き方の手順配列を初期化します。各要素のインデックスを格納するための、サイズ n + 1 の位置情報配列を用意します。配列を走査し、各要素が現在どこにあるのかを位置情報配列に記録します。i が n 未満かつ k が 0 より大きい間、以下の処理を繰り返します。arr[i] が

このチュートリアルでは、与えられた数値 n に対して、ビット単位OR（bitwise OR）の結果が n と等しくなる最大の集合を見つけるプログラムを C++ で作成します。問題の考え方ある整数 i と n のビット単位ORが n と等しくなるためには、i のセットされているビットがすべて n のセットされているビットに含まれている必要があります。つまり、i は n のビットパターンの「部分集合」であればよいことになります。解法の手順数値 n を初期化します。0 から n まで繰り返すループを作成します。もし i | n の結果が n と等しければ、i を結果の集合に追加します。最後に結果を出

このチュートリアルでは、与えられた数値 n より小さくなるように、スワップ（入れ替え）操作を1回だけ行ったときに得られる最大の数を求めるプログラムをC++で作成します。アルゴリズムの考え方問題を解くための手順は以下の通りです。数値 n を文字列として初期化します。文字列の末尾から先頭に向かって走査し、「現在の桁が次の桁より大きい」最初のインデックスを見つけて変数に保存します。そのようなインデックスが見つかった時点でループを抜けます。次に、文字列の末尾から上記のインデックスまでの範囲を走査します。その範囲内で「上記インデックスの桁より小さく、かつ条件を満たす桁の中で最も大きい」桁のインデックスを

このチュートリアルでは、C++を使って「合計（総和）が k より大きい最長の部分配列」を見つけるプログラムを作成します。単純な全探索では O(n²) の計算量が必要ですが、累積和と二分探索を組み合わせることで、O(n log n) まで効率化できます。負の数を含む配列にも対応できるのが特徴です。 解法のアルゴリズム 以下の手順で問題を解いていきます。 配列を初期化します。 配列を先頭から走査し、各インデックスにおける累積和とそのインデックスをペアとして vector に格納します。 格納した累積和を、値とインデックスを基準にソートします。 最小インデックスを保持するための配列を初期化します。