C++

はじめに このチュートリアルでは、信号が文字列内のすべての位置に到達するまでにかかる時間を求めるプログラムについて解説します。 問題の概要 x と o で構成された文字列が与えられます。信号は x の位置から発生し、左右の両方向へ伝播していき、1単位時間ごとに隣接する o を 1 つずつ x へと変えていきます。ここでの課題は、文字列全体がすべて x で埋め尽くされるまでに必要な合計時間を計算することです。 アルゴリズムの考え方 この問題は、連続する o のブロック(区間)に着目することで効率的に解くことができます。手順は以下の通りです。 文字列を先頭から走査し、連続した o のブロックごと

このチュートリアルでは、文字列に含まれる重複しない年(ユニークな年)の総数を求めるC++プログラムについて解説します。ここでは、「DD-MM-YYYY」形式の日付を含む文字列が与えられるものとします。私たちのタスクは、その文字列の中に出現する異なる年(重複を除いた年)の個数を数えることです。実装例#include <bits/stdc++.h> using namespace std; // 文字列内に含まれる重複しない年を計算する int calculateDifferentYears(string str) { unordered_set<string> d

このチュートリアルでは、指定されたインデックスの値を更新しながら、任意の範囲内のGCD（最大公約数）を効率的に求めるプログラムについて解説します。 ここでは、整数を要素とする配列とQ個のクエリが与えられます。各クエリに対して、次のいずれかの処理を実行する必要があります。 指定されたインデックスの値を新しい値Xに更新する 指定された2つのインデックス間の要素のGCDを求める アプローチ：セグメント木による高速化 素朴な実装では、更新やGCD計算のたびに範囲内の全要素を走査する必要があり、1回のクエリにO(n)の計算量がかかります。そこで本記事では、セグメント木（Segment Tree）を用

本記事では、C++のBIT（Binary Indexed Tree、フェニック木）を活用して、色付き木の部分木に含まれる「異なる色の数」を効率的にクエリするアルゴリズムを解説します。 問題の概要 根付き木が与えられ、各ノードには配列で指定された色が割り当てられています。ここで求めたいのは、指定されたノードを根とする部分木（そのノードより下位に存在するすべてのノード）の中に、何種類の異なる色が含まれているかということです。 アルゴリズムの考え方 木構造をそのまま扱うと部分木ごとの集計が難しいため、この手法では問題を「配列上の区間クエリ」に変換して処理します。ポイントは次の3つです。 DFSによ

このチュートリアルでは、配列内の「L番目に小さい値」と「R番目に小さい値」のインデックスの絶対差を求めるクエリ処理について解説します。 整数からなる配列とQ個のクエリが与えられます。各クエリは2つの整数L・Rから構成され、元の配列におけるL番目に小さい値とR番目に小さい値のインデックスの絶対差を計算して出力するのが課題です。 問題のポイント ここで求めるのは「値同士の差」ではなく、それぞれの値が元の配列のどこに位置していたかという「インデックスの差」である点に注意してください。 例として、配列 arr = {1, 7, 4, 2, 8} を値の昇順に並べると次のようになります。 1（インデッ

この記事では、N以下の3つの整数のうち、LCM(最小公倍数)が最大になる組み合わせを見つける方法について解説します。 問題の概要 整数 N が与えられたとき、N 以下の範囲から3つの整数を選び、その3数の最小公倍数(LCM)ができるだけ大きくなるような組み合わせを求めるのが課題です。 実は、最大のLCMを与える3つの整数は必ず N に近い値の中から選ばれることが知られています。そのため、N・N−1・N−2・N−3 という4つの候補だけで場合分けすれば、効率よく答えを導き出すことができます。 アルゴリズムの考え方 連続する2つの整数は互いに素(最大公約数が1)であるため、なるべく大きい数同士を組

このチュートリアルでは、木構造（ツリー）において、あるノードが別のノードの祖先であるかどうかを効率的に判定するプログラムについて解説します。 具体的には、根付き木とQ個のクエリが与えられます。各クエリで指定された2つのノードのうち、一方がもう一方の祖先であるかどうかを判定するのがタスクです。 アルゴリズムの考え方 この問題は、DFS（深さ優先探索）を利用して各ノードに「入った時刻」と「出た時刻」のタイムスタンプを記録することで、高速に解くことができます。 timeIn[u]：ノードuに最初に到達した時刻（行きかけ順） timeOut[u]：ノードuのすべての子孫の探索を終えて出発する時刻（

