C++

問題概要階乗の値が与えられた整数 x で割り切れる、最初の自然数 N を求めるプログラムを作成します。x の値はユーザーから入力されるものとします。例えば、x = 16 の場合、答えは 6 になります。これは 6! = 720 であり、720 mod 16 = 0 となるためです。つまり、6! は 16 で割り切れる最小の階乗ということになります。解法のアプローチこの問題は、シンプルな反復処理（総当たり）で解くことができます。手順は以下の通りです。1 から順に階乗を計算していきます（1!, 2!, 3!, …）各階乗の値を x で割った余り（剰余）を確認します余りが 0 になった時点で処理を停

二分木と値Kが与えられたとき、垂直順走査(Vertical Order Traversal)におけるK番目のノードを出力するのが課題です。該当するノードが存在しない場合は-1を返します。例として、次のような二分木を考えてみましょう。この二分木を垂直順に走査すると、結果は以下のようになります。4 2 1 5 6 3 8 7 9つまり、K = 3 の場合、答えは 1 となります。アプローチの解説考え方は非常にシンプルです。まず垂直順走査を実行し、走査中の現在のノードがK番目のノードかどうかを順番に確認していきます。K番目に到達した時点で、そのノードの値を返します。垂直順走査では、各ノードに水平距離

問題概要N個の相異なる整数からなる配列が与えられたとします。このとき、与えられたN個の整数のうちちょうど1つだけを含み、かつ 1 ≤ L ≤ R ≤ 105 を満たす区間 [L, R] の中から、最も多くの整数を含む（＝最も長い）区間を見つける必要があります。例として、配列が Arr = [5, 10, 200] の場合を考えてみましょう。このときの出力は 99990 となります。候補となる区間は [1, 9]、[6, 199]、[11, 100000] の3つで、それぞれ 5、10、200 をちょうど1つずつ含みます。この中で最後の区間 [11, 100000] には 99990 個の整数が

2つの正の整数 n と k が与えられたとき、(x % k) × (x / k) が n と等しくなるような正の整数 x を求める必要があります。例えば n = 4、k = 6 の場合、答えは 10 になります。実際に確認すると、(10 % 6) × (10 / 6) = 4 × 1 = 4 となり、条件を満たしています。解法のアプローチここでポイントになるのは、x % k の値が必ず 1 以上 k − 1 以下の範囲に収まるという点です（0 は除外します。x % k が 0 になると積も 0 になり、正の整数 n とは一致しないためです）。そこで、n の約数のうち [1, k − 1] の範

数字の配列が与えられたとき、その配列に含まれるすべての数字を使って作れる最大の数を求める問題を考えてみましょう。 例えば、配列が [3, 3, 9, 6, 2, 5] の場合、これらの数字を組み合わせて作れる最大の数は 965332 になります。 アプローチの考え方 この問題に対する最も直感的な解法は、配列内の数字を降順（非増加順）にソートして、その順に出力することです。ソートを使えば確かに正しい答えが得られますが、計算量は O(n log n) となります。 しかし、より効率的な方法があります。それがカウントソート（頻度カウント）の考え方を応用する手法です。 具体的には、次の手順で処理を行い

文字列 str が与えられたとき、その中から最後に出現する非繰り返し文字（重複していない文字）を見つける問題を考えてみましょう。例えば、入力文字列が「programming」の場合、後ろから見て最初に一度しか出現しない文字は「n」となります。もし該当する文字が存在しない場合は、-1 を返します。 解決のアプローチ この問題は、頻度配列（frequency array）を使うことで効率的に解決できます。手順は以下の通りです。 まず、各文字の出現回数を記録するための頻度配列を作成します。 文字列を先頭から走査し、各文字の出現頻度を配列に格納していきます。 次に、文字列を末尾から先頭に向かって走査

問題の概要 2つの正整数 n と k が与えられ、「数字 k を含む数、または k で割り切れる数」のうち n 番目の数を求めます。ただし、k の範囲は 2〜9 とします。 例えば n = 15、k = 3 の場合、答えは 33 です。条件を満たす数は [3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 33] と並んでおり、これらはそれぞれ「3 という数字を含む」か「3 で割り切れる」数です。このうち n 番目にあたるのが 33 なので、出力は 33 となります。 解法のアプローチ この問題は、シンプルなシミュレーション(全探索)で解くことがで

