C++

問題概要 この問題では、整数 N が与えられ、次の数列の N番目の項 を求めるC++プログラムを作成します。 対象となる数列 1, 3, 12, 60, 360, 2520 …(第N項まで) 入出力例で問題を確認しましょう 入力: N = 6 出力: 2520 解法アプローチ この数列の一般項の公式は一見すると分かりにくいですが、項の値が急激に増大している点に注目すると、階乗 または 指数関数的な成長 が関係していると推測できます。 まず階乗を検討してみると、数列の増加率が階乗の値のおよそ半分になっていることが観察できます。さらに、初項が「2の階乗」に相当することもポイントです。これら

本記事では、数列 0, 11, 28, 51, 79, 115, 156, 203, … のN番目の項を求めるプログラムを、C++で実装する方法を解説します。 問題の概要 整数Nが与えられたとき、上記の数列におけるN番目の項の値を求めるのが課題です。 入出力例 まず、具体的な例で問題を確認してみましょう。 入力： N = 5 出力： 79 解法のアプローチ この数列は、隣り合う項同士の差が一定のペースで増えていく「二次数列」です。そのため、各項を順番に計算していく必要はなく、N番目の項を次の一般式から直接求めることができます。 Tn = 3 × N² + 2 × N − 5 たとえば N

この問題では、整数 N が与えられ、C++ を用いて数列「2, 12, 28, 50, 77, 112, 152, 198, …」の第 N 項を求めるプログラムを作成します。 問題の概要 与えられた数列の第 N 項を求めることが課題です。 対象となる数列: 2, 12, 28, 50, 77, 112, 152, 198, ...(全 N 項) 入出力例 入力: N = 6 出力: 112 解法アプローチ この数列は、項が進むにつれて増加幅が広がっていく、いわゆる放物線状(二次曲線的)な増加を示しています。そのため、一般項は二次式で表せると推測できます。実際に各項を N の式で整理する

問題の概要 複素数を表す2つの文字列が与えられたとします。この文字列を解析（パース）して複素数の乗算を実行し、その結果を再び文字列として返すことを考えましょう。 例えば、入力が「1+-1i」と「1+-1i」である場合、計算結果は「0+-2i」となります。 解決のためのアプローチ この問題は、以下の手順に従うことで解くことができます。 aa := 1つ目の複素数の実部と虚部をペアとして取得する bb := 2つ目の複素数の実部と虚部をペアとして取得する x := aa.real × bb.real − aa.img × bb.img（結果の実部） y := aa.real × bb.img

24時間制の時刻を「時:分」形式の文字列で表したリストが与えられます。このリストの中から、任意の2つの時刻の組み合わせについて分単位の差を計算し、その最小値を求めるのが本記事のテーマです。例えば、入力が [12:30, 15:17] の場合、2つの時刻の差は167分となるため、出力は 167 になります。 ポイント：時刻は循環構造を持つ この問題で注意すべき点は、時計の時刻が循環していることです。例えば「23:50」と「00:10」の差は、単純な引き算では1430分になりますが、実際には真夜中をまたいで20分しか離れていません。したがって、日付をまたぐケースも必ず考慮する必要があります。 解法

問題の概要正の整数のリストが与えられ、隣接する整数同士で浮動小数点数の除算を行うことを考えます。例えば、[2,3,4] は 2 / 3 / 4 として評価されます。ここで、演算の優先順位を変更するために、任意の位置に任意の個数の括弧を挿入することができます。目的は、計算結果が最大になるように括弧を配置し、その式を文字列形式で返すことです。ただし、式には冗長な括弧を含めてはいけません。例えば、入力が [1000,100,10,2] の場合、出力は 1000/(100/10/2) となります。解法のポイントこの問題には重要な数学的な性質があります。除算の連鎖において結果を最大化するには、最初の数を

32ビットの正の整数 n が与えられたとき、n とまったく同じ数字の並びを持ち、かつ n よりも大きい値となる最小の32ビット整数を求めます。そのような整数が存在しない場合は -1 を返します。例えば、入力が 213 の場合、同じ数字を使って作れるより大きい数のうち最小のものは 231 なので、答えは 231 になります。解法のアプローチこの問題は、いわゆる「次の順列（next permutation）」を求めるアルゴリズムと同じ考え方で解くことができます。手順は以下の通りです。s := n を文字列に変換したもの、sz := s の長さ、ok := false と初期化するi を sz -

