C++

問題概要ある企業が、最も優秀な社員の一人に対して、リソース収集のためにN個の都市を巡る旅を与えることになりました。とはいえ、社員にも休暇は必要です。本問題では、特定の都市・特定の週でのみ休暇を取得できるという条件のもと、移動スケジュールを工夫して取得できる休暇日数を最大化することを目指します。ただし、以下のルールと制約を守る必要があります。ルールと制約移動範囲：移動できるのはN個の都市のみです（インデックスは0〜N-1）。最初は月曜日にインデックス0の都市にいます。フライト情報：都市同士はフライトで結ばれており、その状態はN×Nの行列flightsで表されます（必ずしも対称行列ではありません）

問題概要n個の整数からなる配列が与えられたとき、長さがk以上の連続する部分配列の中で平均値が最大になるものを見つけ、その最大平均値を出力してください。例として、入力が [1, 12, -5, -6, 50, 3]、k = 4 の場合を考えてみます。長さ4の場合の最大平均値：12.75（例：[12, -5, -6, 50] の和は51、51 ÷ 4 = 12.75）長さ5の場合の最大平均値：10.8（例：[12, -5, -6, 50, 3] の和は54、54 ÷ 5 = 10.8）長さ6の場合の最大平均値：9.16667（配列全体の和は55、55 ÷ 6 ≒ 9.16667）これらを比較すると

問題の概要N個の数値 A1, A2, ..., AN を含む配列A（インデックスは1から開始）と、整数Bが与えられます。整数Bは、配列Aの任意のインデックスiから、i+1、i+2、…、i+B のいずれかの位置へジャンプできることを意味します。ただし、インデックスiに着地するには Ai 枚のコインを支払う必要があり、Ai が -1 の場合、その位置にはジャンプできません。配列Aのインデックス1から出発し、できるだけ少ないコインでインデックスNに到達することが目的です。最小コストでゴールへたどり着くためのインデックスの経路（1からN）を返してください。同じコストの経路が複数存在する場合は、辞書順で

問題の概要 整数 n が与えられたとき、次の操作を行った結果として得られる n 番目の整数を返します。まず 1 から始まる整数列を用意し、9 を含む整数(9、19、29 …)をすべて取り除きます。こうしてできる新しい整数列は、1、2、3、4、5、6、7、8、10、11 … となります。ここで、先頭の整数が 1 である点に注意してください。 たとえば、入力が 9 であれば出力は 10 になります。 解法の考え方 この問題は一見複雑そうですが、実は「9 を含まない整数列」の構造を利用すると、非常にエレガントに解くことができます。 9 を含まない正整数を順番に並べると、それは各桁が 0〜8 のみで

問題概要 1からNまでの番号が付けられたN個の電球が一列に並んでおり、最初はすべて消えています。毎日ちょうど1個の電球を点灯させ、N日後にはすべての電球が点灯状態になるとします。長さNの配列 bulbs が与えられ、bulbs[i] = x は「(i+1) 日目に位置 x の電球を点灯させる」ことを表します。さらに整数 K が与えられたとき、「点灯している2つの電球の間に、消えたままの電球がちょうど K 個挟まれている」という状況が初めて成立する日の番号（最小値）を求めます。そのような日が存在しない場合は -1 を返してください。 例として、入力が bulbs = [1,3,2]、K = 1

問題概要 空でない2次元バイナリ配列 grid が与えられます。ここでいう「島」とは、上下左右の4方向に連結した 1（陸地を表す）の集合のことであり、グリッドの四辺はすべて水に囲まれているものと仮定します。 求めるのは異なる島の数です。ある島が別の島と同じとみなされるのは、両者が同じ形状である場合、または90度・180度・270度のいずれかで回転した後、あるいは左右方向・上下方向のいずれかで反転した後に同じ形状になる場合です。 例として、入力が次のようなケースを考えます。 11000100000000100011 この場合の出力は 1 になります。左上のL字形の島と右下のL字形の島は、回転させ