数値が埋め込まれた正方形の迷路を考えます。この迷路において、四隅のセル(コーナーセル)から中央のセル(ミドルセル)までのすべての経路を見つけることが目的です。移動のルールは次のとおりです。あるセル [i, j] に書かれた値を n とすると、上下左右の4方向にちょうど n ステップ進む必要があります。つまり、[i+n, j]、[i-n, j]、[i, j+n]、[i, j-n] のいずれかのセルへ移動できます。移動先が迷路の範囲外になる場合は、その方向には進めません。入力例以下のような 9×9 の迷路が与えられたとします。344473463675662662334325472655123656

問題概要k個の異なるリストがあり、それぞれの要素は昇順にソートされているとします。このとき、k個のリストすべてから少なくとも1つの数値を含む最小の範囲 [a, b] を求めます。範囲の大小関係は次のように定義されます。b - a < d - c の場合、範囲 [a, b] は範囲 [c, d] より「小さい」とみなすb - a == d - c の場合は、開始位置を比較し、a < c なら [a, b] の方が「小さい」とみなす例えば、入力が [[4,10,15,25,26], [0,9,14,20], [5,18,24,30]] の場合、出力は [14, 18] となります。14

問題概要 二分探索木（BST）とターゲット値が与えられたとき、BST内の値の中からターゲットに最も近いk個の値を見つけることを考えます。ここで、ターゲット値は浮動小数点数である点に注意してください。なお、kは常に有効であり、k ≤ 全ノード数が成り立つものと仮定できます。 例として、次のような木を考えてみましょう。 target = 3.714286、k = 2 の場合、出力は [4, 3] となります。 解法のアプローチ この問題は、「ターゲットより小さい値」を管理するスタックと「ターゲット以上の値」を管理するスタックの2本を用いることで効率的に解けます。各スタックには中間順走査（in-

「L」と「R」のみで構成される文字列を考えます。「L」は左回転(left rotation)、「R」は右回転(right rotation)を表します。このとき、コンパスの針(ピボット)が最終的に向く方向を求めるのが本記事の目的です。取り得る方向は北(N)、東(E)、南(S)、西(W)の4つで、初期状態ではピボットは北(N)を向いているものと仮定します。例えば、入力が「RRLRLLR」の場合、出力は「E」になります。処理の流れを追ってみましょう。初期方向はNです。最初の「RR」で南(S)を向き、続く「LR」で再び北(N)に戻ります。その後の「LL」でも向きは北(N)のまま変わりません。最後の「