問題の概要 長さNの0始まりの配列Aがあり、そこには0からN-1までの整数がすべて1回ずつ含まれているとします。このとき、次のような集合Sの最長の長さを求めて返すのがこの問題の目的です。 S[i] = {A[i], A[A[i]], A[A[A[i]]], …} Sの最初の要素はインデックスiにあるA[i]から始まり、次はA[A[i]]、その次はA[A[A[i]]]というように値をたどっていきます。そして、同じ要素が再び現れる直前で追加を打ち切ります。 例として、配列が A = [5,4,0,3,1,6,2] の場合を考えてみましょう。インデックス0からスタートすると、A[0]=5 → A[5

非負整数のみから構成される配列が与えられ、その中から3つの要素を選んで三角形の3辺としたときに、実際に三角形を成立させられる組み合わせ(トリプレット)の総数を数えるのがこの問題です。 例えば、入力が [2, 2, 3, 4] の場合、答えは 3 になります。以下の3通りが有効な組み合わせだからです。 1番目の「2」を使った [2, 3, 4] 2番目の「2」を使った [2, 3, 4] [2, 2, 3] 解法の鍵：三角形の成立条件 3辺 a、b、c(c を最長の辺とする)が三角形を成すための条件は、a + b > c が成り立つことです。この性質を利用すると、すべての組み合わせを総

テキストエディタには、最初は1文字の「A」だけが表示されているとします。この状態から、各ステップで次の2種類の操作を実行できます。 すべてコピー(Copy All):メモ帳上にあるすべての文字をコピーします。 貼り付け(Paste):直前にコピーした文字を貼り付けます。 ここで整数 n が与えられたとき、最小の操作回数でメモ帳上にちょうど n 個の「A」を揃えることが目標です。つまり、n 個の「A」を得るために必要な最小ステップ数を求めるのがこの問題です。 例として n = 3 の場合を考えてみましょう。答えは 3 です。初期状態では「A」が1つしかないため、まずすべてコピーを行い、続け

問題の概要二分木が与えられたとき、その中に存在する重複する部分木（duplicate subtrees）をすべて見つける問題を考えてみましょう。ここでいう「重複」とは、構造とノードの値が完全に一致する部分木が2つ以上存在することを意味します。各種類の重複部分木について、代表としてどれか1つの根ノードを返せばよいことになっています。たとえば、次のような二分木があるとします。この木に含まれる重複する部分木は、以下の2つです。値 4 を持つ単一ノードの部分木（2か所に出現）根が 2 で、子に 4 を持つ部分木（2か所に出現）解法のアプローチ：部分木のシリアライズこの問題を効率的に解く鍵となるのは、部

本記事では、二分木（バイナリツリー）を m×n の2次元文字列配列として整形して出力する方法を解説します。出力には以下のルールが適用されます。行数 m は、与えられた二分木の高さと一致すること。列数 n は、必ず奇数になること。ルートノードの値は、最初の行のちょうど中央に配置する。ルートノードが存在する行と列によって、残りの領域は「左下」と「右下」の2つの部分に分割される。左側の部分木は左下の領域へ、右側の部分木は右下の領域へそれぞれ出力する。左右の領域は同じサイズとする。片方の部分木が存在しない場合でも、何も出力はしないものの、もう一方の部分木と同じサイズの領域は確保しておく必要がある。ただ

問題の概要 昇順にソートされた整数型配列 nums が与えられます。この配列を1つ以上のサブシーケンス(部分列)に分割できる場合にのみ true を返してください。ただし、各サブシーケンスは次の条件を満たす必要があります。 連続する整数で構成されていること 長さが3以上であること 例えば、入力が [1,2,3,3,4,4,5,5] の場合、出力は true になります。[1,2,3,4,5] と [3,4,5] という2つの連続した数列に分割できるためです。 解決アプローチ この問題は、ハッシュマップで各要素の出現頻度を管理しながら、貪欲法(グリーディ法)で処理を進めることで効率的に解け

問題の概要 2つの整数 n と k が与えられます。ここでの目標は、1から n までの範囲に含まれる n 個の異なる正の整数からなるリストを構築することです。ただし、そのリストは次のルールを満たす必要があります。 リストを [a1, a2, a3, ..., an] と表すとき、隣接要素の絶対差からなるリスト [|a1 − a2|, |a2 − a3|, |a3 − a4|, ..., |an−1 − an|] には、ちょうど k 種類の一意な整数が含まれていなければなりません。条件を満たす答えが複数存在する場合は、そのうちのどれか 1 つを出力すれば問題ありません。 入出力例 たとえば、入力

問題概要 ある部屋に n 個の電球があり、すべて最初は点灯しています。壁には4つのボタンが用意されており、これらのボタンに対してちょうど m 回の操作を行ったとき、n 個の電球が取りうる状態のパターン数を求めるのがこの問題です。 電球には [1, 2, 3, ..., n] というように番号が振られており、4つのボタンの機能は以下の通りです。 ボタン1: すべての電球の点灯・消灯を反転する ボタン2: 偶数番号の電球の状態を反転する ボタン3: 奇数番号の電球の状態を反転する ボタン4: (3k + 1) 番目（k = 0, 1, 2, ...）の電球の状態を反転する 例えば、n = 3、

問題概要 N×Nのチェス盤があるとします。ナイトはr行c列目のマスからスタートし、ちょうどK回の移動を試みます。行と列は0始まりのインデックスで表されるため、左上のマスは(0, 0)、右下のマスは(N-1, N-1)となります。 ナイトは1つのマスから8種類の異なるマスへ移動することができます。その移動パターンは下図の通りです。 ナイトは移動のたびに、8つの可能な移動の中からランダムに1つを選択します。そして、ちょうどK回の移動を完了するか、チェス盤の外に出てしまうまで移動を続けます。この問題では、ナイトが移動を終えた時点で盤上に残っている確率を求めます。 例えば、入力が「3, 2, 0,

非負整数 N が与えられたとき、N 以下の数の中で「単調増加する桁」を持つ最大の数を求めることを考えます。ここで、ある整数が単調増加する桁を持つとは、隣り合うどの2桁 x と y についても x <= y が成り立つ場合を指します。例えば、入力が 332 の場合、答えは 299 となります。この問題は、貪欲法（グリーディーなアプローチ）を使って効率的に解くことができます。基本的な考え方は、左から右へ桁を走査し、単調増加が崩れる位置を見つけたら、その直前の桁を1つ減らして、それ以降のすべての桁を 9 にするというものです。解法の手順数値 N を文字列 s に変換し、i := 1、n := s の

無限に続く数直線上の位置0に立っているとします。目標地点は位置 target にあります。各移動では、左方向または右方向のどちらにも進むことができ、n回目の移動(1から開始)ではちょうどn歩進むことになります。このとき、目的地に到達するために必要な最小の移動回数を求めるのが課題です。 例えば、target = 3 の場合、答えは 2回 となります。0から1へ(+1)、1から3へ(+2)と進むことで、ちょうど2回の移動で目標に到達できます。 解法のアプローチ この問題は、以下の手順で効率的に解くことができます。 target := |target|、cnt := 0 と初期化する targ

長さNの順列A（[0, 1, ..., N-1]を並び替えた配列）を考えてみましょう。グローバル反転（大域転倒）とは、0 <= i < j < N かつ A[i] > A[j] を満たすインデックスのペア(i, j)の総数を指します。一方、ローカル反転（局所転倒）とは、0 <= i < N かつ A[i] > A[i+1]、つまり隣接する2つの要素が逆順になっている箇所の数です。 この問題では、グローバル反転の総数とローカル反転の総数が一致する場合にのみtrueを返す必要があります。例えば、入力が [1,0,2] の場合、ローカル反転は「1と0」の1

この問題では、最初の行が 0 から始まる特別な数列を扱います。それ以降の各行では、直前の行を参照し、0 を「01」に、1 を「10」に置き換えることで新しい行を生成していきます。N 行とインデックス K が与えられたとき、N 行目の K 番目の記号を求めるのが目的です(※ K は 1 から始まるインデックスです)。たとえば N = 4、K = 5 の場合、出力は 1 になります。その理由は以下の通りです。行 1: 0行 2: 01行 3: 0110行 4: 01101001行 4 の 5 番目の文字を数えると「1」であることが確認できます。解法のアプローチこの問題は、行が生成される規則性に注目