C++

この問題では、等差数列(AP)の公差を表す値 d が与えられます。この等差数列は、ある四角形のすべての内角を構成しており、C++で四角形の各角度を求めるプログラムを作成するのが課題です。問題の概要四角形の4つの内角は、公差 d を持つ等差数列の形で並んでいます。このとき、それぞれの角度の値を求める必要があります。具体的な例を使って問題を理解してみましょう。入力d = 15出力67.5, 82.5, 97.5, 112.5説明第1の角度:x 第2の角度:x + 15 第3の角度:x + 30 第4の角度:x + 45四角形の内角の合計は360度です。これを式に当てはめると、次のように計算できます

問題概要 0〜9の数字からなり、長さ m と n をもつ2つの配列を考えます。それぞれの配列は1つの数値を表しています。この2つの配列から数字を選び出し、全体で k 桁となる最大の数を作成することを目指します。ただし重要な制約として、同じ配列から選んだ数字同士の相対的な順序は保持しなければなりません。 たとえば、入力が [3,4,7,5] と [9,1,3,5,8,4]、k = 5 の場合、求める答えは [9,8,7,5,4] となります。 解法のアプローチ この問題は、次の3つの補助関数に分割すると見通しよく実装できます。 modify(v, k)：1つの配列から、順序を保ちながら k

問題概要整数配列 nums が与えられたとき、範囲 [lower, upper]（両端を含む）に収まる区間和の個数を求めます。ここで区間和 S(i, j) とは、i ≤ j を満たすインデックス i から j までの nums の要素の総和として定義されます。例えば、入力が [-3, 6, -1]、lower = -2、upper = 2 の場合、答えは 2 になります。条件を満たすのは [0, 2]（合計 2）と [2, 2]（合計 -2）の2つだけだからです。解法のアプローチ：累積和とマージソートの組み合わせこの問題は素朴に全ペアを調べると O(n²) かかりますが、累積和（プレフィックス

問題概要 高さと幅のペアで表される複数の封筒が与えられるとします。ある封筒が別の封筒の中に入ることができるのは、その封筒の高さと幅の両方が相手の封筒よりも厳密に小さい場合のみです。この条件下で、封筒を最大で何重に入れ子にできるかを求めるのが本問題です。 例えば、入力が [[5,5], [6,4], [6,8], [2,3]] の場合、出力は 3 になります。最も小さい封筒は [2,3] であり、その中に [5,5]、さらにその中に [6,8] を入れることで、合計3枚の封筒を入れ子にできるためです。 解法のアプローチ この問題は、ソートと最長増加部分列（LIS: Longest Increas

問題概要2次元行列と整数 k が与えられたとき、行列内の長方形領域のうち、その合計値が k を超えないものの中で最大の合計値を求めます。例として、次のような入力を考えてみましょう。1010-32このとき k = 3 であれば、緑色で示した長方形領域（1 + 2）の合計がちょうど 3 となり、これが答えになります。アルゴリズムの考え方この問題は、列の組み合わせごとに行方向の累積和を求め、二分探索（lower_bound）を使って条件を満たす最大値を効率よく探すことで解決できます。手順は以下の通りです。関数 maxSumSubmatrix() を定義し、2次元配列 matrix と整数 k を受け

本記事では、以下の3つの操作をすべてO(1)の計算量で実行できるデータ構造をC++で実装する方法を解説します。このデータ構造では、同じ値が複数回挿入されること（重複）が許可されている点がポイントです。 insert(x): コレクションに値 x を挿入する remove(x): コレクションから値 x を削除する getRandom(): コレクションからランダムに1つの要素を取得する アルゴリズムの考え方 これらの操作を高速に行うためには、「動的配列」と「ハッシュマップ」を組み合わせるのが有効です。具体的には、次の手順に従って実装します。 ペア（値, インデックス）を格納する配列 nu

問題概要 カエルが川を渡る場面を考えてみましょう。川は x 単位ごとの区間に分かれており、各区間には石がある場合があります。カエルは石の上に着地することはできますが、水面に落ちることは許されません。ここでは、石の位置を昇順にソートしたリストが与えられ、「カエルが最後の石に着地して川を渡り切ることができるかどうか」を判定します。初期状態ではカエルは最初の石の上におり、最初のジャンプは必ず 1 単位でなければならないものとします。 ジャンプのルール 直前のジャンプが k 単位だった場合、次のジャンプは k − 1 単位、k 単位、k + 1 単位 のいずれかでなければなりません。また、カエルは前

