C++

問題の概要 連結リスト（リンクリスト）が与えられたとき、マージソートのアルゴリズムを用いて昇順にソートします。 List: 10->20->8->17->5->13->4 Sorted list: 4->5->8->10->13->17->20 アルゴリズム headがNULL、またはリストの要素数が1つだけの場合は、そのリストをそのまま返します。 元のリストを中央で2分割し、2つのリストを作成します。 前半と後半のリストをそれぞれ再帰的にソートします。 ソート済みの2つのリストをマージ（統合）します。 C++による

問題概要双方向連結リスト（ダブリーリンクリスト）が与えられたとき、マージソート（merge sort）アルゴリズムを使って昇順に並べ替えます。元のリスト: 10->20->8->17->5->13->4ソート後のリスト: 4->5->8->10->13->17->20双方向連結リストは各ノードが「前」と「次」へのポインタを持つため、通常の片方向リストと異なり、マージ処理の際に prev ポインタも正しく更新する 必要がある点に注意しましょう。アルゴリズムの手順1. 先頭ポインタが NULL、またはリストの要素数が1つだけな

問題の概要任意の順序で与えられた時間区間（インターバル）の集合から、重なり合うすべての区間を1つに統合し、互いに重複しない区間だけを出力するのがこの問題の目的です。たとえば、区間の集合 {{12, 14}, {11, 13}, {20, 22}, {21, 23}} が与えられた場合、次のように処理されます。{12, 14} と {11, 13} は互いに重なっているため、{11, 14} にマージされます。{20, 22} と {21, 23} も互いに重なっているため、{20, 23} にマージされます。その結果、最終的な出力は {11, 14} と {20, 23} の2つの区間になりま

問題の概要大きさがそれぞれ m と n の2つの文字列 str1 と str2 が与えられたとします。ここで求めたいのは、str1 を str2 に変換するために必要な「削除」と「挿入」の操作回数を最小化するという課題です。例として、次のようなケースを考えてみましょう。Str1 = tutorialspoint Str2 = tutorials str1 を str2 に変換するには、5文字分の削除、つまり str1 から point を取り除く必要があります。解法の考え方:最長共通部分列(LCS)この問題は、最長共通部分列(Longest Common Subsequence:LCS) を利

問題の概要長さ n の文字列が与えられたとき、その文字列を回文にするために削除が必要な最小の文字数を求めるのがこの問題の目的です。たとえば、入力文字列が「abcda」の場合、先頭と末尾以外の2文字を削除すれば回文を作ることができます。「b」と「c」を削除すると → 「ada」(回文になります)「c」と「d」を削除すると → 「aba」(回文になります)「b」と「d」を削除すると → 「aca」(回文になります)アルゴリズムの考え方この問題は「最長回文部分列(Longest Palindromic Subsequence: LPS)」の考え方を使うと効率的に解けます。手順は次のとおりです。与えら

