C++

問題概要 [分子, 分母]（分子 / 分母）というペアからなる分数のリストが与えられます。このリストをもとに、次の条件をすべて満たす新しい分数リストを作成するのが課題です。 既約形にする：各分数をこれ以上約分できない形まで簡略化します。（例：20/14 → 10/7） 重複を削除する：約分した結果が同一になる分数は1つだけ残します。 昇順にソートする：分数の実際の値に基づいて小さい順に並べます。 符号の扱い：負の分数の場合、「-」の記号は必ず分子側に付けます。 たとえば、入力が {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}} の場

テレビ番組のリストと、それぞれの視聴時間のリスト、さらに整数 k が与えられたとします。shows[i] と duration[i] は、i 番目の人が視聴した番組名とその視聴時間を表しています。このとき、最も視聴時間の長い上位 k 個の番組の合計視聴時間を求めるのが本記事の目的です。問題の例例えば、入力が以下のような場合を考えてみましょう。shows: [Castle Play, Fairy Tale Series, Castle Play, Jerry Mouse, Rich Boy]duration: [6, 4, 6, 14, 5]k = 2この場合の出力は 26 になります。理由を見

問題の概要 同じ長さを持つ2つの文字列 s と t があり、どちらも小文字の英字のみで構成されているとします。まず文字列 s を任意の順序に自由に並べ替え、その後、s を t と一致させるために必要な最小の文字置換回数を求めます。 例えば、入力が s = eccynue、t = science の場合、答えは 2 になります。これは、eccynue を yccence に並べ替えた後、先頭の y を s に、2番目の c を i に置き換えることで science に変換できるためです。 解決のためのアプローチ この問題の鍵となるのは、並べ替えによって一致させられる文字はできるだけ多く一致

問題概要 2つの文字列 s と t が与えられたとき、s を回転（rotate）させることで t を作り出せるかどうか、つまり s が t の回転になっているかを判定します。 例えば、入力が s = helloworld、t = worldhello の場合を見てみましょう。s を適切な位置で分割して前後を入れ替えると t が得られるため、出力は True（1） になります。 解法のアプローチ この問題は、以下の手順でシンプルかつ効率的に解くことができます。 まず、s0 と s1 の長さが異なる場合は回転になり得ないため、false を返します。 s0 を自分自身と連結した文字列 s =

はじめに文字列 s が与えられたとき、連続して重複している文字を取り除き、各文字を1つだけ残した新しい文字列を返すことを考えます。同じ文字が続けて現れる場合は、それらを1文字にまとめます。文字の出現順序は元のまま維持されます。例として、入力が heeeeelllllllloooooo の場合、出力は helo になります。解法のアプローチこの問題は、以下の手順で解くことができます。結果を格納するための空の文字列 ret を用意します。i = 0 から s のサイズ未満まで、i を1ずつ増やしながらループします。ret が空でなく、ret の最後の文字が s[i] と同じである場合は、その文字を

二分木の根 root が与えられたとき、「自分自身の値が、すべての子孫の値以上である」という条件を満たすノードの個数を求める問題です。たとえば、次のような二分木が入力として与えられたとします。この場合の出力は 4 になります。値が 3 のノード以外は、すべてこの条件を満たしているためです。解き方のアプローチこの問題は、深さ優先探索（DFS）を使うことで効率的に解けます。各ノードに対して「その部分木内の最大値」をボトムアップに返しながら、条件を満たすノードをカウントしていくのがポイントです。手順は以下のとおりです。dfs() 関数を定義します。引数としてノードを受け取ります。ノードが NULL

ここでは、source と target という2つの二分木が与えられ、source を反転(inversion)した木 T のうちの何れかが target の部分木になっているかどうかを判定する問題を扱います。言い換えれば、target の中に、T と値および構造が完全に一致し、そのすべての子孫ノードまで含めて同一であるようなノードが存在するかを確認するということです。反転木とは?ある木が別の木の「反転」であるとは、次のいずれかの条件を満たす場合を指します。両方の木が空(ヌル)である左右の子を必要に応じてスワップしてもよく、かつその左部分木と右部分木が互いに反転関係にある例として、入力が次の

