C++

問題概要1枚の正方形のピースに対して、合計N回の水平方向または垂直方向のカットを加えるとき、同じ大きさの正方形・長方形のピースを最大でいくつ作れるかを求めるのがこの問題です。まず、具体例を使って問題の内容を確認していきましょう。例1入力 − N = 8出力 − 25説明 − N = 8 の場合、垂直方向のカット数は4回、水平方向のカット数は4回となります。合計ピース数 = 2512345678910111213141516171819202122232425例2入力 − 7出力 − 201234567891011121314151617181920アルゴリズムの考え方カットの総数Nが与えられた

正の整数Nが与えられたとき、そのNを長さa、b、cの線分に分割して、最大で何個のセグメントを作成できるかを求めるのが本課題です。 具体例を使って、何をすべきか見ていきましょう。 入力 − N=8, a=3, b=1, c=2 出力 − 8 説明 − Nは長さbのセグメント8個に分割でき、これが作成可能なセグメントの最大数となります。 入力 − N=13, a=2, b=7, c=3 出力 − 6 プログラムで使用するアプローチ この問題は動的計画法（DP）を用いて効率的に解くことができます。配列MaxSeg[i]には、長さiを作成するために必要なセグメントの最大数を格納します。具体的な手順は

本記事では、サイズ N の配列から選ぶサイズ K の部分集合の積において、末尾に連続する 0（末尾ゼロ）の数が最大となる値を求める問題を解説します。 問題の例 入力 − Arr[] = {5, 20, 2}、K = 2 出力 − 2 説明 − サイズ 2 の部分集合は全部で 3 つ作成できます。 [5, 20] の積は 100 です。[20, 2] の積は 40 です。[5, 2] の積は 10 です。 100 の末尾ゼロの数が最も多く、その数は 2 です。したがって答えは 2 となります。 入力 − Arr[] = {60, 40, 25}、K = 2 出力 − 3 解法の考え方：なぜ 2

この記事では、与えられた範囲 [1, N] 内の数が持ちうる「一意な素因数（重複しない素因数）」の最大個数を求める問題を扱います。まず、例を使って問題を具体的に理解しましょう。入力例と出力例入力 − N = 100出力 − 3説明 − 範囲 [1, 100] の中から 30 を考えてみます。30 = 2 × 3 × 5 となり、素因数はすべて異なる3つです。したがって、範囲 [1, 100] において一意な素因数は最大で3個存在します。入力 − N = 300出力 − 4N = 300 の場合は、2 × 3 × 5 × 7 = 210 ≤ 300 となるため、4つの異なる素因数を持つ数（210

この問題では、3つの数値 a、b、M が与えられます。私たちの課題は、2つの数値の合計を M で割った余り(剰余)を求めるプログラムを作成することです。問題を理解するための例入力: a = 14, b = 54, m = 7 出力: 5 説明: 14 + 54 = 68、68 % 7 = 5解法のアプローチこの問題は非常にシンプルで、以下の手順で解くことができます。まず、数値 a と b を足し合わせます。次に、その合計を M で割った余りを計算して出力します。C++では剰余演算子「%」を使用することで、簡単に余りを求めることができます。実装例解法の動作を示すプログラムは以下の通りです。#in

本記事では、「システムが同時に処理できるゾンビプロセスの最大数はどれくらいか」、言い換えればプログラムがどこまで実行を続けられるのかを、実際のコードで検証していきます。 ゾンビプロセス(defunct process とも呼ばれます)とは、exit() システムコールによってすでに実行を終了しているにもかかわらず、プロセステーブル上にエントリが残り続けているプロセスのことです。通常、子プロセスが終了しても、親プロセスが wait() を呼び出して終了ステータスを読み取らない限り、そのエントリは解放されません。これがゾンビプロセスとして残留する仕組みです。 プログラムで使用するアプローチ プ

問題の概要 この記事では、7セグメントディスプレイに対してN個のセグメントを使用したときに、表示できる最大の数を求める方法を解説します。 まず、具体例を使って何をすべきかを確認しましょう。 入力 − N=5 出力 − 71 説明 − この場合、最大の数は7セグメントディスプレイ上で次のように表示されます。 入力 − N=6 出力 − 111 アルゴリズムのアプローチ この問題は、次の3つの場合に分けて考えることができます。 ケース1 −Nが0または1の場合、どの数字も表示できません。 ケース2 −Nが奇数の場合です。奇数個のセグメントで表示できる数字は2、3、5、7、8であり、その中で最

