C++

この問題では、n個の整数で構成される配列 arr[] が与えられます。目的は、値が互いに異なる任意の2つの要素を選んだときに、そのインデックス間の差の最大値を求めることです。問題の概要ここで必要なのは、配列内の整数値の中から「異なる値を持つ2つの要素」を選び、それらのインデックスの差が最大になる組み合わせを見つけることです。入力例arr[] = {4, 1, 3, 2, 1, 2, 4}出力例5説明インデックス0の要素「4」と、インデックス5の要素「2」を比較すると、インデックスの差は 5 − 0 = 5 となり、これが最大値となります。解法のアプローチこの問題は、各要素を先頭の要素 a[0]

問題概要二分木が与えられ、木のノードにカメラを設置することを考えます。あるノードに置かれたカメラは、その親ノード・自分自身・子ノードの3つを監視することができます。このとき、木のすべてのノードを監視するために必要となるカメラの最小台数を求めるのが本問題の目的です。例えば、入力が下図のような木だった場合を考えてみましょう。この場合の出力は 1 になります。わずか1台のカメラで、すべてのノードを監視できるからです。解法のアプローチこの問題は、葉に近いノードから順に判断していく貪欲法（グリーディー法）と再帰を組み合わせることで、効率的に解くことができます。基本的な考え方は「子孫側でカバーできるなら親

本記事では、C++を使って線分の中点（ミッドポイント）を求めるプログラムの作成方法を解説します。線分の始点Aと終点Bの2つの座標が与えられたとき、その中点を計算するアルゴリズムについて学びましょう。 問題の概要 始点A(x1, y1)と終点B(x2, y2)で構成される線分があります。この線分の中点を求めるのが課題です。 入力例 a(x1, y1) = (4, -5) b(x2, y2) = (-2, 6) 出力例 (1, 0.5) 計算の説明 (x1 + x2)/2 = (4 + (-2)) / 2 = 1 (y1 + y2)/2 = (-5 + 6) / 2 = 0.5 解決アプローチ：中

この記事では、n個の整数からなる配列 arr[] が与えられたとき、その中から最小値と最大値を見つけるC++プログラムの作成方法を解説します。 問題の概要 ここでは、n個の整数値を含む配列 arr[] が与えられます。配列内のすべての値の中から、最大値と最小値を求めることが課題です。 具体例で問題を確認しましょう。 入力 arr[] = {2, 1, 6, 9, 4, 10, 15, 21} 出力 max = 21 , min = 1 解法アプローチ この問題には複数の解き方があります。まず基本となるのは、配列の要素同士を直接比較する方法です。各要素を順番に確認しながら、比較によって最大値と最

問題の概要配列 A が与えられたとします。任意の開始インデックスから出発し、一連のジャンプを行うことを考えます。このとき、系列の中で1回目・3回目・5回目…にあたるジャンプを奇数番目のジャンプ、2回目・4回目・6回目…にあたるジャンプを偶数番目のジャンプと呼びます。インデックス i から前方のインデックス j（i < j）へは、以下のルールでジャンプできます。奇数番目のジャンプの場合： A[i] <= A[j] を満たすインデックス j のうち、A[j] が最小となるものへ移動します。該当する j が複数ある場合は、最も小さいインデックス j を選びます。偶数番目のジャンプの場合：