2つの文字列 S と T が与えられたとき、「T が部分列（サブシーケンス）として含まれる」ような S の最短の部分文字列 W を求める問題を考えてみましょう。S の中に T のすべての文字をカバーできるウィンドウが存在しない場合は空文字列を返し、条件を満たすウィンドウが複数ある場合は、開始位置が最も左側にあるものを返します。たとえば、入力が S = abcdebdde、T = bde の場合、出力は bcde になります。これは bdde よりも先に出現するためです。また、deb が答えにならないのは、ウィンドウ内で T の文字が必ず順序どおりに現れる必要があるからです。アルゴリズムの考え方

従業員の勤務スケジュールのリストが与えられているとします。このリストは各従業員の勤務時間を表しています。各従業員は互いに重ならない区間（インターバル）のリストを持ち、それらはすでにソート済みです。ここでの課題は、すべての従業員に共通する「正の長さを持つ空き時間（フリータイム）」を表す有限区間のリストを求め、その結果もソートされた順序で返すことです。 区間は [x, y] の形式で表現します。たとえば schedule[0][0].start = 1、schedule[0][0].end = 2 のように指定します。 入力が schedule = [[[1,2],[5,6]],[[1,3]],

問題概要 数式を表す文字列が与えられ、その式を評価する基本的な電卓を実装することを考えます。式の文字列には、開き括弧と閉じ括弧、加算「+」や減算「-」の記号、非負の整数、そして空白が含まれる可能性があります。つまり、式には非負の整数と「+」「-」「*」「/」の各演算子、開き括弧・閉じ括弧、空白のみが登場します。整数同士の除算では、結果をゼロ方向へ切り捨てるものとします。 例として、入力が「6-4 / 2」であれば、出力は 4 になります。 アルゴリズムの考え方 この問題は、スタックを活用して優先順位の異なる2種類の演算子(加減算レベルと乗除算レベル)を管理することで解けます。使用する変数の

問題概要一本の数直線上にガソリンスタンドがいくつか建っていると考えます。スタンドの位置は stations[0], stations[1], ..., stations[N-1](N は配列の要素数)として与えられます。この状態からさらに K 個のガソリンスタンドを好きな位置に追加し、隣接するスタンド同士の距離の最大値 D をできるだけ小さくしたいとします。目的は、この D の取り得る最小値を求めることです。たとえば、stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]、K = 9 が入力された場合、出力は 0.5 になります。各区間の長さはすべて 1 なので、

整数の配列 A が与えられたとき、「部分配列の左端の要素が、その部分配列内の他のすべての要素以下である」という条件を満たす、空でない連続した部分配列の個数を求めます。 例えば、入力が [1,4,2,5,3] の場合、出力は 11 になります。条件を満たす部分配列は次の 11 個です。 [1], [4], [2], [5], [3], [1,4], [2,5], [1,4,2], [2,5,3], [1,4,2,5], [1,4,2,5,3] 解法のアプローチ:単調スタック この問題は「単調スタック(増加スタック)」を使うことで効率的に解けます。各要素を処理する際、スタックの先頭にある自分より大

問題の概要 0〜9のいずれかの整数 d と、2つの正整数 low・high（それぞれ下限・上限）が与えられます。求めたいのは、low 以上 high 以下のすべての整数を並べたときに、数字 d が合計で何回現れるかです（両端の値も含みます）。 例として、d = 1、low = 1、high = 13 という入力を考えてみましょう。この場合の出力は 6 になります。1, 10, 11, 12, 13 の中で数字「1」は 1回＋1回＋2回＋1回＋1回＝計6回現れるためです。 解法のアプローチ low から high までの数を1つずつ調べる方法では、範囲が大きくなると計算量が膨大になってしまいま

問題の概要ある数字を180度回転させると、別の数字へと変化することがあります。具体的には、0、1、6、8、9を180度回転すると、それぞれ0、1、9、8、6になります。一方で、2、3、4、5、7は回転させると無効な数字になってしまいます。この性質を使った「紛らわしい数（Confusing Number）」とは、180度回転させると元の数とは異なる新しい数になる数のことです。正の整数Nが与えられたとき、1以上N以下の範囲に存在する紛らわしい数の個数を求めるのがこの問題です。例えば、入力が20の場合、出力は6となります。これは、6→9、9→6、10→1、16→91、18→81、19→61 の6つが

