C++

この記事では、2次元行列 mat[][] が与えられたとき、C++を使って各行から条件を満たす要素を1つずつ選び、その合計を最大化するプログラムの作成方法を解説します。問題の概要行列の各行から1つずつ要素を選んで合計を求めます。ただし、現在の行で選ぶ要素は、直前の行で選んだ要素よりも大きい値でなければなりません。この条件を満たす要素の組み合わせの中で、合計が最大になるものを求め、条件を満たす選び方が存在しない場合は -1 を出力します。具体例で問題を確認してみましょう。入力mat[][] = {{4, 6, 1}, {2, 5, 7}, {9, 1, 2}}出力22説明1行目 = 6 2行目

二分木の簡潔なエンコーディングとはここに一つの二分木があるとします。ご存知の通り、二分木の簡潔なエンコーディング（succinct encoding）とは、理論上の最低限に近い記憶領域で木の構造を表現できる手法です。構造的に異なる「n個のノードを持つ二分木」の総数は、n番目のカタラン数（Catalan number）によって表されます。nが大きくなると、この数はおよそ4^nに近づくため、エンコードには最低でも log₂(4^n) = 2n ビットが必要になります。したがって、簡潔な二分木は 2n + O(n) ビット程度で表現できることになります。たとえば、次のような二分木が入力として与えられ

配列Aが与えられます。Aに含まれるすべての要素はm回ずつ出現しますが、ただ1つの要素だけが1回しか出現しません。この課題では、その一意な要素を見つけることが目標です。例えば、入力が A = [6, 2, 7, 2, 2, 6, 6]、m = 3 の場合、出力は 7 になります。解法の考え方（ビットカウント方式）この問題は、整数をビット単位で扱うことで効率的に解くことができます。各ビット位置について、配列内の要素のうちそのビットが立っているものの個数を数えます。m回出現する要素は各ビット位置にmの倍数回だけ寄与するため、「count[i] % m」が0以外になるのは、一意な要素がそのビット位置に

二分木が与えられたとき、値が連続して増加するノードから構成される最長のパスの長さを計算することを考えます。ここで、すべてのノードは単体で長さ1のパスとして扱われるものとします。例えば、次のような二分木が入力として与えられた場合を考えてみましょう。この場合、(11, 12, 13) が最も長い連続増加パスとなるため、出力は 3 になります。解法のアプローチこの問題を解くために、以下の手順に従います。再帰関数 solve() を定義します。引数として root（現在のノード）、prev_data（前のノードの値）、prev_length（現在のパスの長さ）を受け取ります。root が NULL の

