C++

N分木(N-ary tree)を与えられたとき、それをシリアライズ(直列化)し、さらにデシリアライズ(復元)する必要があります。シリアライズとは、データ構造やオブジェクトをビット列に変換する処理のことで、これによりファイルやメモリバッファに保存でき、後で同じ環境または別のコンピュータ環境で元の構造を再構築できます。ここでは、N分木をシリアライズ・デシリアライズするためのアルゴリズムを設計します。N分木とは、根付き木(rooted tree)の一種で、各ノードが持つ子ノードの数がN以下である木のことです。例えば、次のような入力が与えられた場合を考えます。この場合、出力は次のようになります。シリア

N分木（N-ary tree）を1本の二分木へ変換（エンコード）することを考えてみましょう。あわせて、エンコード済みの二分木を元のN分木へ復元（デコード）する機能も実装します。 たとえば、次のような入力が与えられたとします。 このとき、出力は次のようになります。 解法のアプローチ：左子・右兄弟表現 この問題は「左子・右兄弟表現（Left-Child Right-Sibling Representation）」と呼ばれる古典的な手法で解くことができます。考え方はシンプルで、N分木の最初の子を二分木の左の子に対応させ、2番目以降の兄弟ノードを順番に右の子として連結していきます。これにより、任

友人のグループが休暇に出かけ、旅先で互いにお金を貸し借りしていたとしましょう。例えば、AmitさんがBikramさんの昼食代として10ドルを立て替えました。その後、ChandanさんがAmitさんにタクシー代として5ドルを渡しました。このように、各取引をタプル(x, y, z)――つまり「人物xが人物yにzドル支払った」――という形で表現するモデルを設計することを考えます。 Amit、Bikram、Chandanをそれぞれ人物0、1、2とすると、上記の取引は [[0, 1, 10], [2, 0, 5]] と表せます。グループ内のメンバー間の取引リストが与えられたとき、すべての債務を清算する

問題概要空でない2つの文字列 s1・s2(それぞれ最大100文字)と、0以上106以下の範囲にある2つの整数 n1・n2 が与えられます。ここで S1 = [s1, n1]、S2 = [s2, n2] とおきます。S = [s, n] は「文字列 s を n 個連結した文字列」を表します。たとえば [ab, 4] は abababab です。さらに、文字列 s2 からいくつかの文字を取り除くことで s1 が得られるとき、「s1 は s2 から取得できる」と定義します。この定義では、abc は abdbec から取得できますが、acbbe からは取得できません。目的は、[S2, M] が S1

問題概要空でない文字列が与えられます。この文字列を、エンコード後の長さが最小になるようにエンコードすることを考えましょう。エンコードの規則は k[encoded_string] という形式です。これは、角括弧内の encoded_string がちょうど k 回繰り返されることを意味します。ただし、以下の条件があります。k は正の整数であることencoded_string は空であってはならず、余分な空白も含めない入力文字列には小文字の英字のみが含まれると仮定できるエンコードしても文字列が短くならない場合は、エンコードを行わない例えば、入力が aaaaa の場合、出力は 5[a] となります。

問題概要文字列 s と、すべて同じ長さの単語からなるリスト words が与えられたとします。このとき、s の中に存在する部分文字列のうち、words に含まれる各単語をちょうど1回ずつ、間に余計な文字を挟まずに連結したものに一致するものを探し、その開始インデックスをすべて求めます。たとえば、入力が barfoothefoobarman、単語リストが [foo, bar] の場合、出力は [0, 9] となります。これは、インデックス 0 から始まる部分文字列が barfoo、インデックス 9 から始まる部分文字列が foobar であり、いずれも bar と foo を1回ずつ連結した形にな

問題の概要 空きスペースと壁からなる迷路の中に、ボールが1つ置かれています。ボールは空きスペース上を上（u）・下（d）・左（l）・右（r）のいずれかの方向に転がって移動できますが、壁にぶつかるまで停止しません。ボールが停止した時点で、次の方向を選択できます。また、迷路内には穴（hole）が1つあり、ボールが穴の位置まで転がると、その穴に落ちます。 ボールの初期位置・穴の位置・迷路の情報が与えられたとき、ボールを最短距離で穴に落とすための移動手順を求めます。ここでいう距離とは、スタート地点（含まない）から穴（含む）までにボールが通過した空きスペースの数として定義されます。 移動方向は「u」「d