問題の概要整数型配列「arr」が与えられたとき、この配列を「良い配列」にするために削除する必要がある要素の最小数を求めるのが課題です。ここで「良い配列」とは、数列 a1, a2, a3, ... an の各要素 a[i] に対して、i ≠ j を満たす別の要素 a[j] が必ず存在し、a[i] + a[j] の和が2の累乗(べき乗)になるような配列のことを指します。具体例arr1[] = {1, 1, 7, 1, 5}上記の配列では、要素「5」を1つ削除するだけで配列は良い配列になります。削除後は、任意のペア arr[i] + arr[j] の和が2の累乗になります。arr[0] + arr[

問題の概要サイズ n の配列 arr と要素 x が与えられたとき、配列の中央値が x と等しくなるようにするために、配列へ追加すべき要素の最小個数を求めるのがこの課題です。ここで、長さ n の配列における中央値とは、要素を昇順（非減少順）にソートした際に (n-1)/2 番目の位置に存在する要素を指します。例えば、次の配列の場合、中央値は 20 となります。arr1[] = {10, 20, 30, 40}また、arr[] = {1, 2, 3}、x = 4 が与えられた場合を考えてみましょう。この場合、中央値を 4 にするためには {4, 5, 5, 5} の4つの要素を配列に追加する必要

問題概要数値 N が与えられます。1 から N までの要素の中からいくつかを取り除き、残った要素全体の XOR（排他的論理和）が最大になるようにします。このとき、取り除く必要がある要素の最小数を求めるのが課題です。アルゴリズムこの問題は、次の手順で効率よく解くことができます。1. n が 1 または 2 の場合は要素を削除する必要がないため、答えは 0 2. n 以上で最小の 2 のべき乗を求め、これを nextNumber とする 2.1. n == nextNumber または n == (nextNumber - 1) の場合、答えは 1 2.2. n == (nextNum

問題の概要 先頭にゼロが付かない数値 N が与えられます。この問題の目的は、N を 25 で割り切れるようにするために必要な移動（隣り合う 2 桁の入れ替え）の最小回数を求めることです。ただし、どの時点においても数値の先頭がゼロになってはいけません。どのように操作しても N を 25 の倍数にできない場合は、-1 を出力します。 例えば、N = 5071 の場合、25 で割り切れる状態にするには 4 回の移動が必要です。 5071 → 5701 → 7501 → 7510 → 7150 ポイント：25 の倍数の性質 ある整数が 25 で割り切れるのは、そ

問題の概要2つの文字列 str1 と str2 が与えられます。どちらの文字列も「a」と「b」のみで構成されており、長さは等しく、それぞれに1つの _（空きスペース）が含まれています。目標は、次の操作を最小回数だけ実行して、最初の文字列を2番目の文字列へ変換することです。_ が位置 i にあるとき、_ は位置 i+1 または i-1 の文字と入れ替えることができます。位置 i+1 と i+2 の文字が異なる場合、_ は位置 i+1 または i+2 の文字と入れ替えることができます。同様に、位置 i-1 と i-2 の文字が異なる場合、_ は位置 i-1 または i-2 の文字と入れ替えることが

問題の概要 サイズ N の配列が与えられます。この配列の各インデックスは「バケツ」を表しており、それぞれのバケツにはいくつかの荷物（アイテム）が入っています。ここで、K 回の配達ですべての荷物を届け終えるという条件が課されます。ただし、1 回の配達で荷物を取り出せるのは1 つのバケツからだけというルールがあります。 このとき、「すべての荷物を K 回以内で配達し切るために、1 回あたり最低何個の荷物を運べばよいか」を求めるのが本問題です。 具体例 バケツが 5 つあり、それぞれに入っている荷物の数が {1, 3, 5, 7, 9}、配達可能な回数が 10 回であるとします。この場合、1 回あ

問題概要整数 n が与えられ、アルファベットを a = 1、b = 2、c = 3、……、z = 26 というように数値に対応させます。このとき、対応する数値の合計がちょうど n になるようにするために必要な最小の文字数を求めるのが課題です。各文字が表せる最大の値は z = 26 であるため、必要な文字数は「n を 26 で割って切り上げた値」になります。入出力の例入力: n = 23 → 出力: 1 （w = 23 で表現できるため） 入力: n = 72 → 出力: 3 （26 + 26 + 20 = 72）アルゴリズム考え方は非常にシンプルです。1文字あたり最大 26 までの値を担当でき

問題の概要テストにN問の問題があり、クラスにはK人の生徒が在籍しています。このうちN人の生徒は、それぞれちょうど1問ずつ異なる問題を暗記しています。1通のメールに含められる問題数は最大X問です。クラス全員がすべての問題を把握できるようにするには、何通のメールが必要になるかを求めます。具体例N = 3、K = 3、X = 1 の場合、合計6通のメールを送る必要があります。生徒1が自分の問題を生徒2と生徒3に送信（2通）生徒2と生徒3も同様に、各自の問題を他の2人に送信合計メール数 = 2 × 3 = 6通アルゴリズム答えは次の式で計算できます。ceil(N/X) * (K-N) + ceil((

問題文N個の要素からなる配列と整数Kが与えられます。この配列に対して、以下の操作を何度でも繰り返し実行できます。配列のK番目の要素を配列の末尾に挿入し、同時に配列の先頭の要素を削除するこの操作を用いて、配列のすべての要素を等しくするために必要な最小の操作回数を求めるのが課題です。もしすべての要素を等しくすることが不可能な場合は、-1を出力してください。具体例配列 arr[] = {1, 2, 3, 4, 5, 6}、k = 6 の場合、最小5回の操作で全要素を等しくできます。操作1: {2, 3, 4, 5, 6, 6} 操作2: {3, 4, 5, 6, 6, 6} 操作3: {4, 5,

問題概要 AVL木の高さが与えられたとき、その木が取り得るノード数の最小値を求めるのが本問題の目的です。 高さ = 0 の場合、AVL木は最低でも1個のノードを持つ 高さ = 5 の場合、AVL木の最小ノード数は20 アルゴリズム AVL木では、すべてのノードにおいて左部分木と右部分木の高さの差が -1、0、1 のいずれかに収まっていなければならないという高さ平衡条件を維持する必要があります。この性質を利用すると、次のような漸化式を立てることができます。 1. 高さ = 0 のとき … 1 を返す 2. 高さ = 1 のとき … 2 を返す 3. 高さ > 1 のとき … 1 + get

問題の概要サイズNの配列が与えられ、各要素は「1」または「0」のいずれかです。この課題では、すべての要素を0に変換するために必要な最小操作回数を求めます。実行できる操作は以下のとおりです。ある要素が「1」である場合、その値を「0」に変更できます。このとき、次のような効果が発生します。隣接する次の要素が「1」であれば、その要素は自動的に「0」へ変換されます。隣接する次の要素がすでに「0」であれば、何も起こりません。例として、次の配列を考えてみましょう。arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1}この場合、すべての要素を0にするには 4

問題の概要整数型の配列 arr が与えられたとき、配列のすべての要素を削除するために必要な最小の操作数を求めるのが課題です。ただし、要素を削除する際には次の制約が課されます。配列から任意の要素を自由に選択でき、その要素で割り切れるすべての要素を一度に配列から削除できる。例えば、arr[] = {2, 4, 15, 10, 8, 5, 3} の場合、すべての要素を削除するには3回の操作が必要です。2 を選択すると、{2, 4, 10, 8} が削除されます。5 を選択すると、{5, 15} が削除されます。3 を選択すると、{3} が削除されます。アルゴリズム配列を昇順にソートし、各要素の出現回

問題の概要バイナリ文字列 str が与えられます。この文字列が表す数値を作り出すために必要な操作の最小回数を求めてください。実行できる操作は次の2種類のみです。2x を加算する2x を減算する例えば、バイナリ文字列が「1000」の場合、必要な操作は「23 を加算する」のたった1回だけです。一方、バイナリ文字列が「101」の場合は、「22 を加算する」と「20 を加算する」の計2回の操作が必要になります。解法のポイント一見すると、文字列に含まれる「1」の個数がそのまま答えのように思えるかもしれません。しかし、減算という操作を活用することで、より少ない操作回数で目的の数を作れるケースがあります。例

問題の概要Nページからなる本が与えられたとき、目的のページKに到達するために必要な最小のページめくり回数を計算するのがこの問題です。この問題には以下のルールがあります。ページめくりは、本の前側(1ページ目)から始めることも、後ろ側(Nページ目)から始めることもできます。各ページは表と裏の2面を持っています。ただし、最初のページは裏面のみ、最後のページも本の総ページ数によっては裏面のみの場合があります。具体例N = 5、K = 4 の場合を考えてみましょう。このとき最小のページめくり回数は 1回 となります。前からめくる場合: 2回必要です。(1) → (2, 3) → (4, 5)後ろからめく

問題の概要数値Nが与えられたとき、Nをいくつかの回文（上から読んでも下から読んでも同じ並びになる数）の和として表すために必要な回文の最小個数を求める問題です。例えば、N = 15の場合、15 = 8 + 7 と表現できるため、必要な回文の個数は2となります。アルゴリズムの考え方この問題は次の2つのステップで解くことができます。N以下のすべての回文を昇順に生成する和がちょうどNになるような最小の部分集合のサイズを求める後半のステップはいわゆる「部分和問題」の一種であり、メモ化再帰（動的計画法）を用いることで効率的に解けます。回文の効率的な生成方法すべての数値に対して回文かどうかを1つずつ判定する