この記事では、与えられた数 N の各桁の階乗の積と等しくなるような、先頭や末尾に 0 や 1 を含まない最大の数を求める方法を解説します。まず、具体例を使って問題を理解しましょう。入力 − N = 4912出力 − 73332222説明 − 4! × 9! × 1! × 2! = 7! × 3! × 3! × 3! × 2! × 2! × 2! × 2! = 17,418,240入力 − N = 340出力 − 3322なぜ素数の階乗に分解するのか0! と 1! はどちらも 1 に等しいため、0 と 1 の桁は積に影響を与えません。一方、4!、6!、8!、9! はそれぞれ以下のように、素数の階

この問題では、1つの行列が与えられます。私たちのタスクは、上三角部分と下三角部分の要素の合計をそれぞれ計算し、出力するプログラムを作成することです。 下三角行列とは 下三角行列とは、主対角線より上の要素がすべて 0 である行列のことです。対角線上およびその下側の要素のみが値を持ちます。 M00   0   0   …   0 M10   M11   0   …   0 M20   M21   M22   …   0 …

この問題では、n個の整数からなる配列 arr[] が与えられます。配列内のすべてのペアについてXORを計算し、その合計を求めるプログラムを作成することが課題です。問題を理解するための例入力: arr[] = {5, 1, 4} 出力: 10 説明: すべてのペアのXOR: 5 ^ 1 = 4 1 ^ 4 = 5 5 ^ 4 = 1 合計 = 4 + 5 + 1 = 10解法1: 全ペアを列挙する素朴なアプローチ最もシンプルな解き方は、ネストされたループを使って配列内のすべてのペアを列挙する方法です。各ペアのXORを計算し、それを順次合計に加算していきます。アルゴリズムsum = 0 で初期化

問題の概要 この記事では、n個の数値を含む配列 arr[] が与えられたとき、考えられるすべての部分集合（サブセット）のXORの合計を求める方法を解説します。 手順としては、まず配列のすべての部分集合を列挙し、各部分集合ごとに要素同士のXORを計算します。そして、得られた値をすべて足し合わせたものが答えになります。 具体例で理解しよう 入力: arr[] = {5, 1, 4} 出力: 20 各部分集合のXOR: {5} = 5 {1} = 1 {4} = 4 {5, 1} = 4 {5, 4} = 1 {1, 4} = 5 {5, 1, 4} = 0 XORの合計 = 5 + 1 +