問題概要サイズが n × 3 のグリッドがあり、すべてのマスを赤・黄・緑の3色のうちちょうど1色で塗ることを考えます。ここで重要な制約として、隣り合うマス（上下・左右）同士は同じ色にできないというルールがあります。行数 n が与えられたとき、この条件を満たしながらグリッド全体を塗る方法が何通りあるかを求めます。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返してください。例えば、入力が 1 の場合、出力は 12 になります。解法のアプローチこの問題は、各行の塗り方を状態として管理する動的計画法（DP）で効率的に解けます。手順は以下のとおりです。法 m を 10^9

問題概要 3つの整数 n、m、k が与えられます。正の整数からなる配列の最大要素を求めるために、次のようなアルゴリズムが用意されています。 max_val := -1 max_ind := -1 search_cost := 0 n := size of arr for initialize i := 0, when i < n, update (increase i by 1), do:     if max_val < arr[i], then:        &nbs

本記事では、正の整数のみで構成された二分木が与えられたとき、隣接するレベルのノードを同時に合計に含めないという条件を満たす最大合計を求めるプログラムを、C++で解説します。 問題の内容 ここで扱うのは、木の中からいくつかのノードを選び、その値の合計を最大化する問題です。ただし、選んだノードが隣接する2つのレベル（親子関係にある階層）にまたがることはできません。あるレベルのノードを合計に採用したら、その直上・直下のレベルのノードは一切使用できない、という制約があります。 具体例で理解する 次のような二分木を例に考えてみます。 5 / \ 2 1