w × h のサイズを持つ行列 M を考えます。すべてのセルの値は 0 または 1 であり、サイズ l × l の任意の正方形部分行列に含まれる 1 の数は maxOnes 個以下でなければなりません。このとき、行列 M に含めることができる 1 の最大数を求める必要があります。例えば、入力が w = 3、h = 3、l = 2、maxOnes = 1 の場合、出力は 4 になります。3 × 3 の行列では、どの 2 × 2 の部分行列にも 1 は 1 個までしか含められないためです。1 を 4 個配置できる最適な解は以下の通りです。101000101解法のアプローチこの問題の鍵となるのは、行

ブロックのリストがあるとします。blocks[i] = t の場合、i 番目のブロックを構築するには t 単位の時間が必要です。1つのブロックは、必ずちょうど1人の作業員だけが担当できます。各作業員は「2人の作業員に分割する」か「ブロックを1つ構築して退場する」のいずれかの行動を選択でき、それぞれの決断には一定の時間がかかります。作業員を2人に分割するときのコストは、split という数値として与えられます。問題例たとえば、blocks = [1, 2]、split = 5 という入力の場合、出力は 7 になります。これは、まず 5 単位の時間をかけて作業員を2人に分割し、それぞれにブロックを

問題の概要文字列 s と整数 k が与えられたとき、その文字列が「K-回文（K-Palindrome）」であるかどうかを判定します。K-回文とは、文字列から最大 k 文字を削除することで回文（前から読んでも後ろから読んでも同じ文字列）に変換できる文字列のことです。例えば、入力が s = abcdeca、k = 2 の場合、「b」と「e」を削除すると「acdca」となり回文になるため、出力は true になります。解法のアプローチ：最長共通部分列（LCS）を利用この問題は、最長共通部分列（LCS：Longest Common Subsequence）を使うことで効率的に解けます。考え方のポイント

問題の概要いくつかのチャンク(欠片)からなる1本のチョコレートバーがあるとします。各チャンクには固有の甘さがあり、それらは sweetness というリストで与えられます。このチョコレートを K 人の友人と分け合うため、K 回のカットで K+1 個のピースに切り分けます。各ピースは連続したチャンクで構成され、その中で合計甘さが最小のピースを自分が受け取ることになります。ここで求めたいのは、チョコレートバーを最適に切り分けたときに、自分が得られるピースの合計甘さの最大値です。例えば、入力が sweetness = [1,2,3,4,5,6,7,8,9]、K = 5 の場合、出力は 6 になります

問題概要 整数配列 arr が与えられます。1回の操作では、インデックス i から j（i <= j）までの範囲にある「回文」となる部分配列を選んで削除することができます。ここで注意したいのは、部分配列を削除した後、その左右にあった残りの要素が移動して、削除によって生じた隙間を自動的に埋めるという点です。このとき、配列からすべての数値を取り除くために必要な最小の操作回数を求めるのが本問題の目的です。 例として、入力が arr = [1,3,4,1,5] の場合を考えてみましょう。このときの出力は 3 になります。具体的には、「[4] を削除」→「[1,3,1] を削除」→「[5] を削除

円形に並んだ偶数 n 人の人々が、それぞれ別の誰かと握手をします。このとき、握手は全部で n / 2 回行われることになります。ここで求めたいのは、どの握手同士も互いに交差しないような握手の組み合わせが何通りあるかという数です。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。例えば、入力が n = 2 の場合、出力は 1 になります。解法のアプローチこの問題は、有名なカタラン数（Catalan number）と同じ構造を持っています。動的計画法（DP）を使うことで効率的に解くことができます。考え方のポイントは次の通りです。ある1人の人が誰かと握手すると、そ

リンクリストを削除する関数とは 本記事では、C++でリンクリストの全要素を先頭から順に1つずつ解放し、リンクリスト全体を削除する関数の作成方法を解説します。 C/C++には、この操作専用の組み込み関数は用意されていません。そのため、確保したメモリはプログラマ自身が明示的に解放しなければなりません。一方、Javaでは自動ガベージコレクション(GC)が不要になったオブジェクトを自動的に回収するため、リンクリストの削除を意識する必要がありません。これは両言語のメモリ管理における大きな違いの一つです。 deleteLinkedList関数の処理の流れ ポインタの準備: 現在処理中のノードを指すcur