問題概要N個の数値からなる配列があり、そのうち1つの要素を除いて、すべての要素が同じ回数(m回、この値も与えられる)だけ出現するとします。この「例外となる要素」を見つけるのが課題です。例えば、入力が A = [6, 2, 7, 2, 2, 6, 6]、m = 3 の場合を考えてみましょう。ほとんどの要素は3回ずつ現れていますが、7だけは1回しか現れないため、出力は 7 となります。解法のアプローチ:ビットごとのカウントこの問題は、各ビット位置に注目するビット演算のテクニックを使うことで効率的に解くことができます。手順は以下の通りです。INT_SIZE := 整数型変数のバイトサイズ × 8(=

問題の概要配列Aがあるとします。この配列には2回出現する数値がいくつか含まれていますが、1回だけ出現する数値は1つのみです。この配列から、その唯一の要素を見つけ出す必要があります。例えば、A = [1, 1, 5, 3, 2, 5, 2] の場合、出力は 3 になります。すべての数値が2回ずつ出現しているため、XOR（排他的論理和）を使うと重複する要素を互いに打ち消すことができます。これは「y XOR y = 0」というXORの性質を利用したテクニックです。アルゴリズムの手順変数 res = 0 を用意します配列Aの各要素 e に対して、res := res XOR e を実行します最後に r

問題概要 2次元行列 mat と値 K が与えられたとき、要素の合計がちょうど K に等しくなる長方形の部分行列のうち、面積が最大のものを見つけることを考えます。 たとえば、入力が以下の行列であったとします。 28-56 -778-3 11-1443 -43110 ここで K = 9 とした場合、出力は「左上の座標が (1, 0)」「右下の座標が (3, 2)」となります。実際に該当する部分行列は次の通りです。 -778 11-144 -431 この部分行列の合計を確認してみましょう。(-7 + 7 + 8) + (11 - 14 + 4) + (-4 + 3 + 1) = 8

問題の概要さまざまな数字が格納された配列が与えられます。その中からいくつかの数字を選び、任意の順序で連結することで作成できる「3の倍数」の最大値を求めるのが課題です。答えは非常に大きな数になる可能性があるため、文字列として返します。答えが存在しない場合は空文字列を返してください。例えば、入力が [7, 2, 8] の場合、出力は 87 となります。解法のアプローチこの問題は「3の倍数の性質」を利用することで効率的に解けます。ある整数が3の倍数であるための必要十分条件は、その各桁の合計が3で割り切れることです。そこで、数字を3で割った余り(0・1・2)ごとにグループ分けし、合計が3の倍数になるよ

2つの配列 A と B(いずれも n 個の整数を持つ)が与えられたとします。ここで、B の要素をうまく並べ替えることで、(A[i] + B[i]) % n で構成されるシーケンスが辞書式順序で最小になるようにします。最終的に、その最小のシーケンスを返すのが目的です。たとえば、入力が A = {1, 2, 3, 2}、B = {4, 3, 2, 2} の場合、出力は [0, 0, 1, 2] となります。解法の考え方この問題は貪欲法(greedy法)で解くことができます。各位置 i において、(a[i] + b) % n が最小になるような b を残っている候補の中から選んでいく方針です。(a[

問題の概要 ペア（組）からなる配列 A が与えられたとき、最大 K 個のペアを選択した場合のコストの最大値を求めることを考えます。ここで、選択したペア群のコストは次のように定義されます。 コスト =（選択したペアの第1要素の合計）×（選択したペアの中で第2要素の最小値） 例えば、(4, 8)、(10, 3)、(3, 6) の3つのペアを選んだ場合（K = 3）、コストは (4 + 10 + 3) × 3 = 51 となります。 入力例と出力例 次のような入力を考えてみましょう。 A = [(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15,

問題概要 N個の異なる長方形について、それぞれの幅と高さが与えられているとします。このとき、ある長方形を別の長方形の中へ入れ子状に挿入していった後、最終的に残る長方形の数の最小値を求めるのが本記事のテーマです。 ここで、長方形R1とR2の幅をそれぞれW1・W2、高さをH1・H2とすると、W1 < W2 かつ H1 < H2 が成り立つ場合に限り、長方形R1は長方形R2の中に完全に収まります。この性質により、最も小さな長方形は2番目に小さな長方形の中へ、さらにそれは次の長方形の中へ、というように順々に入れ子にしていくことが可能です。 入力例と出力 例えば、入力が {{30, 45},

問題概要数直線上の初期位置を表す整数Nと、左方向へ移動する確率Lが与えられます。点Nを出発してN回の移動を完了したとき、数直線上の各点に到達する確率をすべて求めます。なお、1回の移動ごとに、必ず左または右のどちらかに1だけ進むものとします。例えば、入力が n = 2、l = 0.5 の場合、出力は [0.25, 0, 0.5, 0, 0.25] となります。これは、2回の移動後に位置0・2・4へそれぞれ到達する確率を表しています。解法のアプローチこの問題は動的計画法(DP)を使うことで効率的に解けます。「i回目の移動後に位置jにいる確率」を二次元配列A[i][j]に格納しながら、段階的に確率を

重み付き無向グラフにおいて、特定のノードが「良好ノード」として指定されている場合、任意の2つの異なる良好ノード間の最短距離を求める問題について解説します。以下の図では黄色のノードが良好ノードを表しています。 問題の概要 N個のノードとM本のエッジを持つ重み付き無向グラフが与えられます。そのうちK個のノードが良好ノードとしてマークされています。すべての良好ノードのペアについて最短経路距離を計算し、その中で最小の値を求めます。 アルゴリズムの手順 各良好ノードを始点としてダイクストラ法を実行し、他の良好ノードへの最短距離を求めます。計算量を削減するため、現在の最良結果より距離が大きくなった時点