問題の概要 2次元のグリッドが与えられ、各マスは次の4種類のいずれかで表されます。 1 … スタート地点(必ず1つだけ存在します) 2 … ゴール地点(必ず1つだけ存在します) 0 … 自由に移動できる空きマス -1 … 通ることができない障害物 求めるのは、スタートからゴールまで、障害物以外のすべてのマスをちょうど1回ずつ通るような、上下左右4方向への移動による経路の総数です。 入力例 1000 0000 102-1 この場合の出力は 2 となります。条件を満たす経路は次の2通りです。 (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (1,2) →

問題概要 二分木が与えられ、その根ノードに対して先行順（プレオーダー）の深さ優先探索を実行することを考えます。 この走査では、各ノードを訪問するたびに、まずそのノードの深さDと同じ数だけダッシュ「-」を出力し、その直後にノードの値を表示します。深さがDのノードの直接の子の深さはD+1となり、根ノードの深さは0です。 さらに重要なルールとして、あるノードに子が1つしか存在しない場合、その子は必ず左の子であることが保証されています。この走査の出力文字列Sが与えられたとき、元の二分木を復元し、その根を返すのが本問題です。 例えば、入力が「1-2--3--4-5--6--7」の場合、復元される木は次

問題の概要パズル文字列が与えられたとき、ある単語が「有効」であるためには、次の2つの条件を満たす必要があります。単語がパズルの先頭の文字を含んでいること単語を構成するすべての文字が、パズルにも含まれていることたとえば、パズルが「abcdefg」である場合、「face」や「cabbage」は有効な単語です。一方、「beefed」は「a」を含まないため無効であり、「based」はパズルに存在しない「s」を含むため無効となります。ここでの課題は、答えのリスト answers を求めることです。answers[i] は、単語リスト words の中で、パズル puzzles[i] に対して有効となる単

問題の概要サイズ arrLen の配列があり、インデックス 0 の位置にポインタが置かれています。各ステップごとに、ポインタを左に1マス移動するか、右に1マス移動するか、その場にとどまるかのいずれかを選択できます。ここで、整数 steps と arrLen が与えられたとき、ちょうど steps 回の操作を終えた時点でポインタが依然としてインデックス 0 に存在するような移動パターンの総数を求めます。答えが非常に大きくなる可能性があるため、10^9 + 7 で割った余りを返してください。たとえば、入力が steps = 3、arrLen = 2 の場合、出力は 4 になります。3 ステップ後に

問題の概要正方グリッド arr が与えられます。「非ゼロシフトの下降経路」とは、arr の各行からちょうど1つずつ要素を選び、かつ隣接する行で選んだ要素が同じ列にこないようにする選び方のことです。本問題では、このような下降経路の中で、選んだ要素の合計が最小となる値を求めます。たとえば、入力が arr = [[1,2,3],[4,5,6],[7,8,9]] の場合、出力は 13 になります。考えられる下降経路は [1,5,9]、[1,5,7]、[1,6,7]、[1,6,8]、[2,4,8]、[2,4,9]、[2,6,7]、[2,6,8]、[3,4,8]、[3,4,9]、[3,5,7]、[3,5,

問題概要m × n のグリッドが与えられます。各セルは 0 または 1 のいずれかの値を持ち、0 は空きセル、1 は障害物(ブロックされたセル)を表します。1 ステップごとに、現在いる空きセルから上下左右のいずれかの方向へ移動できます。「最大 k 個までの障害物を除去できる」という条件下で、左上隅のセル (0, 0) から右下隅のセル (m-1, n-1) まで移動するために必要な最小ステップ数を求めてください。到達可能な経路が存在しない場合は -1 を返します。入力例000110000011000このグリッドに対して k = 1 を与えたとき、出力は 6 になります。障害物をまったく除去しな

問題概要 n個の箱があり、各箱は [status, candies, keys, containedBoxes] の形式で以下の情報を持つものとします。 status[i]：box[i] が開いていれば 1、閉じていれば 0 candies[i]：box[i] に入っているキャンディーの数 keys[i]：box[i] 内の鍵で開けられる箱のインデックスの配列 containedBoxes[i]：box[i] の中に入っている箱のインデックスの配列 まず initialBoxes 配列で指定された箱からスタートします。開いている箱からはすべてのキャンディーを取り出せ、その中の鍵を使って新し

問題の概要文字が書かれた正方形のマス目(ボード)を考えます。スタート地点は右下の「S」とマークされたマスで、ゴールは左上の「E」とマークされたマスです。それ以外のマスには、1〜9の数字か、障害物を表す「X」が書かれています。1回の移動では、移動先に障害物がない場合に限り、「上」「左」「左上」のいずれかに進むことができます。求めるのは、次の2つの要素からなるリストです。通過したマスの数字を集めたときに得られる最大の合計値その最大合計を実現する経路の本数答えは 10^9 + 7 で割った余りとして返します。経路が1つも存在しない場合は [0, 0] を返します。例として、board = [E12,

覆面算パズルとは？ 覆面算（ふくめんざん）とは、数式内の数字をアルファベットなどの記号に置き換えたパズルです。ここでは、等式の左辺を複数の単語（文字列）、右辺を結果の単語として表現したとき、その等式が以下のルールのもとで成立するかどうかを判定する問題を扱います。 文字と数字の対応： 各文字は 0〜9 のいずれか1桁の数字に割り当てられる。 一意性： 異なる文字には必ず異なる数字が割り当てられる。 先頭ゼロの禁止： words[i] および result を数値として読み取る際、先頭に 0 が来てはならない。 等式の成立： 左辺の数値の総和が右辺の数値と一致すること。 判定： 以上の条件を満た

問題の概要 文字列 S が与えられたとき、「ある文字列をそれ自身と連結した形（AA の形）」として表すことができる、異なる空でない部分文字列の個数を求めることを考えます。 たとえば入力が elloelloello の場合、出力は 5 になります。条件を満たす部分文字列の例としては、ll のほかに、ello、lloe、loel、oell のようなものが挙げられます。 アプローチ：ローリングハッシュ すべての部分文字列同士を直接比較すると非常に非効率なため、ここではローリングハッシュ（Rabin–Karp 法）を活用します。ウィンドウを1文字スライドさせるたびにハッシュ値を O(1) で更新でき

以下のようなキーボードレイアウトがあるとします。 ABCDEF GHIJKL MNOPQR STUVWX YZ 各大文字アルファベットは座標に配置されています。例えば、Aは(0,0)、Bは(0,1)、Pは(2,3)、Zは(4,1)にあります。与えられた単語を2本の指のみで入力する際の最小総移動距離を求めます。2地点(x1,y1)と(x2,y2)間の距離はマンハッタン距離 |x1-x2| + |y1-y2| で定義され、開始位置はキーボード上の任意の場所から始められます。 問題の例 入力が HAPPY の場合、出力は6となります。 H

x軸上に一次元の庭があるとします。庭の始点は位置0、終点は位置nです。庭には位置[0, 1, ..., n]に合計n + 1個の蛇口が設置されています。ここで、整数nと長さn + 1の整数配列rangesが与えられ、ranges[i]は「i番目の蛇口を開けると、範囲[i - ranges[i], i + ranges[i]]へ水をまける」ことを表します。この問題の目的は、庭全体に水を行き渡らせるために開く必要のある蛇口の最小本数を求めることです。どのように組み合わせても全域をカバーできない場合は、-1を返します。たとえば、入力がn = 5、ranges = [3, 4, 1, 1, 1, 0]

問題概要整数型の配列 nums が与えられます。この配列の「値」は、すべてのインデックス i（0 ≤ i ≤ n−2）における |nums[i] − nums[i+1]| の総和として定義されます。ここで n は配列のサイズです。私たちは配列内の任意の部分配列を選んで反転することができ、この操作は一度だけ実行できます。操作を行った後の最終的な配列の値として考えられる最大値を求めてください。たとえば、入力が [1, 5, 4, 2, 3] の場合、出力は 10 になります。解法のアプローチこの問題は、以下の手順に従って解くことができます。ret := 0、extra := 0 で初期化します。n

問題概要d日間でタスクのリストをスケジューリングすることを考えます。タスクには依存関係があり、i番目のタスクに取り掛かるためには、0 <= j < i を満たすすべてのタスク j を先に完了させておく必要があります。さらに、毎日最低1つはタスクを完了させなければなりません。スケジュール全体の難易度は、d日間の各日の難易度の合計として定義され、ある日の難易度は、その日に完了したタスクの中で最も高い難易度の値となります。ここで、整数型配列 taskDifficulty と整数 d が与えられます。i番目のタスクの難易度は taskDifficulty[i] です。スケジュール全体の難易

問題の概要整数型の配列 arr と整数 d が与えられます。1ステップごとに、インデックス i から次の場所へジャンプできます。右方向： i + x（ただし i + x < n、かつ x は 1 以上 d 以下）左方向： i - x（ただし i - x >= 0、かつ x は 1 以上 d 以下）ここで n は配列のサイズです。さらに重要な制約として、インデックス i から j へジャンプできるのは、arr[i] > arr[j] であり、かつ i と j の間にあるすべてのインデックス k に対して arr[i] > arr[k] を満たす場合のみです。つまり、より低