C++

ある配列が昇順にソートされているとします。しかし、この配列は私たちには未知のピボット（基準点）を軸に回転されています。このような回転ソート配列の中から最小値を見つける必要があります。例えば、配列が [3,4,5,1,2] の場合、出力は 1 となります。 解決のためのアプローチ：二分探索 この問題は二分探索（バイナリサーチ）を応用することで効率的に解けます。単純な線形探索では O(n) の計算量がかかりますが、回転ソート配列では必ずどちらか片側の半分がソート済みになっているという性質を利用すると、計算量を O(log n) まで抑えられます。 アルゴリズムの手順 low := 0、hig

問題概要この問題では、1018以下の整数 N が与えられ、その素因数とそれぞれの出現回数（指数）をすべて出力することが求められます。具体例を見てみましょう。入力：100 出力：2 2 　　　5 2 説明：100 の素因数分解は 100 = 2 × 2 × 5 × 5 となります。解き方のアプローチこの問題を解くには、まず対象の数の素因数をすべて求め、その後それぞれの素因数が出現する回数を数える必要があります。手順は以下の通りです。まず、2 が因数として何回含まれるかを確認し、割り切れる限り数を 2 で割り続けます。次に、3 から √n までの奇数を順に調べ、その数の因数となる素数が見つかるたび

素因数とは、ある数の約数の中で素数であるものを指します。約数とは、掛け合わせるとその数になる整数のことです。素因数分解とは、対象の数を素因数で再帰的に割り算を繰り返し、その数のすべての素因数を求めるプロセスのことです。例:N = 120素因数 = 2, 3, 5素因数分解: 2 × 2 × 2 × 3 × 5素因数に関するポイントある数の素因数の集合は常に一意に定まります。素因数分解は、約数の判定や最小公倍数・最大公約数の計算など、多くの数学的計算において重要な役割を果たします。暗号技術(RSA暗号など)の基礎となる重要な概念でもあります。C++で素因数を求めるプログラム以下のプログラムは、試

問題の概要この問題では、ある数値 N が与えられ、その数値の奇数番目の桁（下から1桁目・3桁目・5桁目…）の合計が素数であるかどうかを判定します。ここでいう素数判定（素数性テスト）とは、与えられた数が素数かどうかを効率的に確認するためのアルゴリズムのことです。具体例で理解しようまず、例を見て問題の内容を確認しましょう。入力：3425出力：No説明：奇数番目の桁の合計 = 5 + 4 = 9。9は素数ではないため「No」。この例では、3425 の下から数えて1桁目の「5」と3桁目の「4」を足すと 9 になります。9 は 3×3 と表せるため素数ではなく、答えは「No」となります。解法のアプローチ

この記事では、与えられた数値Nが素数であるかどうかを判定する方法について解説します。 素数判定（Primality Test）とは、与えられた数が素数かどうかを調べるために用いられるアルゴリズムのことです。 素数とは、1とその数自身でしか割り切れない数のことです。例：2、3、5、7。 問題の例 入力：11 出力：Yes（素数である） 基本的な素数判定方法（試し割り法） 素数判定には複数の手法があります。 最もシンプルな方法は、Nより小さいすべての数で割り切れるかを確認することです。1つでもNを割り切る数が存在すれば、Nは素数ではありません。 具体的には、i = 2 から n-1 までのすべて

プリム法（Prims Algorithm）は、与えられた重み付き無向グラフから最小全域木（Minimum Spanning Tree）を求めるための貪欲法（グリーディ法）ベースのアルゴリズムです。 基本用語のおさらい 重み付きグラフ（Weighted Graph）とは、すべての辺に重み（コストや距離などの数値）が割り当てられているグラフのことです。 無向グラフ（Undirected Graph）とは、すべての辺が双方向につながっているタイプのグラフです。ある頂点から別の頂点へ移動できる場合、その逆方向にも必ず移動できます。 最小全域木（Minimum Spanning Tree）とは、元のグラ

問題の概要この問題では、整数 n が与えられます。求められているのは、n の2進数表現における「セットビット（1になっているビット）」を1つだけ変更することで作れる数のうち、n より小さい最大の整数を出力することです。具体例を見てみましょう。入力: n = 3 出力: 2 解説: (3)10 = (011)2 セットビットを1つ反転すると、001 と 010 が得られます。このうち大きいのは 010、すなわち 2 です。解き方のアプローチこの問題を解く鍵は、「最も右側にあるセットビット」に注目することです。n より小さくなるようにビットを1つだけ変更するなら、最下位のセットビットを0に反転する