関数 F(n) = P − (0.006 × n) があるとします。ここで P はあらかじめ与えられた定数です。さらに、整数のリストと数値 A が与えられたとき、リストの中から「F(n) の値が A に最も近くなる」要素を見つけるのがこの問題の目的です。例として、P = 12、A = 5、リストが {1000, 2000} の場合を考えてみましょう。まず、F(1000) = 12 − (0.006 × 1000) = 6、次に F(2000) = 12 − (0.006 × 2000) = 0 と計算できます。A = 5 に最も近い値は 6 であるため、答えは 1000 となります。解法の考え

2つの文字列 str1 と str2 が与えられたとします。2つ目の文字列に対して「任意の2文字を入れ替える」という操作を0回以上行った後、両者の間で最長の共通プレフィックス(接頭辞)の長さを求めるのがこの問題です。 例えば、str1 = HERE、str2 = THERE の場合、出力は 4 になります。2つ目の文字列は文字を入れ替えることで HERET に変換できるため、先頭から一致する部分の長さは4文字となるからです。 アプローチ 文字の入れ替えは str2 に対してしか行えないため、プレフィックスの長さを最大化するには、次のような考え方でアルゴリズムを組み立てます。 まず str2

空洞（キャビティ）とはここでは、与えられた行列の中に存在する「空洞（キャビティ）」の数を求める問題を考えます。ある要素が空洞とみなされるのは、その周囲に隣接するすべての要素（上下左右および斜め方向）が、その要素よりも大きい場合です。例として、次のような行列を見てみましょう。456715456この行列の場合、中央の「1」は周囲のすべての要素（4, 7, 4, 5, 5, 6, 5, 6）よりも小さいため空洞となり、出力は 1 になります。アルゴリズムの考え方基本的なアプローチはシンプルで、各要素について周囲の要素を順番にチェックし、すべての隣接要素より小さければ空洞としてカウントします。ただし、

n次の正方行列を考えます。この行列にはすべて異なる要素が含まれています。ここで、パス上のすべてのセルが差1で増加順に並ぶような最長パスを求める必要があります。あるセルからは、左・右・上・下の4方向に移動できます。例えば、次のような行列があるとします。129538467この場合の出力は 4 になります。最長パスは 6→7→8→9 となるためです。解法のアプローチこの問題を解くためには、次の考え方に従います。まず、すべてのセルから始まる最長パスを計算します。すべてのセルについて最長パスが求まったら、その中の最大値を返します。このアプローチで重要なポイントは、多くの重複する部分問題が存在することです

問題の概要n個の要素からなる配列が与えられたとき、正確にk個の奇数を含む最長の部分配列（サブ配列）の長さを求めるのがこの問題です。例として、A = [2, 3, 4, 11, 4, 12, 7]、k = 1 の場合を考えてみましょう。このとき答えは 4 となり、該当する部分配列は [4, 11, 4, 12] です（含まれる奇数は 11 の1個だけです）。アルゴリズム：スライディングウィンドウこの問題はスライディングウィンドウ（尺取り法）を使うことで効率的に解けます。全体の計算量は O(n) に抑えられます。手順は以下の通りです。max := 0、count := 0、start := 0 と

はじめにソートされていない配列Aと、2つの数値x・yが与えられたとき、配列内におけるxとyの最小距離（インデックスの差）を求める問題を考えてみましょう。なお、配列には重複した要素が含まれている場合もあります。例えば、配列が A = [2, 5, 3, 5, 4, 4, 2, 3]、x = 3、y = 2 である場合、3と2の間の最小距離は 1 となります。解法のアプローチこの問題は、配列を一度だけ走査することでO(n)の計算量で解くことができます。手順は以下の通りです。配列を左から右へ走査し、xまたはyのいずれかが見つかった時点で停止します。その位置のインデックスを prev として保存します

問題の概要整数 n が与えられたとき、n 辺の凸多角形が持つ対角線の本数を求める問題を考えます。例えば n = 5（五角形）の場合、対角線の数は 5 本になります。対角線の数を求める数式n 辺の凸多角形では、各頂点から対角線を引ける相手は、自分自身と両隣の 2 つの頂点を除いた残りの頂点です。つまり、1 つの頂点あたり n − 3 本の対角線を引くことができます。したがって、n 個の頂点全体では n × (n − 3) 本の対角線が数えられます。しかし、この数え方では各対角線を両端の頂点から 2 回ずつ重複して数えてしまいます。そこで 2 で割ることで、実際の対角線の総数が求められます。対角線

