C++

問題概要 整数型の配列 nums と正整数 k が与えられます。この配列を「連続する k 個の整数」からなるセットに完全に分割できるかどうかを判定し、可能であれば true を、不可能であれば false を返してください。 たとえば、入力が [1,2,3,3,4,4,5,6]、k = 4 の場合を考えてみましょう。この配列は [1,2,3,4] と [3,4,5,6] の2つのセットに分割できるため、答えは true(出力は 1)になります。 解法のアプローチ この問題は、マップ(連想配列)で各数値の残り出現回数を管理しながら、昇順にグループを形成していくことで効率よく解けます。手順は以下の

整数配列 arr と目標値 target が与えられたとします。この問題では、配列内の value より大きいすべての要素を value に置き換えたとき、その配列の合計が目標値にできるだけ近くなるような整数 value を見つけます。合計が等しくなる候補が複数存在する場合は、より小さい方の整数を返します。 例として、配列が [4,9,3]、目標値が 10 の場合を考えてみましょう。value を 3 とすると、配列は [3,3,3] となり、合計は 9 になります。これは 10 に最も近いため、答えは 3 となります。 解法のアプローチ この問題を解くために、以下の手順に従います。 n

n個の電球があり、最初はすべて消えている状態だとします。まず、すべての電球を点灯させます。次に、2番目ごとの電球を消灯します。3ラウンド目では、3番目ごとの電球をトグル（消えていれば点灯、点いていれば消灯）します。同様に、iラウンド目ではi番目ごとの電球をトグルしていき、nラウンド目では最後の1個の電球のみをトグルします。このとき、nラウンド終了後に点灯している電球の数を求めるのがこの問題です。例えば入力が3の場合、答えは1になります。その過程は以下の通りです。最初、3つの電球は［消灯， 消灯， 消灯］の状態です。1ラウンド後、［点灯， 点灯， 点灯］になります。2ラウンド後、［点灯， 消灯，

問題概要 1から7までの一様なランダム整数を生成する関数 rand7() が与えられているとします。この関数を利用して、1から10までの一様なランダム整数を生成する関数 rand10() を実装するのが本記事の目的です。なお、乱数を直接生成するライブラリ関数を新たに使用することはできません。 解法のポイント:棄却サンプリング この問題を解く鍵は、rand7() を2回呼び出すことで、より広い範囲の一様分布を作り出すことです。 次の式を考えてみましょう。 rand40 = (rand7() - 1) * 7 + (rand7() - 1) これは7進法の2桁の数とみなすことができ、0から48

ここにマッチ売りの少女がいると想像してください。彼女が持っているマッチ棒の本数と長さは正確にわかっており、そのすべてのマッチ棒を使い切って1つの正方形を作れるかどうかを調べる必要があります。条件は以下のとおりです。マッチ棒を折ったり切ったりしてはいけない棒同士をつなぎ合わせることは可能各マッチ棒は必ずちょうど1回使用する入力は少女が持っているマッチ棒の長さのリストで、出力は正方形を作成できる場合は true、できない場合は false となります。たとえば入力が [1,1,2,2,2] の場合、答えは true です。一辺の長さが2の正方形を作ることができ、一辺には長さ1のマッチ棒を2本組み合

