C++

小文字の英字のみで構成された2つの文字列 S と T が与えられたとします。S には同じ文字が2回以上現れることはなく、S はあらかじめ何らかの独自の順序(カスタムオーダー)でソートされています。ここで、T の文字を並べ替えて、S の順序と一致するようにするのが課題です。具体的には、S 内で x が y より先に現れるならば、結果の文字列でも x は y より先に現れなければなりません。例として、S = cba、T = abcd の場合を考えてみましょう。このとき出力は cbad となります。a、b、c はいずれも S に含まれているため、これらの順序は S に従って c、b、a である必要が

問題の概要正の整数からなる配列 A と、2つの正整数 L・R が与えられます。このとき、「部分配列内の最大要素の値が L 以上 R 以下」という条件を満たす、連続した空でない部分配列の個数を求めるのが目的です。例えば、A = [2,1,4,3]、L = 2、R = 3 の場合を考えてみましょう。条件を満たす部分配列は [2]、[2,1]、[3] の3つであるため、出力は 3 になります。解法のアプローチこの問題は、配列を一度走査するだけで O(n) の時間計算量で解けます。考え方のポイントは次の通りです。ret:最終的な答え(条件を満たす部分配列の総数)dp:「現在注目している位置で終わる、条

ノード数 N の有向非巡回グラフ（DAG）が与えられているとします。ここでの課題は、ノード 0 からノード N-1 へ至るすべての経路を見つけ出し、任意の順序で返すことです。グラフは次のように表現されます。ノードは 0, 1, ..., graph.length - 1 であり、graph[i] は「辺 (i, j) が存在するノード j」のリストを意味します。たとえば、入力が [[1,2], [3], [3], []] の場合、出力は [[0,1,3], [0,2,3]] となります。解法のアプローチこの問題は深さ優先探索（DFS）とバックトラッキングを組み合わせることで解けます。具体的には

同じ非ゼロの長さを持つ2つの整数列 A と B が与えられているとします。ここで、A[i] と B[i] の要素を入れ替える(スワップする)ことができます。ただし、スワップできるのは、それぞれの数列において同じインデックス位置にある要素同士のみです。いくつかのスワップを行った後、A と B の両方が厳密に増加する(strictly increasing)状態にしたいと考えます。このとき、両方の数列を厳密に増加させるために必要な最小のスワップ回数を求めるのがこの問題です。問題の例例として、入力が A = [1,3,5,4]、B = [1,2,3,7] の場合を考えてみましょう。このとき答えは 1

