C++

負でない整数からなるスコア配列が与えられたとします。2人のプレイヤーが交互に配列の両端から数値を1つずつ選んでいきます。最初にプレイヤー1が選択し、次にプレイヤー2、その後再びプレイヤー1という順番で続きます。一度選ばれた数値は、もう一方のプレイヤーが選ぶことはできません。すべてのスコアが選ばれ終わった時点で、より高い合計スコアを獲得したプレイヤーが勝者となります。ここでは、スコア配列が与えられたときに、プレイヤー1が勝利できるかどうかを予測するプログラムをC++で作成します。 問題例 入力が [1, 5, 233, 7] の場合を考えてみましょう。このときの出力は True(真)になります

文字列のリストが与えられたとき、その中から最長の非共通部分列(Longest Uncommon Subsequence)を見つける問題を考えます。ここでいう非共通部分列とは、リスト内のいずれか1つの文字列の部分列でありながら、他のどの文字列の部分列にもなっていないものを指します。 まず「部分列」とは、元の並びから一部の文字を削除することで得られる列であり、残りの要素の相対的な順序は変更しないものです。たとえば "abc" の部分列には "a"、"ac"、"bc"、"abc" などが含まれます。

問題の概要0と1だけで構成された行列（マトリックス）が与えられたとき、各セルについて「最も近い0」までの距離を求める問題を考えます。ここで、隣接する2つのセル間の距離は1と定義します。例として、次のような入力が与えられたとします。000010111この場合、出力は次のようになります。000010121中央の「1」は上下左右のいずれかに存在する0までの距離が1であり、左下の「1」とその右隣の「1」は、それぞれ最寄りの0までの距離が1と2であることを示しています。解法のアプローチこの問題は幅優先探索（BFS）を用いることで効率的に解くことができます。基本的な考え方は、まずすべての「0」のセルを探索

n人の兵士が一列に並んでおり、それぞれの兵士には固有の評価値（rating）が割り当てられているとします。この中から、以下のルールに従って3人の兵士で構成されるチームを作ります。 インデックス (i, j, k) の3人の兵士を選び、その評価値が (rating[i], rating[j], rating[k]) であるとします。 チームが有効とみなされる条件は次のいずれかです。 (rating[i] < rating[j] < rating[k]) — 評価値が昇順に並ぶ場合 (rating[i] > rating[j] > rating[k]) — 評価値が降順に

文字列 s と整数 k が与えられたとします。ここでの課題は、s に含まれるすべての文字を使って、k 個の空でない回文（パリンドローム）文字列を構築できるかどうかを判定することです。例えば、入力が true、k = 4 の場合を考えてみましょう。この場合、各文字をそれぞれ別の文字列に割り当てるしか方法がないため、出力は True になります。解決のアプローチこの問題を解く鍵となるのは、回文の性質です。回文では、奇数回出現する文字は最大で 1 種類しか許されません。したがって、k 個の回文を構築できるかどうかは、「奇数回出現する文字の種類数」が k 以下であるかどうかで決まります。以下の手順で解

問題の概要円を (radius, xc, yc) という形式で表します。ここで (xc, yc) は円の中心座標です。同様に、軸に平行な長方形(軸平行境界ボックス)を (x1, y1, x2, y2) という形式で表し、(x1, y1) が左下隅の座標、(x2, y2) が右上隅の座標とします。このとき、円と長方形が互いに重なっているかどうかを判定する必要があります。たとえば、次のような入力が与えられた場合を考えてみましょう。この場合、出力は true(重なりあり)となります。解決のアプローチこの問題を解く鍵は、「長方形の中で円の中心に最も近い点」を見つけることです。その点と円の中心との距離が

問題の概要2進数形式で与えられた数値 s を、以下のルールに従って 1 になるまで減らしていくとき、必要なステップ数を求めることを考えます。現在の数が偶数の場合：その数を 2 で割る現在の数が奇数の場合：その数に 1 を加える具体例入力が 1101 の場合、出力は 6 になります。1101 は10進数で 13 を表します。処理の流れは以下の通りです。13 は奇数なので、1 を加えて 14 にする（ステップ1）14 は偶数なので、2 で割って 7 にする（ステップ2）7 は奇数なので、1 を加えて 8 にする（ステップ3）8 は偶数なので、2 で割って 4 にする（ステップ4）4 は偶数なので、

