C++

問題の概要 森の中にいるすべてのウサギには、それぞれ固有の毛色があります。ここで、一部のウサギ(全員の場合もありえます)が「自分と同じ色のウサギは他に何匹いるか」という質問に答え、その回答が配列として与えられます。求めたいのは、これらの回答と矛盾しない範囲で、森に存在しうるウサギの最小数です。 入力例での考え方 たとえば入力が [1, 1, 2] のとき、答えは 5 になります。 「1」と答えた2匹は、同じ白色のグループに属していると考えられます(自分のほかに同じ色のウサギが1匹いる、という意味です)。 一方、「2」と答えたウサギは白ではあり得ません。もし白なら「同じ色は1匹」と答えるはず

問題概要簡略化されたパックマン風のゲームを考えてみましょう。プレイヤーは点 (0, 0) からスタートし、目的地は (target[0], target[1]) です。マップ上には複数の幽霊がおり、i 番目の幽霊は (ghosts[i][0], ghosts[i][1]) からスタートします。各ターンで、自分とすべての幽霊は同時に、北・東・西・南の4方向のいずれかに1単位ずつ移動できます(移動しない選択も含まれます)。幽霊がどのように動こうとも、自分がどの幽霊よりも先に目的地へ到達できれば脱出成功です。ただし、幽霊と同じマスに同時に到達した場合は脱出とはみなされません。脱出が可能なら true

問題概要 数列 A を最大 K 個の隣接するグループに分割することを考えます。このとき、スコアは「各グループの平均値の合計」として定義されます。目的は、達成可能な最大のスコアを求めることです。 例として、A = [9, 1, 2, 3, 9]、K = 3 の場合を見てみましょう。最適な分割は [9]、[1, 2, 3]、[9] であり、このときのスコアは次のように計算できます。 9 + (1 + 2 + 3) / 3 + 9 = 20 一方、[9, 1]、[2]、[3, 9] のように分割すると、得られるスコアはこれより小さくなります。 解法のアプローチ：動的計画法（メモ化再帰） この問題は

問題の概要重複のない整数値を持つ連結リストの先頭ノード(head)が与えられます。さらに、連結リスト内の値の部分集合であるリストGも渡されます。このとき、Gの中にいくつの「連結成分」が存在するかを求めます。ここで、2つの値が連結しているとは、それらが連結リスト上で連続して現れることを意味します。例えば、連結リストが [0,1,2,3]、G = [0,1,3] の場合、出力は 2 になります。これは、0と1が連結リスト上で隣接しているため [0,1] という一つの成分となり、3は単独で [3] という別の成分となるからです。解法のアプローチこの問題は、連結リストを先頭から順に走査し、「Gに含まれ

単語のリストが与えられたとき、参照文字列 S とインデックスのリスト A を組み合わせることで、それらをエンコードできます。例えば、単語リストが [time, me, bell] の場合、S = time#bell#、indexes = [0, 2, 5] のように表現できます。各インデックスの位置から読み始め、# 記号に到達するまで読み進めると、元の単語を復元できる仕組みです。 ここでの課題は、与えられたすべての単語をエンコードできる最短の参照文字列 S の長さを求めることです。上記の例では、答えは 10 となります。 解法のアプローチ この問題は、トライ木(Trie)を活用すると効率的に