この記事では、サイズがそれぞれ異なるk個のソート済み配列を1つの配列にマージし、ソートされた結果を出力する方法を解説します。例えば、k = 3 で配列が {2, 4}、{3, 5, 7}、{1, 10, 11, 12} の場合、出力は次のようになります。1 2 3 4 5 7 10 11 12アルゴリズムの考え方：優先度付きキュー（最小ヒープ）を使うすべての要素を単純に連結してからソートすることもできますが、その場合の計算量は O(N log N)（Nは全要素数）になります。一方、各配列がすでにソートされているという性質を活かせば、優先度付きキュー（min-heap）を使って O(N log

問題の概要サイズが必ずしも同じとは限らない、3つのソート済み配列 A、B、C が与えられます。このとき、各配列から1要素ずつ選んでできる三つ組 A[i]、B[j]、C[k] について、その最大値と最小値の差、すなわち max(A[i], B[j], C[k]) − min(A[i], B[j], C[k]) を最小化するのが本問題の目的です。入力例1：A : [ 2, 5, 6, 9, 11 ] B : [ 7, 10, 16 ] C : [ 3, 4, 7, 7 ]出力：1説明：A[i] = 6、B[j] = 7、C[k] = 7 を選択すると、max − min = |7 − 6| = 1

問題概要 2次元配列（グリッド）があり、各セルにはそのセルを通過するために必要なコストを表す数値が格納されています。左上のセルから右下のセルへ移動するとき、合計コストが最小となる経路を見つけるのが目的です。この問題のポイントは、上下左右の4方向への移動がすべて許可されているという点です。 例えば、次のような入力が与えられたとします。 32101661319 1114481587 1011141751234 891264221141 100331124221 この場合の出力は 340 となります。これは (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34

概念長さ p、幅 q のボードが与えられたとき、このボードを p×q 個の正方形に分割する際のコストを最小にすることを目指します。ボードの各辺にはそれぞれ切断コストが設定されており、コストが最小になるような切断の順序を選択することが求められます。例下図のようなボードを正方形に分割する場合、最適な切断方法は以下の通りです。このケースにおける合計最小コストは 65 となり、以下の手順で計算されます。初期値 : Total_cost = 0 Total_cost = Total_cost + 辺のコスト × 現在のピース数 コスト5 水平切断 : Cost = 0 + 5*1 = 5 コスト5 垂直

概要 A × B のマス目からなるチェス盤が与えられたとき、「盤面を2つに分断してしまわない」という条件を満たす範囲で、最大で何回のカット(切り込み)を入れられるかを求めるのが本記事のテーマです。 一見すると単純なパズルのように見えますが、盤面のつながりを保ちながらどこまで切り進められるかを考える、幾何学およびグラフ理論の観点からも興味深い問題です。 入出力の例 具体的な入力と出力の例は以下の通りです。 入力 A = 2, B = 4 出力 最大カット数 = 3 入力 A = 2, B = 2 出力 最大カット数 = 1 考え方 A = 2、B = 2 の場合、カットできるのは1回だけです

概要 ノード数 b、エッジ数 a の無向グラフが与えられたとき、そのグラフにオイラー回路（Euler Circuit）を構築するために追加すべき最小のエッジ数を求めるのが本記事のテーマです。 入力例 b = 3, a = 2 Edges[] = {{1, 2}, {2, 3}} 出力例 1 ノード1とノード3をつなぐことで、オイラー回路を構築できます。 考え方 グラフにオイラー回路が存在するためには、すべてのノードの次数が偶数である必要があります。次数が偶数であれば、あるノードに入った後、別のエッジを使って出ていくことができるためです。 ここで、次の2つの場合が考えられます。 ケース1：グ

概要 N個の整数が与えられたとき、残りの数のGCD(最大公約数)が、元のN個の数のGCDよりも大きくなるようにするために取り除くべき数の最小個数を求めます。GCDを大きくすることが不可能な場合は「NO」と出力します。 入力例1 b[] = {1, 2, 4} 出力例1 1 最初の要素「1」を取り除くと、残りの数のGCDは2となり、元のGCD(1)より大きくなります。必要な削除数は1です。 入力例2 b[] = {6, 9, 15, 30} 出力例2 2 元のGCDは3です。6と9の2つを取り除くと、残りは{15, 30}となり、GCDは15になります。これは元のGCDの3より大きいため、必要

概要正の整数 n 個からなる配列 arr[] が与えられたとき、二項係数 arr[i]Carr[j] が最大となるような要素のペア arr[i] と arr[j] を配列から見つけるのが課題です。条件を満たすペアが複数存在する場合は、そのうちのいずれか1つを出力すれば構いません。入力例arr[] = {4, 1, 2}出力例4 2 4C1 = 4 4C2 = 4 2C1 = 2 (4, 2) が nCr を最大化する唯一のペアです。解法の考え方nCr は n に関して単調増加する関数とみなせます。つまり n+1Cr > nCr が成り立ちます。この性質を利用することで答えに近づくことがで

概念本記事では、根付き木における2つのノードのLCA（最小共通祖先）を求める問題を、RMQ（区間最小値クエリ）の問題へ帰着させることで解く手法について解説します。用語の整理根付き木Tにおいて、2つのノードaとbの最小共通祖先（Lowest Common Ancestor：LCA）とは、aとbの両方を子孫として持つノードのうち、根から最も遠い位置にあるノードを指します。例えば、下図のように、ノードDとノードIのLCAはノードBになります。LCA問題はさまざまなアプローチで解くことが可能で、それぞれ時間計算量や空間計算量が異なります。区間最小値クエリ（Range Minimum Query：RMQ

基本概念与えられた二分木の中から、最大の完全二分部分木のサイズを求めるのが本記事のテーマです。完全二分木とは – 最後のレベルを除くすべてのレベルがノードで完全に埋まっており、最後のレベルのノードができるだけ左側に寄せられている二分木を指します。すべての完全（パーフェクト）二分木は必ず完全二分木でもありますが、その逆は成り立ちません。また、ある木が完全二分木でない場合、それは完全（パーフェクト）二分木でもないという点にも注意してください。入力例1 2 / \ 3 4 / \ / \ 5 6 7 8 / \ / 9 10 11出力例1Size :

概要整数 N が与えられたとき、その桁をできるだけ少なく（0桁でも可）削除して得られる「最大の立方数」を求めるのが本記事のテーマです。与えられた数値からは、どの桁でも自由に削除できます。ここでいう立方数とは、ある整数 B に対して A = B3 と表せる数のことです。たとえば 8 = 23 や 125 = 53 などが該当します。なお、どのように桁を削除しても立方数を作れない場合は -1 を出力します。具体例例1： N = 1025 の場合、「0」を削除すると残りは 125 となり、5 × 5 × 5 = 125 なので立方数です。例2： N = 806 の場合、「0」と「6」を削除すると残り

概要 文字「(」「)」「{」「}」「[」「]」を含む文字列 str が与えられたとき、その括弧がバランスしているかどうかを判定するのが本記事のテーマです。 括弧が「バランスしている」とは、以下の条件を満たすことを指します。 開いた括弧は、必ず同じ種類の括弧で閉じられていること。 開いた括弧が、正しい順序で閉じられていること。 入力例1： str = (()){} 出力： Yes（バランスしている） 入力例2： str = ))(([][ 出力： No（バランスしていない） アルゴリズムの考え方 一般的にこの種の問題はスタックを使えば O(N) 時間で解けますが、ここでは追加のメモリ領域

概念赤黒木（Red-Black Tree）では、あるノードにおける最大高さは、最小高さの2倍以下でなければなりません。したがって、与えられた二分探索木に対して、以下の性質を満たしているかどうかを検証する必要があります。検証すべき性質： すべてのノードについて、そのノードから最も遠い葉までの経路（最長経路）に含まれるノード数が、最も近い葉までの経路（最短経路）に含まれるノード数の2倍を超えないこと。例1：赤黒木になれないケース13    41 \    / \ 15  11 101 \   /    \ 17 61

概念与えられた二分木に対して、それがヒープの性質(ヒープ属性)を持っているかどうかを検証する必要があります。二分木がヒープであるためには、次の2つの条件を満たしていなければなりません。二分木が完全木であること(最後のレベルを除くすべてのレベルが埋まっている状態)。二分木のすべてのノードの値が、その子ノードの値以上であること(最大ヒープ(max-heap)を想定した場合)。例以下の例では、この木はヒープの性質を満たしています。一方、次の例はヒープの性質を満たしていません。アプローチ上記の2つの条件は、それぞれ別々に検証する必要があります。完全性の検証には isComplete(二分木が完全木かど

連結グラフが与えられたとき、そのグラフが2部グラフ(bipartite graph)であるかどうかを判定することを考えます。2部グラフとは、頂点集合を2つのグループに分割でき、すべての辺が必ず異なるグループの頂点同士を結ぶようなグラフのことです。言い換えると、隣接する頂点同士が常に異なる色になるように、グラフ全体を2色で塗り分けられるグラフです。例えば、次のような6頂点のグラフを考えてみましょう。この場合、出力は True(1)となります。このグラフは偶数長の閉路を持ち、2色での塗り分けが可能だからです。解き方のアプローチこの問題は、DFS(深さ優先探索)を用いて頂点を順番に彩色していくことで

概念 本記事のテーマは、与えられた文字列が「有効な数値」であるかどうかを検証する方法です。単純な整数だけでなく、小数点や「2e5」のような指数表記(e表記)を含む文字列も正しく判定できるようにします。 入力出力 str = 12.5true str = deffalse str = 2e5true str = 10e4.4false このように、12.5 や 2e5(指数表記)は数値として有効ですが、def のような英字のみの文字列や、10e4.4 のように e の後ろに小数点が含まれる文字列は無効と判定されます。 判定のアプローチ 文字列が有効な数値かどうかを判定するには、コー