問題概要m個の0とn個の1が与えられているとします。さらに、バイナリ文字列からなる配列があります。ここでの課題は、与えられたm個の0とn個の1を使用して生成できる文字列の最大数を求めることです。ただし、各0と1はそれぞれ一度しか使用できません。例えば、配列が [10, 0001, 111001, 1, 0]、m = 5、n = 3 の場合、出力は4になります。これは、5つの0と3つの1を使って「10」「0001」「1」「0」の合計4つの文字列を作ることができるためです。解法のアプローチこの問題は動的計画法（DP）を用いて効率的に解くことができます。手順は以下の通りです。(m + 1) × (n

問題概要円の半径と中心のx・y座標が与えられたとき、円の内部から一様（均等）にランダムな点を1つ生成する関数 randPoint() を実装します。実装にあたっては、以下の点に注意する必要があります。入力値および出力値はすべて浮動小数点数として扱います。半径と中心のx・y座標は、クラスのコンストラクタに渡されます。円周上の点も「円の中にある」ものとみなします。randPoint() は、ランダムな点のx座標とy座標をこの順で返します。例えば、入力が [10, 5, -7.5]（半径10、中心 (5, -7.5)）の場合、randPoint() を呼び出すたびに、[11.15792, -8.54

ここでは、「マジックストリング（魔法の文字列）」と呼ばれる特別な文字列 S を扱います。この文字列は 1 と 2 のみで構成され、次のような性質を持っています。 文字列 S 内の連続する 1 および 2 の出現回数（ランレングス）を順に並べて連結すると、元の文字列 S 自身が再現されます。 文字列 S の先頭部分は次のようになっています。S = 1221121221221121122…… S の連続する 1 と 2 をグループに分けると、次のようになります。1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | 2 | 11 | 22 ……そして、各グループにおける

問題の概要整数型の配列が与えられたとき、その配列から作られるすべての異なる増加部分列を求めることを考えます。ただし、増加部分列の長さは2以上でなければなりません。例えば、配列が [4, 6, 7, 7] の場合、出力は次のようになります。[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7, 7], [4, 7, 7]]解法のアプローチこの問題は、バックトラッキング（深さ優先探索）を用いて効率的に解くことができます。手順は以下の通りです。すべての結果を格納するための配列 res を定義します。solve というメソッドを

問題概要League of Legends(LOL)の世界には、ティーモ(Teemo)というヒーローがいます。彼の攻撃を受けると、敵のアーシュ(Ashe)は毒状態に陥ります。本記事では、ティーモがアーシュに対して行った攻撃の時刻を昇順に並べた時系列と、1回の攻撃ごとの毒の持続時間が与えられたとき、アーシュが毒状態であった時間の合計を求める問題を扱います。なお、ティーモはある時点の最初に攻撃を行い、その瞬間に相手を毒状態にできるものと仮定します。入出力の例たとえば、攻撃時刻が [1,4]、毒の持続時間が 2 秒の場合、出力は 4 になります。時刻 1 にティーモが攻撃を行うと、アーシュは即座に毒

問題概要軸に平行で互いに重ならない長方形のリスト rects が与えられているとします。このとき、長方形が覆う空間の中から整数座標の点をランダムかつ一様に選択して返す関数 pick を実装する必要があります。実装にあたっては、以下の条件を満たす必要があります。整数点とは、x座標・y座標がともに整数である点を指します。長方形の周囲（境界線）上にある点も、長方形が覆う空間に含まれるものとします。i番目の長方形 rects[i] は [x1, y1, x2, y2] という形式で表されます。ここで [x1, y1] は左下隅の整数座標、[x2, y2] は右上隅の整数座標です。各長方形の縦および横の

問題の概要M×N の要素を持つ行列が与えられたとき、そのすべての要素を対角順（ジグザグ順）で取り出すことを考えます。例として、次のような 3×3 の行列を見てみましょう。123456789この場合、期待される出力は [1, 2, 4, 7, 5, 3, 6, 8, 9] です。要素は左上からスタートし、右上方向への斜め移動と左下方向への斜め移動を交互に繰り返しながら順番に辿られていきます。アルゴリズムの手順この問題は「右肩上がりの斜め列（反対角線）ごとに要素を集め、進む方向を交互に入れ替える」という方針で解くことができます。具体的な手順は以下の通りです。結果格納用の配列 ret を用意し、n

文字列 s が与えられたとき、その中に含まれる最長の回文部分列（パリンドローム・サブシーケンス）の長さを求める問題を考えます。文字列の最大長は 1000 と仮定できます。たとえば入力が bbbab の場合、出力は 4 になります。このとき bbbb が回文部分列の一例です。 解法のアプローチ この問題は、「元の文字列 s と、それを逆順にした文字列 x の最長共通部分列（LCS）の長さを求める」ことで解決できます。回文は前後どちらから読んでも同じになるため、元の文字列と逆順の文字列の両方に共通して現れる最長の部分列こそが、最長回文部分列となるからです。 アルゴリズムの手順 x := s と

n_rows（行数）と n_cols（列数）からなる2値行列を考えてみましょう。すべての要素は初期状態で0になっています。ここで、0の値を一様にランダムに選択し、その値を1に変更して、該当する位置 [row.id, col.id] を返す関数 flip() を定義する必要があります。さらに、すべての値を0に戻す関数 reset() も実装しなければなりません。その際、システムの乱数生成関数（Math.random）の呼び出し回数を最小限に抑え、時間計算量と空間計算量を最適化することが求められます。 例えば、2×3の行列に対して flip() を4回呼び出した場合、結果は [0,1]、[1,2]

問題概要 負でない数値のリストと目標となる整数 k が与えられたとき、長さが2以上の連続する部分配列（サブアレイ）の中に、合計が k の倍数（つまり n × k、n は任意の整数）となるものが存在するかどうかを判定する関数を作成します。 例えば、入力が [23, 2, 4, 6, 7] で k = 6 の場合を考えてみましょう。[2, 4] は長さ2の連続部分配列であり、その合計は 6 で k の倍数に一致するため、結果は True（真） となります。 解法のアプローチ：累積和の剰余とハッシュマップ この問題は、累積和（プレフィックスサム）の剰余とハッシュマップを組み合わせることで、O(n)

問題の概要 文字列 s と文字列のリスト（辞書）d が与えられます。このとき、与えられた文字列 s からいくつかの文字を削除することで作れる、辞書の中で最も長い単語を見つけます。候補が複数存在する場合は、最も長く、かつ辞書順（レキシコグラフィカル順）で最小の単語を返します。条件を満たす単語が存在しない場合は、空文字列を返します。 たとえば、入力が s = abpcplea、d = [ale, apple, monkey, plea] の場合、abpcplea から不要な文字を削除して apple を作ることができるため、答えは apple になります。 ポイント：部分列の判定 「文字を削除し

問題概要 0と1のみから構成されるバイナリ配列が与えられたとき、0と1の個数が等しい連続する部分配列(サブ配列)の最大長を求めることを考えます。 例えば、入力が [0,1,0] の場合、出力は 2 になります。[0,1] または [1,0] が、0と1の個数が等しい最長の連続部分配列だからです。 解法のアプローチ この問題は「累積和」とハッシュマップを組み合わせることで効率的に解けます。1を +1、0を −1 として扱い、同じ累積和が2回現れた位置の間に、0と1の個数が等しい区間が存在すると考えるのがポイントです。 具体的な手順は以下の通りです。 ret := 0(答え)、n := n

問題の概要 1からNまでのN個の整数があるとします。「美しいアレンジメント（美しい順列）」とは、これらのN個の数字をすべて使って構成される配列のうち、配列内のi番目の位置（1 <= i <= N）について、次のいずれかの条件が成り立つものと定義されます。 i番目の位置にある数が、iで割り切れる。 iが、i番目の位置にある数で割り切れる。 具体例：N = 2 の場合 入力が2のとき、答えは2になります。 1つ目の美しいアレンジメント [1, 2] 1番目の位置（i=1）にある数は1で、1はi（=1）で割り切れます。 2番目の位置（i=2）にある数は2で、2はi（=2）で割り切れ

正の整数の配列 w が与えられ、w[i] がインデックス i の重みを表しているとします。このとき、重みに比例した確率でインデックスをランダムに選択する関数 pickIndex() を定義する必要があります。 例えば、入力が [1, 3] の場合、pickIndex() を5回呼び出すと、結果は 0, 1, 1, 1, 0 のようになります。インデックス 1 の重みが 3 であるため、インデックス 1 が選ばれる確率はインデックス 0 の3倍になります。 解決策のアプローチ この問題を解くために、以下の手順に従います。 配列 v を定義します。 コンストラクタで以下のように初期化します。

はじめにこのチュートリアルでは、数列「3、5、33、35、53…」のN番目の項を求めるC++プログラムについて解説します。この問題では、ある整数nが与えられます。私たちのタスクは、その数列におけるn番目の項を特定することです。数列の規則性まず、この数列がどのように構成されているのかを見てみましょう。1番目の項：32番目の項：53番目の項：33（1番目の項に「3」を付加）4番目の項：35（1番目の項に「5」を付加）5番目の項：53（2番目の項に「3」を付加）6番目の項：55（2番目の項に「5」を付加）つまり、奇数番目の項は「i/2 番目の項の末尾に3を付けた数」、偶数番目の項は「(i/2 − 1