この記事では、サイズ N の3つの配列 arr1[]、arr2[]、arr3[] が与えられたとき、「同じ配列からは連続して要素を選べない」という制約のもとで、合計の最大値を求めるプログラムをC++で作成する方法を解説します。問題の概要N個の要素を選んで合計を最大化します。i 番目に選べる要素は、各配列の i 番目の要素、すなわち arr1[i]、arr2[i]、arr3[i] のいずれか1つです。重要な制約として、隣り合う位置で同じ配列から2回続けて要素を選ぶことはできません。具体例で問題を確認してみましょう。入力例arr1[] = {5, 8, 9, 20}, arr2[] = {7, 1

この問題では、サイズ 2 × n の長方形グリッドが与えられます。縦・横・斜めのいずれの方向にも隣接しないように要素を選んだときの最大合計を求めるプログラムを、C++で作成していきましょう。 問題の概要 最大合計を求めるにあたっては、現在注目している要素に対して、縦・横・斜めのどの方向で隣接している要素も一緒に選択することはできません。 具体例で問題を確認してみましょう。 入力 rectGrid[2][] = {{3, 8, 9}, {4, 1, 1}} 出力 13 解説 考えられるすべての選び方とその合計は、以下のようになります。 rectGrid[0][

問題の概要本記事では、循環配列 cirArr[] が与えられたとき、「どの2つの要素も隣接して選ばない」という条件を満たす要素の最大合計を求めるプログラムをC++で作成します。問題の詳細循環配列に対して、隣接する要素を同時に選ぶことができない、つまり要素を一つ飛ばしで選択した場合の最大合計を求める必要があります。循環配列とは、配列の末尾の要素が先頭の要素につながっている特殊な配列構造のことです。具体例で問題を確認しましょう。入力例cirArr[] = {4, 1, 5, 3, 2}出力例9解説最大の合計となる循環部分列は [4, 5, 2] で、その合計は 9 になります。解決アプローチこの問

はじめにこの記事では、動的計画法（Dynamic Programming：DP）を活用して「最大和増加部分列（Maximum Sum Increasing Subsequence：MSIS）」を求めるC++プログラムについて詳しく解説します。この問題では、N個の整数を含む配列が与えられます。私たちのタスクは、配列の中から要素を選び出し、その合計値を最大化することです。ただし、選んだ要素は元の配列内での並び順を保ちながら、厳密に増加している（昇順に並んでいる）必要があります。問題のポイント「増加部分列」とは、元の配列の相対的な順序を崩さずに取り出した要素の列であり、かつ各要素が直前の要素よりも大

この問題では、N個の整数からなる配列 arr[] と、2つのインデックス x・y が与えられます。求めるのは「インデックス x までのプレフィックスから選んだ増加部分列の最大和」であり、プレフィックスより後ろにあるインデックス y の要素を必ず部分列に含める必要があります。 問題の概要 インデックス x までの範囲で増加部分列の最大和を求め、そのうえでインデックス y の要素を必ず含めます。 具体例で問題を確認しましょう。 入力 arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6 出力 26 説明 インデックス 3 までの部分列を選び、最

この記事では、N個の要素からなる配列 arr[] が与えられたとき、C++のBinary Indexed Tree（BIT、フェニック木）を活用して、最大和増加部分列（Maximum Sum Increasing Subsequence）を求めるプログラムの作成方法を解説します。問題例で理解しよう入力arr[] = {4, 1, 9, 2, 3, 7}出力13解説この場合、最大の和を持つ増加部分列は「1, 2, 3, 7」であり、その合計は 1 + 2 + 3 + 7 = 13 となります。解法のアプローチこの問題を効率的に解くために、Binary Indexed Tree（BIT）を使用しま

この記事では、与えられた配列の要素を並べ替えたときに、隣接する要素同士の絶対差の合計が最大になる値を求めるプログラムをC++で実装する方法を解説します。 問題の概要 与えられた配列の要素からすべての順列を生成し、各順列について隣接要素間の絶対差の合計を計算します。そして、それらの合計の中で最大となる値を答えとして返します。なお、ここでは配列を環状とみなし、末尾の要素と先頭の要素の差も合計に含めます。 具体例を使って問題を理解しましょう。 入力 arr[] = {9, 1, 6, 3} 出力 22 説明 配列 {9, 1, 6, 3} の順列の一つ {9, 3, 6, 1} を見てみま

本記事では、数値 N が与えられたとき、C++ を用いて「隣接する要素の差の絶対値の合計」が最大となる値（maxSum）を求める方法を解説します。 問題の概要 1 から N までの整数で作られるすべての順列を対象に、隣接する要素同士の差の絶対値を合計し、その最大値を求めるのが目的です。 入力例 N = 4 出力例 7 解説 N = 4 の場合、考えられるすべての順列（4! = 24 通り）について、隣接要素の差の絶対値の合計を計算すると以下のようになります。 {1, 2, 3, 4} → 1 + 1 + 1 = 3 {1, 2, 4, 3} → 1 + 2 + 1 = 4 {1, 3,

この記事では、与えられた整数Nに対して、それらの数の最小公倍数（LCM）がNとなるような相異なる数を選んだときの合計の最大値を求めるプログラムを、C++で実装する方法を解説します。問題の概要一見複雑に思えるこの問題ですが、実は答えは「Nのすべての約数の合計」になります。なぜなら、Nの約数全体を集めた集合の最小公倍数は必ずNとなり、これ以上大きい合計は得られないからです。したがって、Nの相異なる約数をすべて足し合わせた値が最大合計となります。具体例を使って問題を確認してみましょう。入力N = 12出力28説明N = 12 の相異なる約数は 1, 2, 3, 4, 6, 12 の6つです。 合計

本記事では、整数Nが与えられたとき、最小公倍数(LCM)がNとなる相異なる数の組の中で、その総和が最大になる値を求めるプログラムをC++で作成します。 問題の概要 ここでの課題は、Nを最小公倍数(LCM)として持つ数の組み合わせの中から、和が最大になるものを見つけ出すことです。 具体例で問題を確認してみましょう。 入力 N = 10 出力 18 説明 LCMが10となる最大の和は 1 + 2 + 5 + 10 = 18 10を最小公倍数とする数の組み合わせはいくつか存在しますが(例：2と5、1と10など)、その中でも10のすべての約数 {1, 2, 5, 10} を使った場合に和が最大となり、