整数 n が与えられたとき、n の直前の数（n − 1）がn の1の補数と一致しているかどうかを判定するのが、この問題の目的です。 具体例で問題を理解する 入力: 12 出力: No 解説: (12)10 = (1100)2 直前の数 11 = (1011)2 12 の1の補数 = (0011)2 入力: 4 出力: Yes 解説: 4 = (100)2 直前の数 3 = (011)2 4 の1の補数 = (011)2 単純なアプローチ 最も素直な方法は、n − 1 を計算し、n の各ビットを反転して得られる1の補数と直接比較することです。し

問題の概要この問題では、整数の配列が与えられます。配列の各要素について、その要素より前方(左側)に位置する要素の中で最大の値を見つけて出力します。該当する要素が存在しない場合は -1 を出力します。入出力例入力: {6, 2, 7, 1, 5, 3} 出力: -1, 6, -1, 7, 7, 7この例では、最初の要素「6」の前方には要素が存在しないため -1。2番目の要素「2」の前方にあるのは「6」だけなので 6。3番目の要素「7」の前方に「7」より大きい要素はないため -1。4番目の要素「1」の前方には「7」があるので 7。以降も同様に判定していきます。解法1: 二重ループによる単純なアプロ

はじめに本記事では、N分木(N-ary Tree)が与えられたときに、その先行順走査(プレオーダートラバーサル)の結果を出力する問題を扱います。ポイントは、再帰呼び出しを使わずにスタックだけで実装するところです。基本用語の確認N分木(N-ary Tree)とは、すべてのノードが最大N個の子ノードを持つことができる木構造のことです。たとえば2分木(バイナリツリー)は、各ノードが最大2つの子ノードを持ちます。先行順走査(Preorder Traversal)は、木のノードを巡回する方法の1つで、まずルートノードを訪問し、その後、子ノードを左から順に訪問していきます。問題例次のようなN分木を考えてみ

この問題では、二分木とあるノードの値が与えられ、そのノードの前順走査(プレオーダー)における後続ノードを出力することが求められます。基本用語の整理二分木(Binary Tree):各ノードが最大2つの子ノードを持つことができる特別な木構造です。前順走査(Preorder Traversal):木のノードを巡回する方法の1つで、「根ノード → 左の子 → 右の子」の順に訪問します。前順走査における後続ノード:前順走査の順序において、対象ノードの直後に現れるノードのことです。問題例具体例を見て、問題を理解しましょう。入力: 9 出力: 0 説明: この木の前順走査は「5 9 0 1 2 5」の順に

問題の概要 この問題では、二分木とあるノードの値が与えられ、そのノードの前順走査における先行ノード（Preorder Predecessor）を出力することが求められます。 用語の整理 二分木（Binary Tree）とは、各ノードが最大2つの子ノードを持つことができる特殊な木構造のことです。 前順走査（Preorder Traversal）は、木のノードを巡回する方法の一つで、「根ノード → 左の子 → 右の子」の順に訪問していきます。 前順先行ノードとは、前順走査において対象ノードの直前に訪問されるノードのことを指します。 具体例 次の例で問題を確認してみましょう。 入力: 1 出力:

問題の概要この問題では、ある二分木の中順走査(通りがけ順)と後順走査(帰りがけ順)の結果が与えられます。目的は、これらの情報をもとに木を実際に構築することなく、前順走査(行きがけ順)の結果を求めて出力することです。問題例入力: 中順走査: 16 7 21 12 1 5 9 後順走査: 16 21 7 1 9 5 12 出力: 前順走査: 12 7 16 21 5 1 9この入力から復元される二分木は次のような構造になります。 12 / \ 7 5 / \ / \ 16 21 1 9単純なアプローチ

この問題では、文字 a と b のみで構成された文字列 str と整数 N が与えられます。str を N 回繰り返して連結することで新しい文字列を作成し、その中に含まれる「a の出現回数が b より多い」部分文字列の総数を求めて出力するのが課題です。 問題の例 まず、具体的な例で問題を確認してみましょう。 入力: aab 2 出力: 9 説明: 作成された文字列は aabaab。 条件を満たす部分文字列: a, aa, aab, aaba, aabaa, aabaab, aba, baa, abaa 解法のアプローチ この問題を解くには、毎回完全な文字列を生成するのではなく、元の文字列 st