テーブルの上にN枚のカードが置かれており、各カードの両面には正の整数が印刷されています（表面と裏面で異なる数字の場合もあります）。まず任意の枚数のカードを裏返し、その後1枚のカードを選びます。選んだカードの裏面に書かれた数字Xが、どのカードの表面にも存在しないとき、その数字Xは「良い（good）」と呼ばれます。このとき、最も小さい「良い」数を求めるのがこの問題の目的です。良い数がひとつも存在しない場合は0を返します。ここで、fronts[i]とbacks[i]はそれぞれi番目のカードの表面と裏面の数字を表し、カードを裏返すと表面と裏面の数字が入れ替わります。例えば、fronts = [1,2,

問題概要 1より大きい正整数のリストが与えられます。これらの整数を使って二分木を構築することを考えます。ただし、同じ数は何度でも使用でき、葉以外のすべてのノードは、その2つの子ノードの値の積になっていなければなりません。この条件を満たす二分木が全部で何通り作れるかを求め、答えは 109 + 7 で割った余りとして返します。 たとえば入力が [2, 4, 5, 10] の場合、答えは 7 になります。具体的には次の7通りの木が作れます。 [2] [4] [5] [10] [4, 2, 2]（根が4、子が2と2） [10, 2, 5]（根が10、子が2と5） [10, 5, 2]（根が10、子が

問題概要 複数の人が互いにフレンド申請(友達リクエスト)を送る場面を考えてみましょう。各人の年齢は配列 ages に格納されており、ages[i] が i 番目の人の年齢を表します。このとき、人物 A は次のいずれかの条件に当てはまる場合、人物 B(B ≠ A)に対してフレンド申請を送りません。 age[B] <= 0.5 * age[A] + 7 age[B] > age[A] age[B] > 100 かつ age[A] < 100 これらの条件に該当しなければ、A は B にフレンド申請を送ります。なお、A が B に申請したからといって、B が必ずしも A

問題の概要文字列 S が与えられたとき、複数の置換操作を実行して、特定の文字グループを新しい文字列に置き換えることを考えます。各置換操作には3つのパラメータがあります。開始インデックス i、検索対象の単語 x、置換後の単語 y です。ルールは次のとおりです。もし x が元の文字列 S の位置 i から始まっている場合は、その出現箇所を y に置き換えます。そうでない場合は、何も行いません。例1S = abcd という文字列に対し、置換操作 i = 2、x = cd、y = ffff を適用するとします。「cd」は元の文字列 S の位置2から始まっているため、この部分を「ffff」に置き換えます

カードゲーム「21」をベースにした、次のようなゲームを考えてみましょう。プレイヤーのリマは0点からスタートし、所持点がK点未満である間、数字を引き続けます。各ターンでは、区間 [1, W] に含まれる整数の中からランダムに1つを選んで加点します（Wは与えられた整数）。各抽選は互いに独立しており、すべての出目は等しい確率で現れるものとします。リマは合計がK点以上になった時点で数字を引くのをやめます。このとき、彼女の最終的な得点がN点以下になる確率を求めてください。例として、N = 6、K = 1、W = 10 の場合を考えます。K = 1 なので、リマは最初に1枚カードを引いた時点で必ず1点以上

配列 A の任意の連続する部分配列 B は、以下の性質を満たすとき「山（マウンテン）」と呼ばれます。 B のサイズが 3 以上であること 0 < i < B.length - 1 を満たすある i が存在し、B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] となること（要素が一度単調に増加した後、単調に減少する形状であること） ここで、整数の配列 A が与えられたとき、その中で最も長い山の長さを求めることを考えます。山がひとつも存在しない場合は 0 を返します。

問題の概要 Rimaは、整数の配列として与えられるカードの手札を持っています。彼女はこの手札を組み替えて、それぞれサイズWのグループに分けたいと考えています。ただし、各グループは「W枚の連続したカード」、つまり値が1ずつ増えていく並びで構成されている必要があります。このような分割が可能かどうかを判定するのが課題です。 例えば、手札が [1,2,3,6,2,3,4,7,8]、W = 3 の場合、答えは true になります。実際に [1,2,3]、[2,3,4]、[6,7,8] という3つのグループに再配置できるからです。 解法のアプローチ この問題は、各カードの値ごとの出現回数をマップで管

小文字のみで構成された文字列 S と整数型配列 shifts が与えられたとします。ここで「シフト」とは、ある文字をアルファベット順で次の文字に置き換えることを意味し、z の場合は a に戻ります（循環）。そして、各 shifts[i] = x に対して、文字列 S の先頭から i+1 文字目までをそれぞれ x 回シフトします。すべてのシフト操作を適用した後の最終的な文字列を求めるのがこの問題です。 例として、文字列が abc、shifts = [3, 5, 9] の場合を考えてみましょう。 最初の1文字を3回シフト → dbc 最初の2文字をそれぞれ5回シフト → igc 最初の3文字をそ