2つの整数NとMが与えられたとき、以下の2種類の操作のみを使ってNからMに到達するために必要な最小ステップ数を求める問題について解説します。数xを2倍にする(xは2*xになる)数xから1を引く(xはx−1になる)例えば、N = 4、M = 6の場合、答えは2になります。まずNに対して「1を引く」操作を行うと3になり、続けて「2倍する」操作を行うと2 * 3 = 6となり、Mに到達できます。したがって、必要な最小ステップ数は2です。解法のアプローチ:問題を逆転させるこの問題を効率的に解く鍵となるのは、問題を逆向きに考えることです。NからMへ向かう代わりに、MからNへ向かうと考え直すと、操作は次の

問題の概要数値 N が与えられ、額面が 1、10、25 のコインがそれぞれ無限にあるものとします。このとき、ちょうど N を支払うために必要なコインの最小枚数を求めます。例えば、N が 14 の場合、答えは 5 枚になります。10 の硬貨 1 枚と 1 の硬貨 4 枚を組み合わせれば、合計 14 をちょうど支払えるためです。アルゴリズムの考え方（貪欲法）この問題は、価値の大きいコインから優先的に使う「貪欲法（Greedy法）」で効率的に解くことができます。手順は以下のとおりです。N < 10 の場合： 1 の硬貨を N 枚使えばよいので、答えは N 枚となります。9 < N <

問題の概要 等差数列の要素が順番に並んだ配列が与えられますが、そのうち1つの要素が欠けています。この欠けている要素を見つけるのが本記事の目的です。 例えば、配列が arr = [2, 4, 8, 10, 12, 14] の場合、公差は2であり、6が欠けているため、出力は 6 となります。 アルゴリズムのポイント:二分探索の活用 この問題は二分探索を使うことで、O(log n)の計算量で効率的に解くことができます。基本的な考え方は以下のとおりです。 まず配列の中央の要素に着目します。 中央の要素とその次の要素の差が、公差(diff)と一致しているかどうかを確認します。 一致しない場合、欠けてい

N×N の行列が与えられたとき、行列の任意の列から要素のペアを取り出し、その差が最大になるペアを見つける問題を考えてみましょう。例えば、次のような行列があるとします。123535967この場合、出力は 8 になります。最大の差を持つペアは 0 列目の (1, 9) だからです。解法のアイデア考え方は非常にシンプルです。各列ごとに最大値と最小値を求め、その差を計算します。そして、すべての列の中で最も大きな差を返せばよいのです。アルゴリズムの手順各列について、最初の行の値を最大値・最小値の初期値として設定します。残りの行を順に走査しながら、最大値と最小値を更新していきます。その列の最大値と最小値の

等比数列の各項が順番に格納された配列があるとします。しかし、そのうちの1つの要素が欠けてしまっています。ここでの課題は、この欠けている要素を見つけることです。 例えば、arr = [1, 3, 27, 81] という配列が与えられた場合、本来は 9 が入るべき位置が空いているため、出力は 9 となります。 二分探索によるアプローチ この問題は二分探索（バイナリサーチ）を使うことで効率的に解くことができます。基本的な考え方は以下の通りです。 まず配列の中央要素（mid）に着目し、中央要素とその隣の要素との比が、数列の公比と一致しているかどうかを確認します。 もし比が一致しなければ、欠けている

3つの整数 a、b、x が与えられたとき、ab の値に最も近い x の倍数を求めることを考えます。例えば、a = 5、b = 4、x = 3 の場合を考えてみましょう。54 = 625 ですが、625 に最も近い 3 の倍数は 624 となります。これが求めるべき出力です。解法のアプローチこの問題は非常にシンプルで、以下の手順に従うことで解決できます。まず num = ab を計算します。次に f = floor(num / x)(num を x で割った値の切り捨て)を求めます。左側(小さい側)で最も近い候補は cl = x × f、右側(大きい側)の候補は cr = x × (f + 1)