クエリ文字列のリストとパターンが与えられ、ブーリアン値のリストを返す問題を考えてみましょう。answer[i] は、queries[i] がパターンに一致する場合にのみ true となります。ここで「クエリの単語がパターンに一致する」とは、パターンの単語に小文字を挿入することでクエリと等しくできることを意味します。大文字の順序と種類は完全に一致している必要があります。例えば、入力が [FooBar,FooBarTest,FootBall,FrameBuffer,ForceFeedBack]、pattern = FB の場合、出力は [true, false, true, true, false

問題概要 N × N のグリッドが与えられ、各セルには 0(水)または 1(陸地)のいずれかが格納されています。この中から「最も近い陸地セルまでの距離」が最大となる水セルを 1 つ見つけ、その距離を返すのが目的です。距離の計算にはマンハッタン距離を使用します。2 つのセル (x0, y0) と (x1, y1) 間の距離は、次の式で定義されます。 |x0 − x1| + |y0 − y1| また、グリッド内に陸地が存在しない場合、または水が存在しない場合は -1 を返します。 入力例 101000101 この場合の出力は 2 となります。中央のセル (1, 1) は、すべての陸地セルからちょう

問題の概要いくつかの取引（トランザクション）が与えられているとします。ある取引は、以下のいずれかの条件を満たす場合に「無効である可能性」があるとみなされます。取引金額が1,000ドルを超えている同じ名前による別の取引が、異なる都市で60分以内（60分ちょうども含む）に行われている各取引文字列transactions[i]はカンマ区切りの値で構成されており、それぞれ「名前」「時間（分単位）」「金額」「都市」を表しています。取引のリストが与えられたとき、無効である可能性のある取引だけを抽出して返すのが目標です。たとえば、入力が [alice,20,800,mtv, bob,50,1200,mtv]

問題概要 整数型の配列 arr と整数 k が与えられます。まず、元の配列を k 回繰り返してつなげた新しい配列を作成します。たとえば、arr = [1, 2]、k = 3 の場合、生成される配列は [1, 2, 1, 2, 1, 2] となります。 そのうえで、この配列における最大部分配列の合計を求めます。なお、部分配列の長さは 0 でもよく、その場合は合計を 0 とみなします。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返してください。 たとえば、入力が [1, -2, 1]、k = 5 のとき、答えは 2 になります。 解き方の考え方 この問題は、連結後

問題の概要ここでは、「Q」「W」「E」「R」の4種類の文字のみで構成された文字列を扱います。各文字がちょうど n/4 回(n は文字列の長さ)出現するとき、その文字列は「バランスが取れている」と定義します。元の文字列をバランスの取れた状態にするには、連続する部分文字列を同じ長さの任意の別の文字列で置き換えます。このとき必要となる部分文字列の最小の長さを求めるのが目的です。例えば、s = QQWE の場合、答えは 1 になります。これは先頭の Q を R に置き換えて RQWE とすれば、各文字が1回ずつ出現しバランスが取れるためです。また、文字列がすでにバランスしている場合は 0 を返します。

問題の概要2つの整数 n と start が与えられたとき、0 から 2^n − 1 までの整数の順列 p を、以下の条件を満たすように求める問題を考えます。p[0] = start であること隣接する要素 p[i] と p[i+1] の2進数（バイナリ）表現は、1ビットのみ異なること最初と最後の要素である p[0] と p[2^n − 1] も、1ビットのみ異なることたとえば、n = 2、start = 3 が入力された場合、答えは [3, 2, 0, 1] となります。これを2進数で表すと [11, 10, 00, 01] であり、隣り合う値同士（最後の要素と最初の要素を含む）が必ず1ビッ

文字列の配列 arr が与えられたとします。ここで扱う文字列 s とは、arr の部分列（サブシーケンス）の中から「重複する文字を一切含まないもの」を選び、それらを連結して作られる文字列のことです。この問題の目的は、そのような s として実現できる最大の長さを求めることです。 例えば、入力が [cha, r, act, ers] の場合、出力は 6 になります。このとき条件を満たす解としては chaers や acters が挙げられます。 解法のアプローチ この問題を解くために、以下の手順に従って進めます。 まず、2つの文字列 s と t を受け取るメソッド ok() を作成します。この

問題の概要ここでは、n列×2行の行列について、次の情報が与えられているものとします。行列の各要素は 0 または 1 のみ0行目(上段)の要素の合計が upper として与えられる1行目(下段)の要素の合計が lower として与えられるi列目(0始まり)の要素の合計が colsum[i] として与えられる(colsum は長さ n の整数配列)この課題では、upper、lower、colsum の情報をもとに元の行列を復元し、2次元の整数配列として返します。有効な解が複数存在する場合は、そのうちのどれを返しても構いません。一方、条件を満たす解が存在しない場合は、空の2次元配列を返します。たとえ

非負整数 n が与えられたとき、そのエンコード形式を求めることを考えます。エンコードのルールは以下の表の通りです。 数値エンコード結果0""1"0"2"1"3"00"4"01"5"10"6"11"7"000" 表を見ると、1桁の「0」「1」は数値1・2に、2桁の「00」〜「11」は数値3〜6に、3桁の「000」以降は数値7以降に対応していることが分かります。つまり、ビット長ごとに区切られたブロックの中へ、整数が順番に割り当てられていく仕

問題の概要 複数のリストからなる領域データを考えてみましょう。各リストの先頭にある領域は、そのリストに含まれる他のすべての領域を包含しています。つまり、領域Xが別の領域Yを含む場合、XはYよりも大きな領域であると定義されます。また、定義上、あらゆる領域Xは自分自身を常に含むものとします。 このとき、2つの領域r1とr2が与えられたら、両方を同時に含む中で最も小さい領域（最小の共通領域）を見つける必要があります。なお、r1・r2・r3という領域が存在し、r1がr3を含んでいる場合には、r3を含む別の領域r2は存在しないことが保証されています。 例えば、入力が以下のようなデータで、r1 = &ls

問題の概要整数の配列 nums が与えられたとき、配列の要素を選んで合計が3で割り切れるようにする場合の、最大の合計値を求める問題を考えます。例えば、入力が [3,6,5,1,8] の場合、出力は 18 になります。これは、要素 5 を除いた [3,6,1,8] を選んだときの合計が 18 となり、3で割り切れるためです。解決のアプローチこの問題は動的計画法(DP)を用いて効率的に解くことができます。dp[i][j] を「最初の i 個の要素の中から選んだ要素の合計を3で割った余りが j となるときの最大合計」と定義します。具体的な手順は以下の通りです。n を配列 nums のサイズとします(

問題の概要2つの整数 tomatoSlices（トマトのスライス数）と cheeseSlices（チーズのスライス数）が与えられます。これらは、次の2種類のバーガーを作るための材料です。ジャンボバーガー： トマトのスライス4枚とチーズのスライス1枚を使用スモールバーガー： トマトのスライス2枚とチーズのスライス1枚を使用与えられた材料をすべて使い切り、トマトのスライスとチーズのスライスの残りがどちらも0になるように、ジャンボバーガーとスモールバーガーの個数 [total_jumbo, total_small] を求めます。もし材料を余らせずに使い切ることが不可能な場合は、空の配列 [] を返し

m × n のサイズを持つバイナリ行列(0と1のみで構成される行列)が与えられたとき、すべての要素が1である正方形の部分行列の総数を数える問題を考えてみましょう。例えば、次のような行列が与えられたとします。011111110111この場合、答えは 15 となります。内訳は以下の通りです。1 × 1 の正方形(1つの1からなる):10個2 × 2 の正方形(4つの1からなる):4個3 × 3 の正方形(9つの1からなる):1個解法のアプローチ:動的計画法(DP)この問題は、動的計画法を用いることで効率的に解くことができます。基本的な考え方は、「各セルを右下の角とする正方形の個数」をそのセルの値と

0からn-1までのIDを持つn人の人がおり、各人は必ず1つのグループに所属しているとします。長さnの配列groupSizesが与えられ、この配列の各要素はその人が所属すべきグループのサイズを示しています。ここでの課題は、実際に形成されるグループと、各グループに含まれる人々のIDを見つけ出すことです。例えば、入力が [3,3,3,3,3,1,3] の場合、出力は [[5], [0, 1, 2], [3, 4, 6]] となります。なお、答えは一意ではなく、[[2,1,6],[5],[0,4,3]] や [[5],[0,6,2],[4,3,1]] なども有効な解として認められます。解法のアプローチ

問題の概要整数型の配列 nums と、しきい値を表す整数 k が与えられます。ここで、正の整数である「除数(割る数)」を1つ選び、配列のすべての要素をその値で割った結果(切り上げ)を合計することを考えます。この合計値がしきい値 k 以下となるような、最小の除数を求めるのが本問題の目的です。例として、nums = [1,2,5,9]、k = 6 の場合を考えてみましょう。答えは 5 になります。除数が 1 のとき:合計は (1+2+5+9) = 17 となり、しきい値を超えてしまいます。除数が 4 のとき:合計は (1+1+2+3) = 7 となり、まだしきい値より大きいです。除数が 5 のとき

問題の概要：連続数字（Sequential Digits）とは ある整数が連続した桁（シーケンシャルディジット）を持つとは、その数値の各桁が、直前の桁よりも必ず1大きくなっている状態を指します。例えば 123 や 4567 のような数値が該当します。 この記事では、指定された範囲 [low, high] に含まれる連続数字をすべて見つけ、昇順に並べたリストとして返す方法を解説します。例として、low = 100、high = 300 が与えられた場合、条件を満たすのは 123 と 234 の2つだけであるため、出力は [123, 234] となります。 解法のアプローチ 連続数字は「先頭の桁