問題概要 同じ目的地に向かうN台の車が、片側1車線の道路を走行しているとします。目的地までは「target」マイル離れており、各車iは一定の速度speed[i]（マイル毎時）を持ち、出発時点での位置は目的地からposition[i]マイル手前にあります。 車は前方の車を追い越すことはできませんが、追いついてバンパー同士をくっつけたまま同じ速度で走ることは可能です。このとき2台の車間距離は無視され、同じ位置にいるものとみなされます。車のフリート（車隊）とは、同じ位置・同じ速度で走行する1台以上の車の集合のことです。仮にある車が目的地ちょうどの地点でフリートに追いついた場合も、その車はそのフリート

問題概要バランスの取れた括弧文字列 S が与えられたとき、以下のルールに基づいてその文字列のスコアを計算することを考えます。() のスコアは 1AB のスコアは A + B(A と B はそれぞれバランスの取れた括弧文字列)(A) のスコアは 2 × A(A はバランスの取れた括弧文字列)たとえば、入力が「(()(()))」の場合、出力は 6 になります。アルゴリズム(スタックを利用した解法)この問題はスタックを使うことで効率的に解くことができます。解法の手順は以下の通りです。ans := 0 と初期化し、整数型のスタック st を用意するi を 0 から文字列 S のサイズまで繰り返すS[i

ミラーリフレクション問題とは4つの壁すべてに鏡が張られた正方形の部屋を考えてみましょう。南西の角以外の各角には、0、1、2という番号が付けられたレシーバー（受光器）が設置されています。この正方形の部屋の一辺の長さは p であり、南西の角から発射されたレーザー光線は、最初に東側の壁に当たります。その位置は、0番のレシーバーから距離 q の地点です。このとき、光線が最初に到達するレシーバーの番号を求めるのが本問題です。例えば、p = 2、q = 1 の場合を考えてみます。光線は壁で反射を繰り返し、最終的に左側の壁へ戻ってきたときに初めてレシーバー2に到達します。したがって、出力は 2 となります。

任意の長さの文字列が与えられ、その文字列に含まれる大文字を小文字へ、小文字を大文字へ変換するのが課題です。この処理は「ケース(大小文字)の反転」と呼ばれ、C++ではいくつかの方法で実装できます。例入力 − string str = Welcome To The Site!出力 − wELCOME tO tHE sITE!解説 − 大文字の W、T、T、S を小文字に変換し、小文字の e、l、c、o、m、e、o、i、t、e を大文字に変換します。記号や特殊文字(!など)には何も操作を行いません。入力 − string str = HELLO出力 − hello解説 − 大文字の H、E、L、L、

本記事では、2つの文字列(str1とstr2)が与えられたときに、両者に共通する文字のペア数を求める方法を解説します。具体的には、str1[i] == str2[j]となる組み合わせを「一致するペア」とみなし、該当するたびにカウントを1ずつ増やしていきます。逆にstr1[i] != str2[j]の場合はペアとして扱われず、カウントも増加しません。 実行例 入力 − str1 = hello　　　 str2 = heoo出力 − count is: 3 説明: str1[0] = str2[0](h)、str1[1] = str2[1](e)は一致しており、str1[2] != str2[2]

本記事では、与えられた整数に含まれる偶数の数字と奇数の数字をそれぞれカウントする方法を解説します。さらに、偶数の数字が偶数回出現しており、かつ奇数の数字が奇数回出現しているかどうかも判定します。実行例入力: digit = 12345出力: 偶数の個数 = 2      奇数の個数 = 3説明: 偶数の数字は2回(偶数回)、奇数の数字は3回(奇数回)出現しているため、条件を満たしています。入力: digit = 44556出力: 偶数の個数 = 3      奇数の個数 =

整数値が格納された変数startから変数endまでの範囲が与えられ、その範囲内に存在する階乗数の総数を求めるのがこの課題です。 階乗数とは ある数の階乗とは、その数から1ずつ減らしながら順に掛け合わせて計算される値です。「!」という記号で表され、0!、1!、2!、3!、5!のように書きます。なお、0!と1!はどちらも常に1となります。 例：2の階乗 = 2 × (2−1) = 2 × 1 = 2 　　3の階乗 = 3 × (3−1) × (2−1) = 3 × 2 × 1 = 6 具体例 入力 − start = 5, end = 600 出力 − 階乗数の個数は 3 説明 − 5〜60