正の整数からなる配列と整数 m が与えられたとします。この配列を m 個の連続する部分配列に分割できるものとし、分割後の各部分配列の要素和の中で最大値が最小となるような分割方法を見つけるアルゴリズムを考案します。 例えば、配列が [7, 2, 4, 10, 9]、m = 2 の場合を考えてみましょう。[7, 2, 4] と [10, 9] の2つの部分配列に分割すると、それぞれの和は 13 と 19 になり、最大値は 19 となります。これがこの入力に対する最適な答えです。 解法のアプローチ:動的計画法(DP) この問題(LeetCode 410「Split Array Largest Sum

問題概要 2つの整数 n と k が与えられます。1から n までの範囲の整数を「辞書式順序」（数値の大小ではなく、文字列として比較した順序）で並べ替えたとき、k 番目に小さい整数を求めるのがこの問題です。 例えば、n = 14、k = 3 が入力された場合、答えは 11 になります。1から14までの数を辞書式順序で並べると [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9] となるため、3番目の数は 11 だからです。 解法のアプローチ この問題は、トライ（trie）木の構造をイメージしながら、各接頭辞（プレフィックス）の下にいくつの数が存在す

問題概要 N 個の数値を含む配列 A があるとします。この配列における部分列スライスとは、0 <= K0 < K1 < K2 < … < Kn < N を満たす整数列 (K0, K1, K2, …, Kn) のことを指します。 A[K0], A[K1], …, A[Kn] が公差一定の等差数列を成すとき（n >= 2）、その部分列スライスは等差スライス（算術スライス）と呼ばれます。本問題では、配列 A に含まれる等差スライスの総数を求めることが課題です。 入出力例 入力が [2,4,6,8,10] の場合、答えは 7 となります。次の 7 つの等差ス

ここに1000個のバケツがあるとしましょう。そのうち1つだけに毒が入っており、残りはすべて水が入っています。見た目はどれもまったく同じで、区別がつきません。毒を飲んだ豚は15分以内に死んでしまうため、1時間以内に毒の入ったバケツを特定するには、最低何頭の豚が必要でしょうか？ 問題の一般化 まず、この問題を一般化してみましょう。条件は次のとおりです。 n個のバケツがあり、そのうちちょうど1つに毒が入っている 毒を飲んだ豚は m 分以内に死ぬ p 分以内に毒のバケツを特定したい このとき必要な豚の最小頭数を求めるのが目標です。例えば n = 1000、m = 15、p = 60 の場合、答え

問題の概要互いに異なる単語からなるリストが与えられたとします。ここで求めたいのは、リストの中に含まれる連結語をすべて見つけるアルゴリズムです。連結語とは、同じリスト内にある少なくとも2つの短い単語を組み合わせて完全に構成できる文字列のことを指します。たとえば、単語リストが [cow, cows, cowsgoatcows, goat, goatcowsgoat, hippopotamuses, deer, deercowgoatcow] である場合、出力は [cowsgoatcows, goatcowsgoat, deercowgoatcow] となります。解き方のアプローチこの問題は、トライ

問題の概要 整数 n が与えられたとき、「2つの n 桁の数をかけ合わせて作ることができる最大の回文数」を求める問題を考えます。積は非常に大きな値になるため、結果は 1337 で剰余（mod）を取って返します。 例えば入力が 2 の場合、答えは 987 となります。これは次のような計算によるものです。 987 = (99 × 91) mod 1337 = 9009 mod 1337 = 987 解法のアプローチ 回文数は「前半の数字列を逆順に並べたものを後半に付け足す」ことで生成できます。そこで、前半部分となる候補 h を大きい方から順に試し、そこから回文を作り、その回文が2つの n 桁の

数列とウィンドウサイズ k が与えられたとき、スライディングウィンドウ方式で各ウィンドウにおける中央値の一覧を求める問題を考えます。例えば、次のような分布の場合をみてみましょう。 ウィンドウ位置中央値 13-1-353681 13-1-35368-1 13-1-35368-1 13-1-353683 13-1-353685 13-1-353686 ここでは k = 3 としており、得られる結果は [1, -1, -1, 3, 5, 6] となります。 アルゴリズムの考え方 この問題を解くために、以下の手順に従います。 順序付き集合（multiset）arr を定義する 関数 ins

ズーマゲームとはズーマ（Zuma）ゲームについて考えてみましょう。テーブルの上には一列にボールが並んでおり、それぞれのボールには赤（R）、黄（Y）、青（B）、緑（G）、白（W）のいずれかの色が付いています。また、こちらの手元にもいくつかのボールが用意されています。各ターンでは、手元のボールを1つ選んで列の中に挿入できます。挿入後、同じ色のボールが3個以上連続して並んでいれば、そのグループは自動的に取り除かれます。この消去は連鎖的に発生し、これ以上ボールを取り除けなくなるまで繰り返されます。この問題の目的は、テーブル上のボールをすべて消すために挿入する必要のあるボールの最小数を求めることです。す

問題の概要 配列が与えられたとき、その中のペア（A[i] と A[j]）が次の条件を満たす場合、これを「重要な逆ペア（important reverse pair）」と呼びます。 i < j かつ A[i] > 2 × A[j] 本記事では、このような重要な逆ペアの個数を求めます。たとえば入力が [2, 8, 7, 7, 2] の場合、条件を満たすのは (8, 2)、(7, 2)、(7, 2) の 3 組であるため、結果は 3 となります。 解法のアプローチ：マージソートの応用 すべてのペアを単純に調べる方法では計算量が O(n²) となり、配列が大きい場合に非効率です。そこで

問題の概要ある会社AがまもなくIPO（新規株式公開）を控えているとしましょう。自社の株式を良い価格で売却するために、A社はIPO前にいくつかのプロジェクトへ取り組み、資本を増やしたいと考えています。しかし、A社のリソースには限りがあり、IPOまでに完了できるのは最大k件の異なるプロジェクトだけです。最大k件のプロジェクトを完了した後の総資本を最大化する最適な戦略を設計して、A社を助けましょう。各プロジェクトiには純利益 Pi と、着手に必要な最小資本 Ci が設定されています。初期資本は W です。プロジェクトを完了すると純利益を獲得でき、その利益は総資本に加算されます。つまりこの問題は、与え

一列に並んだ n 台のスーパー洗濯機があるとします。初期状態では、各洗濯機には何着かの服が入っているか、あるいは空になっています。1 回の移動ごとに、任意の m 台（1 ≤ m ≤ n）の洗濯機を選び、選んだ各洗濯機から 1 着ずつ、隣接する洗濯機へ同時に渡すことができます。ここで、左から右へ各洗濯機に入っている服の枚数を表す整数配列が与えられます。すべての洗濯機の服の枚数を同じにするために必要な最小の移動回数を求めてください。均等にすることが不可能な場合は -1 を返します。具体例たとえば入力が [1, 0, 5] の場合、出力は 3 になります。手順は以下の通りです。右端の 5 から中央の

問題概要ここに、色の異なる複数の箱が一列に並んでいるとします。それぞれの色は異なる正の整数で表されます。プレイヤーは複数のラウンドに分けて箱を取り除き、すべての箱をなくすことを目指します。各ラウンドでは同じ色が連続した箱（k個、k >= 1）を選んでまとめて取り除くことができ、その際に k × k 点の得点を獲得できます。例えば、入力が [1,3,2,2,2,4,4,3,1] の場合、出力は 21 になります。この記事では、獲得できる得点を最大化するためのアルゴリズムを解説します。出力が 21 になる理由実際の消し方の一例を見てみましょう。[1,3,2,2,2,4,4,3,1] → 3個

問題概要 正の整数 n が与えられます。このとき、長さ n のすべての出席記録のうち「報酬対象（rewardable）」とみなせるものの総数を求めます。答えは非常に大きな値になる可能性があるため、109 + 7 で割った余りを返します。 出席記録に使用できる文字 学生の出席記録を表す文字列には、次の3種類の文字のみを含めることができます。 A … 欠席（Absent）を表します L … 遅刻（Late）を表します P … 出席（Present）を表します 「報酬対象」となる条件 ある出席記録が報酬対象とみなされるのは、次の両方を満たす場合です。 A（欠席）が2回以上含まれていないこ