C++

迷路の中にボールがあるとします。迷路には空きスペース（通路）と壁があります。ボールは上下左右のいずれかの方向に転がって空き通路を進むことができますが、壁にぶつかるまで止まりません。ボールが停止したときに、次の方向を選べます。この問題では、ボールの開始位置、目的地、そして迷路そのものが与えられ、「ボールが目的地の位置で停止できるかどうか」を判定する必要があります。迷路は2次元配列で表現され、1は壁、0は空きスペースを意味します。迷路の外周はすべて壁になっています。開始位置と目的地は行・列のインデックス（座標）で与えられます。問題例たとえば、次のような2次元配列で表される迷路を考えてみましょう。0

問題概要 空きマスと壁からなる迷路の中にボールがあります。ボールは上・下・左・右のいずれかの方向に転がって空きマスを進むことができますが、壁にぶつかるまで止まることはできません。ボールが停止したときに、初めて次の方向を選ぶことができます。 ボールのスタート位置、目的地、そして迷路そのものが与えられるので、ボールが目的地で停止するまでの最短距離を求めてください。ここでの距離とは、ボールが転がって通過した空きマスの数のことです（スタート位置は含まず、目的地は含みます）。どうしても目的地で停止できない場合は -1 を返します。 迷路は2次元配列で表現されます。1 が壁、0 が空きスペースを意味し、迷