問題の概要 正の整数を格納した片方向リンクリストが与えられます。このリストを処理し、各ノードの next ポインタが「そのノードの値（val）の数だけ前方にあるノード」を指すように変更します。ジャンプ先となるノードが存在しない場合は、next を NULL に設定します。 たとえば、入力が {2, 2, 3, 5, 9, 15, 3, 4} の場合、出力は [2, 3, 15] になります。これは、先頭ノード（値 2）から 2 つ先のノード（値 3）へ、さらに 3 つ先のノード（値 15）へと順番にジャンプしていき、次のジャンプでリストの範囲外に出るためそこで終了するからです。 解決のため

「(」と「)」のみで構成される文字列 s が与えられたとき、この文字列をバランスの取れた状態にするために挿入が必要な括弧の最小数を求める問題について解説します。例えば、入力が「(()))(」の場合、出力は 2 になります。これは「(()))(」を「((()))()」のように変形することで、バランスの取れた文字列にできるからです。アルゴリズムの考え方この問題は、以下の手順で解くことができます。カウンタとして o := 0、cnt := 0 を初期化します。i := 0 から文字列 s の長さ未満の間、i を 1 ずつ増やしながら以下を繰り返します。s[i] が「(」と等しい場合:o を 1 増や

各要素が開始時刻と終了時刻 [start, end] を持つ区間のリストが与えられたとします。この中から互いに重複しない2つの区間を選び、そのサイズの合計の最小値を求めます。ここで、区間のサイズは (end - start + 1) として定義されます。条件を満たす2つの区間が存在しない場合は 0 を返します。例えば、入力が [[2,5],[9,10],[4,6]] の場合、出力は 5 になります。これは、サイズ 3 の区間 [4,6] と、サイズ 2 の区間 [9,10] を選ぶことで、合計 5 という最小値が実現できるためです。解法のアプローチこの問題は、動的計画法（DP）と二分探索を組み

数値のリストが与えられたとき、そのリストを左方向に k 要素分だけ回転させるメソッドを実装する問題を考えてみましょう。例えば、入力が [5,4,7,8,5,6,8,7,9,2]、k = 2 の場合、出力は [8,5,6,8,7,9,2,5,4,7] となります。先頭の2要素（5と4）が末尾に移動し、残りの要素が前に詰められるイメージです。解決のアプローチこの問題は、以下の手順で解くことができます。結果を格納するための配列 ret を定義します。n := nums のサイズ（要素数）とします。k := k mod n として、k が n 以上の場合に備えます（k が n の倍数なら回転しても元の

小文字アルファベットのみで構成された文字列 s が与えられたとします。このとき、ある1つの文字が他のすべての文字の合計よりも多く出現するような、最短の部分文字列(最小長は2)の長さを求める必要があります。条件を満たす部分文字列が存在しない場合は -1 を返します。例えば、入力が abbbcde の場合、出力は 2 になります。これは部分文字列 bb が最短であり、この中では b が他の文字より多く出現しているためです。解法のアプローチこの問題を解くためには、以下の手順に従います。配列 cnt を受け取る関数 ok() を定義します。total := 0、maxVal := 0 と初期化します。

本記事では、C++を使って複利を計算するプログラムの作成方法について解説します。 複利とは、発生した利息を元本に加算し、その更新された合計額に対して再度利息を計算する仕組みのことです。単利と異なり「利息が利息を生む」ため、運用期間が長くなるほど資産が加速度的に増えていくのが特徴です。 複利の計算式 複利は次の数式で求めることができます。 A = P × (1 + r/100)t P：元本（最初に預け入れた金額） r：年利率（%） t：運用期間（年） A：t年後の元利合計額 C++での実装例 #include <bits/stdc++.h> using namespace std

本記事では、2つのデータセットの関係性を数値で表せる「相関係数」を求めるC++プログラムについて解説します。相関係数とは、2つの変数間の関係の強さと方向を示す統計量で、-1から1までの値を取ります。1に近いほど正の相関が強く、-1に近いほど負の相関が強いことを意味し、0に近い場合はほぼ相関がないと判断できます。このプログラムでは、2つの配列として与えられたデータを受け取り、それらの値の間の関係の強さを表す相関係数（ピアソンの積率相関係数）を計算します。相関係数の計算式相関係数 r は次の公式で求められます。r = (n・ΣXY − ΣX・ΣY) / √[ (n・ΣX² − (ΣX)²) × (

このチュートリアルでは、指定された範囲の中から約数の個数が奇数となる数を数えるC++プログラムを紹介します。具体的には、範囲の下限と上限が与えられ、その間に含まれる数のうち、約数の個数が奇数になっているものをすべてカウントするのが目的です。数学的なポイント：約数の個数が奇数になるのは完全平方数だけ一般に、整数 n の約数は d と n/d のペアで現れるため、その個数は偶数になります。しかし、完全平方数(1, 4, 9, 16, …)の場合だけは例外です。例えば n = 9 の場合、約数は 1, 3, 9 の3つです。これは 3 × 3 = 9 となり、√n 自身が約数として1回だけ現れるため

このチュートリアルでは、C++を使って共分散を求めるプログラムの作成方法について解説します。 ここでは、2組の数値データ(確率変数)が与えられ、それらの共分散を計算します。共分散とは、2つの変数がどの程度連動して変動するかを示す統計的な指標のことです。 共分散とは 共分散は、2つの変数の関係性を測るための統計量です。片方の変数が大きくなるときにもう片方も大きくなる傾向があれば正の値になり、逆の傾向があれば負の値になります。共分散は次の式で求められます。 cov(X, Y) = Σ(xi − x̄)(yi − ȳ) / (n − 1) ここで、x̄とȳはそれぞれのデータセットの平均値、nはデー

このチュートリアルでは、カレン数（Cullen Number）を求めるC++プログラムについて解説します。カレン数とは？カレン数とは、次の公式で表される整数列のことです。2n × n + 1このプログラムでは、1つの整数 n が与えられたとき、上記の公式を使って n 番目のカレン数を計算して出力します。例えば、n = 2 の場合、22 × 2 + 1 = 9 となるため、答えは 9 になります。C++での実装例以下が、n 番目のカレン数を求めるC++のコードです。#include <bits/stdc++.h> using namespace std; // n番目のカレン数を求

このチュートリアルでは、C++を用いて「3つの点を通る平面の方程式」を求めるプログラムについて解説します。3次元空間内の異なる3点が与えられたとき、その3点すべてを通る平面は一意に定まります。本記事では、与えられた3点から平面の方程式 ax + by + cz + d = 0 の形で求める方法を、数学的な考え方とサンプルコードの両面から紹介します。平面の方程式を求める考え方3点 P1(x1, y1, z1)、P2(x2, y2, z2)、P3(x3, y3, z3) を通る平面の方程式は、以下の手順で求められます。まず、点P1からP2へのベクトル (a1, b1, c1) と、点P1からP3へ

このチュートリアルでは、最初のN個のイッカノビフ（Iccanobif）数を求めるC++プログラムについて解説します。 整数Nが与えられ、その位置までのイッカノビフ数をすべて出力することが課題となります。イッカノビフ数はフィボナッチ数と非常によく似た数列ですが、決定的な違いがひとつあります。それは、直前の2つの数を加算する前に、それぞれの桁を反転（逆順）させるという点です。 アルゴリズムの流れ 数列は0と1から始まります。 3項目以降は、「直前の2つの数の桁をそれぞれ反転した値の和」を新しい項として追加します。 例えば、13の次の項は reverse(8) + reverse(13) = 8

このチュートリアルでは、浮動小数点数の最大公約数（GCD：Greatest Common Divisor）を求めるC++プログラムについて解説します。通常、GCDは整数に対して計算されることが多いですが、この記事では小数を含む2つの値が与えられた場合に、そのGCDを求める方法を紹介します。アルゴリズムの考え方浮動小数点数のGCDを求めるには、ユークリッドの互除法を応用します。具体的な手順は以下の通りです。まず、大きい方の値を a、小さい方の値を b とするように入れ替えます。b の絶対値が十分に小さくなった場合（ここでは0.001未満）、その時点の a をGCDとして返します。そうでなければ、