この問題では、n個の整数からなる配列 arr[] が与えられます。私たちの課題は、その配列のすべての部分配列（サブ配列）のXOR値の合計を求めるプログラムを作成することです。 具体的には、まず与えられた配列のすべての部分配列を列挙し、それぞれの部分配列について要素全体のXORを計算し、その値を合計用の変数に加算していきます。 問題例で理解しよう 入力: arr[] = {5, 1, 4} 出力: 19 説明: この配列のすべての部分配列のXORは次のようになります。 XOR {5} = 5 XOR {1} = 1 XOR {4} = 4 XOR {5, 1} = 5^1 = 4 XOR {1

この問題では、2つの整数 k と n が与えられます。級数 K^n + (K^(n-1) × (K-1)^1) + (K^(n-2) × (K-1)^2) + … + (K-1)^n の合計を求めるプログラムを作成するのが課題です。問題を理解するための例まず、具体的な入力と出力を見てみましょう。入力: n = 3, k = 4 出力: 175 説明: 級数の合計は以下の通りです。 = 4^3 + ((4^2)×(3^1)) + ((4^1)×(3^2)) + ((4^0)×(3^3)) = 64 + 48 + 36 + 27 = 175解法1：forループを使う単純なアプローチ最もシンプルな方

この問題では、2つの大きな数を表す文字列が与えられます。私たちのタスクは、これら2つの大きな数の合計を求めるプログラムを作成することです。大きな数は int や long long などの標準の整数型では表現できないほど大きくなるため、数値を文字列として受け取り、桁ごとに演算を行う手法が有効です。問題を理解するための例入力: number1 = "341299123919" number2 = "52413424" 出力: 341351537343解決のアプローチこの問題を解くには、両方の文字列を1の位（末尾）から先頭に向かって走査します。各桁を1桁ずつ

この問題では、2つの数値が与えられ、そのうちの1つは桁（けた）の配列として表現されています。ここでの課題は、片方の数値が桁の配列として与えられている場合に、2つの数値の合計を正しく求めるプログラムを作成することです。問題を理解するための例入力: n = 213, m[] = {1, 5, 8} 出力: 371 説明: 213 + 158 = 371解法のアプローチこの問題は、筆算と同じ要領で「桁ごとの加算」を行うことで解くことができます。具体的な手順は以下の通りです。数値 n の最下位桁（1の位）を、配列の末尾（(size-1)番目）の要素に加算します。加算結果が10以上になった場合は繰り上が

この記事では、与えられた積（掛け算の結果）と等しくなる2つの異なる素数を見つけるC++プログラムについて解説します。 具体的には、1つの整数値が与えられたとき、その積がちょうど入力値と一致するような2つの素数のペアを見つけることが課題です。例えば入力が「35」であれば、5 × 7 = 35 が成立するため「5 7」が出力されます。条件を満たすペアが存在しない場合は、その旨を報告します。 アルゴリズムの考え方 この問題は、次の手順で効率的に解決できます。 素数表の作成： エラトステネスの篩（ふるい）を用いて、N未満のすべての素数を事前に求めておきます。 ペアの探索： 2からN未満までの各整

はじめに本記事では、C++を使用して2つの文字列に共通しない文字(アンコモン・キャラクター)を見つけるプログラムについて解説します。具体的には、2つの文字列が与えられたとき、どちらか一方の文字列にのみ含まれる文字を抽出し、アルファベット順にソートして出力するのが目的です。問題の概要入力として2つの文字列を受け取り、次の条件を満たす文字を出力します。片方の文字列には存在するが、もう片方には存在しない文字出力はアルファベット順(a〜z)にソートされていること例えば、「tutorials」と「point」という2つの文字列が与えられた場合、共通しない文字は「a l n p r s u」となります。ア

このチュートリアルでは、C++を用いて、同一の行列を行優先(row-major)順序と列優先(column-major)順序の両方で表現し、それらを加算して得られる新しい行列のトレースを求めるプログラムについて解説します。ここでは、行優先順序で格納された配列と列優先順序で格納された配列の2つが与えられます。私たちの課題は、この2つの行列を加算して形成される行列のトレースを計算することです。トレースとは?行列のトレース(trace)とは、主対角線上にある要素、すなわち行番号と列番号が等しい位置にある要素の総和のことです。本記事のコードでは、i == j となる要素をすべて合計することでトレースを

はじめに このチュートリアルでは、木構造において「3つのノード（トリプレット）を結ぶパス上に含まれるノードの数」が最大となるようなトリプレットを見つけるプログラムについて解説します。 N個のノードからなる木が与えられ、その中から3つのノードを選びます。選んだノード同士を結ぶパス全体で覆われるノードの数が最大になるような組み合わせを見つけることが、この記事のゴールです。 アルゴリズムのアプローチ この問題は、木の「直径」（任意の2ノード間で最も長くなる経路）を求めるテクニックを応用することで効率的に解けます。具体的な手順は次の通りです。 1. 任意のノードからDFS（深さ優先探索）を行い、最も

はじめに このチュートリアルでは、和（合計）と積がどちらもNに等しい2つの数を見つけるC++プログラムについて解説します。 具体的には、ある整数値Nが与えられたとき、その2つの数の和と積がそれぞれ与えられた値Nと一致するような、別の2つの数を求めるのが課題です。 数学的な背景 求めたい2つの数を a と b とすると、以下の連立方程式が成り立ちます。 a + b = N a × b = N この条件から二次方程式 x² − Nx + N = 0 が導かれ、解の公式を用いることで次のように表せます。 a = (N + √(N² − 4N)) / 2b = (N − √(N² − 4N))