二分探索木（BST）の中に1つのノードが与えられたとき、そのノードの中間順巡回（in-order traversal）における後継ノードを見つける問題を考えます。中間順後継が存在しない場合はnullを返します。 ここでいう「後継ノード」とは、対象ノードの値より大きいキーの中で最小の値を持つノードのことです。 この問題の特徴として、木のルートには直接アクセスできず、対象のノードのみにアクセスできるという点があります。ただし、各ノードは親ノードへの参照（parentポインタ）を持っています。ノードの定義は以下の通りです。 class Node { public int val;

白と黒のピクセルで構成された画像が与えられ、その中に含まれる「孤独な黒ピクセル（Black Lonely Pixel）」の数を求める問題を考えます。画像は2次元のchar型配列として表現され、各要素は黒ピクセルを表す B、白ピクセルを表す W のいずれかです。 ここで孤独な黒ピクセルとは、その位置と同じ行・同じ列に他の黒ピクセルが一切存在しない B のことを指します。 例として、次のような入力が与えられたとしましょう。 WWBWBWBWW このとき出力は 3 となります。3つの B はいずれも、自分の属する行にも列にも他の黒ピクセルを持たないため、すべてが孤独ピクセルと判定されるからです。 解

問題概要 ある整数 n が与えられたとき、合計がちょうど n になる「正の連続する整数からなるリスト」の個数を求めます。 例えば、入力が n = 15 の場合、出力は 4 になります。条件を満たすリストは次の4つです。 [1, 2, 3, 4, 5] [4, 5, 6] [7, 8] [15] 解法のアプローチ(スライディングウィンドウ) この問題はスライディングウィンドウ(尺取り法)を使うことで効率的に解けます。区間 [begin, end] 内の合計を管理しながら、ウィンドウを伸縮させていくのがポイントです。 具体的な手順は以下の通りです。 begin := 1、end := 1、

2つのソート済みリストが与えられたとき、それらを統合した結果の中央値を求める問題を考えます。例えば、配列が [1,5,8] と [2,3,6,9] の場合、統合すると [1,2,3,5,6,8,9] となり、中央値は 5 になります。 この問題は、二分探索を利用することで非常に効率的に解くことができます。単純に2つの配列をマージしてから中央値を計算する方法では O((m+n) log(m+n)) の計算量が必要ですが、分割位置（パーティション）を二分探索で調整する手法を使えば、O(log(min(m, n))) まで削減できます。 アルゴリズムの手順 solve() 関数を定義します。引数

整数 n が与えられたとき、n番目の「醜い数（Ugly Number）」を求めることを考えます。醜い数とは、その素因数が 2、3、5 のみである数のことです。例えば、10番目の醜い数は 12 になります。小さい方から順に並べると、1、2、3、4、5、6、8、9、10、12、… となるためです。 この問題は、動的計画法を用いることで効率的に解くことができます。基本となる発想は、「すでに求めた醜い数に 2、3、5 を掛けた値もまた醜い数になる」という性質を利用し、重複なく小さい順に次の醜い数を生成していくというものです。 アルゴリズムの手順 (n + 1) サイズの配列 v を定義します。 n

問題の概要入力として整数 N が与えられます。求めるのは、1 ≤ A ≤ N かつ 1 ≤ B ≤ N を満たし、最大公約数 GCD(A, B) が B と一致するようなすべてのペア (A, B) の個数です。つまり、「ペアの最大公約数が B そのものになる」組み合わせをすべて数え上げます。入出力の例入力： N = 5出力： gcd(A, B) が B となるペア (A ≤ N, B ≤ N) の個数 ― 10説明：(1,1), (2,1), (3,1), (4,1), (5,1), (2,2), (3,3), (4,2), (4,4), (5,5) の合計 10 個入力： N = 50出力：

整数Nが入力として与えられ、「各桁に現れる0の個数が偶数個であるN桁の数」が全部でいくつあるかを求めるのがこの問題の目的です。ここで扱う数には先頭の0も含まれます。たとえばN=3の場合、001、002、003…010…といった数もすべて対象になります。 具体例で理解する 入力例1 入力：N=4 出力：0が偶数個含まれるN桁の数の個数は 7047 説明：4桁のすべての数は次のようになります。 最小値は0000、その次は0011、0012、0013、0014……と続き、最大値は9900です。 入力例2 入力：N=5 出力：0が偶数個含まれるN桁の数の個数は 66383 説明：5桁のすべての数は次

整数 N が入力として与えられます。目的は、各桁に含まれる 0 の個数が奇数となる N 桁の数が全部でいくつあるかを求めることです。ここでは先頭の 0 も有効な桁として扱います。たとえば N=3 の場合、000、011、012、…、990 のような数もカウント対象に含まれます。 具体例を使って理解しましょう。 入力 − N=3 出力 − 0 が奇数個含まれる N 桁の数の個数 − 244 説明 − 3 桁の数は次のような並びになります。 最小は 000、続いて 011、012、013、014、…、最大は 990。 入力 − N=5 出力 − 0 が奇数個含まれる N 桁の数の個数 − 336

問題概要 2つの文字列 str_1 と str_2 が入力として与えられます。求めるのは、str_1 に含まれる文字をそれぞれ1回だけ使用して、str_2 と同一の文字列を何個構築できるかという個数です。 注意： 両方の文字列に含まれるアルファベットは、すべて大文字・小文字が統一されているものとします。 具体例で確認してみましょう。 入力： str_1 = abcaaaabca、str_2 = bca 出力： 別の文字列から構築できる文字列の出現回数： 2 説明： str_1 内には bca が次の2箇所に存在します。 str_1[1-3]=bca、str_1[7-9]=bca 入力： str

0、1、2のみで構成された文字列 str が与えられたとき、0・1・2がそれぞれ同数含まれる部分文字列をすべて見つけ、その総数を求めるのが本記事の目的です。例えば str が「12012」の場合、条件を満たす部分文字列は「120」「201」「012」の3つであるため、答えは3となります。 具体例で理解する 入力： str=112200120 出力： 0・1・2の個数が等しい部分文字列の数： 5 説明： 条件を満たす部分文字列は以下の5つです。 str[0-5]=112200、str[1-6]=122001、str[5-7]=012、str[6-8]=120、str[0-8]=1122

文字列 str が与えられたとき、その中に含まれる「最初と最後の文字が同じ」部分文字列の個数を数えるのが本記事の目的です。例えば、入力が baca の場合、条件を満たす部分文字列は b、a、c、a、aca の5つになります。それでは、具体的な例を使って理解していきましょう。入力 − str=abaefgf出力 − 最初と最後の文字が同じ部分文字列の数:9説明 − 条件を満たす部分文字列は以下の通りです。a, b, a, e, f, g, f, aba, fgf。合計9個。入力 − str=abcdef出力 − 最初と最後の文字が同じ部分文字列の数:6説明 − 条件を満たす部分文字列は以下の通り

文字列 str が与えられたとき、「どの文字も最大 k 回までしか出現しない」ような部分文字列の総数を求めるのがこの問題のゴールです。たとえば、入力が "abc"、k=1 の場合、条件を満たす部分文字列は "a"、"b"、"c"、"ab"、"bc"、"abc" の 6 個になります。 例で理解する 入力 − str="bbddehj", k=1 出力 − 各文字が最大 1 回まで出現する部分文字列の数: 14 説明 − 条件を満たす部分

文字列 str が与えられたとき、「先頭の文字が X と一致し、末尾の文字が Y と一致する」部分文字列がいくつあるかを数えるのが本記事の目的です。たとえば、入力が artact、X=a、Y=t の場合、条件を満たす部分文字列は art、act、artact の 3 つとなるため、答えは 3 になります。 具体例で理解する 例 1 入力 − str=abcccdef、X=a、Y=c 出力 − 条件を満たす部分文字列の数: 3 説明 − 該当する部分文字列は次のとおりです。 abc、abcc、abccc。合計 3 個。 例 2 入力 − str=tempest、X=t、Y=t 出力 − 条件を満

問題の概要正の整数からなる配列が与えられたとき、その中から異なる偶数のみを含む部分集合(サブセット)がいくつ作れるかを求めます。要素がまったく同じ集合は重複してカウントせず、1つとして数えます。たとえば [2, 4, 6] と [6, 2, 4] は順序が違うだけなので、同じ集合として扱います。具体的な例で確認してみましょう。例1入力: arr[] = {1, 3, 5, 7, 8, 3, 2}出力: 異なる偶数を含む部分集合の数 → 3解説: 配列に含まれる偶数は 8 と 2 の2種類です。作られる部分集合は [2]、[8]、[2, 8] の3つになります。例2入力: arr[] = {2,

この記事では、文字列 str と長さ3の部分文字列 sub_str が与えられたとき、str の中に sub_str と同じ文字順で現れる部分列（サブシーケンス）が何個あるかを求める方法を解説します。例えば、「act」というパターンは「cataract」という文字列の中に3回部分列として出現します。具体的な例で確認してみましょう。入力例と出力例入力 − str = settlement、sub_str = set出力 − 与えられた文字列における長さ3の部分列の個数：5説明 − 条件を満たす部分列は以下の通りです。1. set tlement, 2. se t t lement, 3. se

問題の概要 正の整数からなる配列が与えられます。目的は、配列内の連続した要素からなる部分配列のうち、「偶数と奇数の要素数が等しい」ものをすべて見つけ、その個数を求めることです。 例として、配列が { 1, 2, 3, 4 } の場合、条件を満たす部分配列は {1,2}、{2,3}、{3,4}、{1,2,3,4} の4つとなり、答えは 4 になります。 入力例と出力例 入力 − arr[] = {1, 3, 5, 7, 8, 3, 2} 出力 − 偶数と奇数の個数が等しい部分配列の数 − 4 説明 − 該当する部分配列は {7, 8}、{8, 3}、{3, 2}、{7, 8, 3, 2} の4つ

正の整数からなる配列が与えられたとき、要素の合計が素数になる部分配列（サブ配列）の個数を求めるのが本記事の目的です。例えば、配列 {1, 2, 3, 4} の場合、隣接する要素からなる部分配列 {1,2}、{2,3}、{3,4} の合計はそれぞれ 3・5・7 となり、いずれも素数であるため、条件を満たす部分配列は 3 個となります。 具体的な例で確認してみましょう。 入力 − arr[] = {1, 3, 5, 3, 2} 出力 − 合計が素数になる部分配列の数: 3 説明 − 該当する部分配列は {3, 2}（合計 5）、{3, 5, 3}（合計 11）、{3, 5, 3, 2}（合計 13

整数 N が入力として与えられ、1からNまでのすべての数値に含まれる桁数の合計を求めるのが本記事の目的です。桁数は数値の大きさに応じて増えていきます。具体的には、1〜9はそれぞれ1桁、10〜99はそれぞれ2桁、100〜999はそれぞれ3桁、というように10倍ごとに桁数が1つずつ増加します。 具体例を見てみましょう。 例1 入力： N = 11 出力： 1からNまでの合計桁数：13 説明： 1〜9は各1桁なので9桁、10と11は各2桁なので4桁。よって合計は 9 + 4 = 13桁 となります。 例2 入力： N = 999 出力： 1からNまでの合計桁数：2889 説明： 1〜9は