この問題では、前置記法（プレフィックス）で表された式が与えられ、それを後置記法（ポストフィックス）に変換して出力することが求められます。 前置記法と後置記法とは 前置記法（プレフィックス記法）は、演算子がオペランド（被演算子）の前に置かれる表記方法です。 例：+AB 後置記法（ポストフィックス記法）は、演算子がオペランドの後に置かれる表記方法です。 例：AB+ なお、この変換処理では、中置記法（インフィックス）を経由せずに、直接前置記法から後置記法へ変換する必要があります。 問題例 具体的な例を見てみましょう。 入力：/+XY+NM 出力：XY+NM+/ 説明：中置記法に直すと (X+Y)/(

この問題では、前置記法（プレフィックス表記）で書かれた式が与えられ、それを中置記法（インフィックス表記）に変換して出力することが求められます。前置記法と中置記法とは前置記法（プレフィックス表記）とは、演算子がオペランド（被演算子）の前に置かれる記法のことです。例：+AB一方、中置記法（インフィックス表記）は、演算子がオペランドとオペランドの間に置かれる、私たちが普段目にする一般的な数式の書き方です。例：A+B中置記法は人間にとって理解しやすい形式ですが、コンピュータは計算を行う際に前置記法や後置記法（ポストフィックス表記）を利用します。特に後置記法はスタックベースの評価に適しており、多くの処理

この記事では、整数値を格納した2次元配列 mat[][] が与えられたとき、その累積和行列（プレフィックスサム行列）を求める問題について解説します。 累積和行列とは？ 累積和行列とは、行列の各要素が「その位置より上側と左側にあるすべての要素の合計」を表す行列のことです。数式で表すと以下のようになります。 prefixSum[i][j] = mat[i][j] + mat[i-1][j] + ... + mat[0][j] + mat[i][j-1] + ... + mat[i][0] つまり、(i, j) の値は、左上の要素 (0, 0) から (i, j) までの長方形領域内の全要素の総和に

この問題では、n個の整数からなる配列が与えられ、プレイヤーXとプレイヤーYの2人がその数字を使ってゲームを行います。私たちのタスクは、どちらのプレイヤーが勝つかを事前に予測することです。 勝敗を決めるルールはシンプルです。プレイヤーXが選んだ数字の合計と、プレイヤーYが選んだ数字の合計の絶対差が4の倍数であればXの勝ち、4で割り切れない場合はYの勝ちとなります。なお、ゲームは必ずプレイヤーXから開始されます。 問題の具体例 まず、入力例と出力例を見ながら問題を理解しましょう。 入力：a[] = {3, 6, 9, 12} 出力：X 解説： Xは 3 と 6 を選択（合計 9） Yは 12

問題概要このゲームには2人のプレイヤーXとYが登場します。両者が最適な戦略でプレイし、Xが先手である場合、どちらが勝利するかを予測するのが私たちのタスクです。ゲームのルールコインゲームでは、それぞれN枚とM枚のコインが入った2つの山が用意されています。プレイヤーの一方がゲームに使う山を1つ選び、選んだ山を半分ずつに分割していきます。これを、どちらかのプレイヤーがそれ以上分割できなくなるまで繰り返します。具体例問題を理解するために、具体例を見てみましょう。Input: M = 2 , N = 2 Output: X解説 − Xが先手でMの山を選び(どちらの山も同じ枚数)、山を2つに分割します。す

浮動小数点数の精度とは、小数点以下の値をどこまで正確に保持できるかを表す尺度です。たとえば、10 ÷ 6 = 1.6666666… のように循環小数となる計算結果は、厳密に保存しようとすると無限のメモリが必要になります。そこで、メモリのオーバーフローを防ぐために、コンパイラ側で精度の上限が設定されています。C++のfloat型の場合、この精度は小数点以下6〜7桁程度であり、それ以降の桁が循環する場合は値が破棄されます。この切り捨てによって大きな誤差が生じるのを避けるため、C++には浮動小数点数の丸めや精度指定を行うための関数やライブラリが用意されています。本記事では、代表的なものとして flo