問題の概要 文字列の中に「aaa」「bbb」「ccc」のように同じ文字が3つ連続する部分文字列がひとつも含まれていないとき、その文字列をハッピーな文字列と呼びます。 ここで、3つの整数 a、b、c が与えられます。このとき、次の条件をすべて満たす文字列 s を返してください。 s はハッピーな文字列であり、かつ可能な限り長いこと。 s には文字 a が最大 a 個、b が最大 b 個、c が最大 c 個含まれること。 s は a、b、c の3種類の文字のみで構成されること。 条件を満たす文字列が存在しない場合は、空文字列を返します。 たとえば a = 1、b = 1、c = 7 が入力され

1からmまでの正整数を要素とする配列queriesが与えられたとき、すべてのクエリqueries[i]（iは0からn-1まで、nはqueriesのサイズ）を以下のルールに従って処理することを考えます。 初期状態では、順列はP=[1,2,3,...,m]となっています。 現在のiに対して、順列Pの中でqueries[i]が存在する位置（インデックスは0始まり）を探し、その要素を順列Pの先頭へ移動させます。 そして、与えられたすべてのクエリに対する結果を格納した配列を返す必要があります。 具体例で確認する たとえば、入力がqueries = [3,1,2,1]、m = 5である場合、出力は[

文字列が与えられたとき、HTML構文の特殊文字を通常の文字へ置き換えるHTMLパーサーを設計することを考えます。HTMLエンティティパーサーとは、HTMLコードを入力として受け取り、特殊文字のエンティティをすべて対応する実際の文字に置き換えるパーサーのことです。まず、対象となる特殊文字とそのエンティティの一覧を確認しましょう。二重引用符：エンティティは &quot;、記号は 単一引用符：エンティティは &#39;、記号は アンパサンド：エンティティは &amp;、記号は &大なり記号：エンティティは &gt;、記号は >小なり記号：エンティティは

数値 k が与えられたとき、合計がちょうど k と等しくなるようなフィボナッチ数の最小個数を求めます。ただし、同じフィボナッチ数は複数回使用しても構いません。 例えば、入力が k = 7 の場合、出力は 2 になります。フィボナッチ数列は 1, 1, 2, 3, 5, 8, 13, ... と続きますが、k = 7 の場合は 2 + 5 = 7 という 2 つの数の組み合わせで表現できるためです。 アルゴリズム(貪欲法) この問題は貪欲法(グリーディ法)を用いることで効率的に解けます。基本的な考え方は、「k を超えない最大のフィボナッチ数を選び、残りの値に対して同じ操作を繰り返す」というもので

ハッピー文字列とは「ハッピー文字列」とは、a、b、c の3種類の文字のみで構成され、かつ隣接する任意の2文字が異なる(s[i] != s[i + 1])という条件を満たす文字列のことです。つまり、同じ文字が連続して現れない文字列を指します。問題の概要2つの整数 n と k が与えられたとき、長さ n のすべてのハッピー文字列を辞書順に並べたリストを考えます。このリストの k 番目の文字列を求めてください。ただし、長さ n のハッピー文字列が k 個未満しか存在しない場合は、空文字列を返します。例えば、n = 3、k = 9 とすると、出力は cab になります。長さ3のハッピー文字列は全部で1

レストランで顧客が行った注文を表す配列 orders があるとします。各要素は orders[i] = [cust_name_i, table_num_i, food_item_i] の形式で、cust_name_i は顧客名、table_num_i はテーブル番号、food_item_i は顧客が注文した料理を表します。 このとき、レストランの「ディスプレイテーブル」を返す必要があります。ディスプレイテーブルとは、各行に「どのテーブルがどの料理を何個注文したか」を示す表のことです。1列目にはテーブル番号が入り、残りの列には料理名がアルファベット順に並びます。また、1行目はヘッダー行とし、最初

問題概要 croakOfFrogs という文字列が与えられます。この文字列は、複数のカエルが発する「croak」という鳴き声が混ざり合ってできています。複数のカエルが同時に鳴くこともあるため、複数の「croak」が入り混じった状態になっています。 ここでの課題は、与えられた文字列に含まれるすべての鳴き声を完成させるために必要な「カエルの最小匹数」を求めることです。 有効な「croak」とは、1匹のカエルが c、r、o、a、k の5文字を必ずこの順番で発声することを指します。カエルは5文字すべてを出し切って初めて1回の鳴き声が完了します。もし文字列が有効な「croak」の組み合わせとして成立しな

複数のカードが一列に並んでおり、各カードにはポイントが割り当てられています。これらのポイントは整数配列 cardPoints として与えられます。各ステップで、列の先頭または末尾からカードを1枚取得でき、ちょうど k 枚のカードを取得しなければなりません。最終的なスコアは、取得したカードのポイントの合計になります。ここでの課題は、整数配列 cardPoints と整数 k が与えられたときに、獲得できる最大スコアを求めることです。 例で理解する たとえば、入力が cardPoints = [1,2,3,4,5,6,1]、k = 3 の場合、出力は 12 になります。最初の1枚は、左端・右端どち

問題の概要 「リストのリスト」である nums が与えられたとき、そのすべての要素を対角順（ダイアゴナルオーダー）に並べて出力するのがこの問題の目的です。 たとえば、次のような行ごとに長さの異なる配列（ジャグ配列）が入力として与えられた場合を考えてみましょう。 このとき、期待される出力は次のとおりです。 [1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16] 解法のアプローチ この問題は、各要素を「値と座標のセット」として一旦記録し、対角線ごとの順序になるようにソートし直すことで解けます。具体的な手順は以下の通りです。 結果を格納す

問題概要 整数 num が与えられます。この整数に対して、次の手順をちょうど2回適用することを考えます。 0〜9の範囲から数字 x を1つ選ぶ。 同じく0〜9の範囲から別の数字 y を1つ選ぶ(y は x と同じでも構いません)。 num の10進表現に含まれるすべての x を y に置き換える。ただし、新しい整数に先頭ゼロが含まれてはならず、値が0になってもいけません。 1回目の操作結果を a、2回目の操作結果を b としたとき、a と b の差の最大値を求めるのがこの問題の目的です。 たとえば入力が 555 の場合、出力は 888 になります。1回目は x = 5、y = 9 を選んで

問題の概要 同じ長さを持つ2つの文字列 s1 と s2 が与えられたとします。このとき、s1 のある並べ替え(順列)が s2 のある並べ替えを「破る」ことができるか、あるいはその逆が成り立つかどうかを判定する必要があります。 ここで「文字列 a が文字列 b を破る」とは、0 から n-1 までのすべてのインデックス i において x[i] >= y[i](アルファベット順での比較)が常に成立することを意味します。 たとえば、入力が s1 = abc、s2 = xya の場合、出力は true になります。これは、s2 の並べ替えである ayx が、s1 = abc の並べ替えである a

問題概要 0と1のみで構成される配列 nums と整数 k が与えられたとします。このとき、配列内のすべての「1」が互いに少なくとも k 個以上離れて配置されているかどうかを判定し、条件を満たしていれば true を、そうでなければ false を返すプログラムを作成します。 例えば、入力が nums = [1,0,0,0,1,0,0,1]、k = 2 の場合、出力は true になります。これは、それぞれの「1」が互いに2つ以上の間隔をあけて配置されているためです。 解法のアプローチ この問題は、配列を先頭から一度だけ走査する線形探索（O(n)）で効率的に解くことができます。ポイントは、「

問題概要 整数型の配列 nums と整数 limit が与えられます。「部分配列内の任意の2要素の絶対差が limit 以下である」という条件を満たす、最も長い空でない連続部分配列（サブアレイ）の長さを求めてください。 例として、nums = [8,2,4,7]、limit = 4 が入力された場合の出力は 2 になります。すべての部分配列を確認してみましょう。 [8] → |8−8| = 0 ≤ 4（条件を満たす） [8,2] → |8−2| = 6 > 4（条件を満たさない） [8,2,4] → |8−2| = 6 > 4（条件を満たさない） [8,2,4,7] → |8−2