C++

正の整数が与えられたとき、それが交互ビット（alternating bits）を持つかどうかを判定することを考えます。つまり、2進表現において隣り合うどの2つのビットも、必ず異なる値になっている状態です。 例えば、入力が「10」の場合、10の2進表現は「1010」であり、1と0が交互に並んでいるため、出力は True となります。 解法のアプローチ この問題は、ビット演算を用いて下位ビットから順番に確認していくことで解決できます。手順は以下の通りです。 p := n AND 1（n の最下位ビットを p に保存する） n < 2 の場合は true を返す（1桁のビットは自動的に条件

問題概要文字列 s が与えられたとき、「0 の個数と 1 の個数が等しく、かつすべての 0 とすべての 1 がそれぞれ連続してまとまっている」ような部分文字列の総数を求めます。同じ内容の部分文字列が複数回現れる場合は、出現した回数だけカウントします。例えば、入力が 11001100 の場合、条件を満たす部分文字列は 1100、10、0011、01、1100、10 の 6 つとなるため、出力は 6 になります。解法の考え方この問題は、文字列を一度走査するだけで O(n) の計算量で解くことができます。ポイントは「現在の文字が連続している回数」と「直前まで別の文字が連続していた回数」を比較するとい

問題の概要 負でない整数からなる配列 nums があるとします。この配列の「次数（degree）」とは、配列内のいずれか一つの要素が出現する最大頻度のことです。ここでの課題は、nums と同じ次数を持つ連続した部分配列のうち、可能な限り短い長さを見つけることです。 例えば、入力が [1, 2, 2, 3, 1] の場合、出力は 2 になります。これは、入力配列において要素 1 と 2 がそれぞれ2回出現しているため、配列の次数は 2 となるからです。同じ次数 2 を持つ部分配列には、次のようなものがあります。 [1, 2, 2, 3, 1] [1, 2, 2, 3] [2, 2, 3, 1]

グリッド内の魔方陣とは 与えられたグリッドの中に、「魔方陣（マジックスクエア）」の条件を満たす3×3の部分グリッドがいくつ含まれているかを求める問題を考えてみましょう。ここでいう魔方陣とは、1から9までの相異なる数字で埋められた3×3の格子であり、各行・各列・そして両対角線の合計がすべて等しいものを指します。 たとえば、次のような入力が与えられたとします。 438495192762 この場合の出力は 1 になります。左上にある次の3×3の部分グリッドが魔方陣を形成しているためです。 438951276 実際に確かめてみると、どの行も列も対角線も合計が15になっており、魔方陣の条件を満たしてい

問題概要整数が書かれたカードのデッキが与えられます。このとき、X ≥ 2 となる整数 X を選び、デッキ全体を1つ以上のグループに分割できるかどうかを判定します。分割は以下の条件を満たす必要があります。各グループはちょうど X 枚のカードで構成されている同じグループ内のカードには、すべて同じ整数が書かれている例えば、入力が deck = [1,2,3,4,4,3,2,1] の場合、出力は True になります。[1,1]、[2,2]、[3,3]、[4,4] という4つのグループに分割でき、それぞれのグループが2枚の同じ数字のカードで構成されているためです。解法のアプローチこの問題は「最大公約数

問題概要4つの数字が格納された配列が与えられます。これらの数字をすべて使い、作成できる最大の24時間制の時刻を求めてください。最も早い時刻は 00:00、最も遅い時刻は 23:59 です。00:00 を基準として、深夜0時からの経過時間が長いほど「大きい」時刻とみなします。答えは必ず5文字の文字列(HH:MM 形式)として返し、有効な時刻を構成できない場合は空文字列を返します。たとえば、入力が [1, 2, 3, 4] の場合、出力は 23:41 になります。解法のアプローチこの問題は、深さ優先探索(DFS)とバックトラッキングを組み合わせ、4桁の数字の全順列を試すことで解けます。具体的な手順

はじめにこの記事では、全員に同じボーナス点を加算しても、どの学生も100点を超えないという条件下で、合格できる学生の最大人数を求めるC++プログラムについて解説します。具体的には、N人の学生の点数が格納された配列が与えられます。各学生に同じ量のボーナス点を加えることで、より多くの学生(合格ラインは50点)を合格させることが目的です。ただし、加点によってどの学生も100点を超えてはいけません。アルゴリズムの考え方この問題は次の手順で解くことができます。まず、配列内の最高得点を見つけます。最高得点の学生がちょうど100点になるようにボーナス点を計算します(ボーナス = 100 − 最高得点)。これ

このチュートリアルでは、「そのサイズのすべてのサブ配列(部分配列)の合計がk未満となる、最大のサブ配列サイズ」を求めるプログラムについて解説します。 サイズNの配列と整数kが与えられます。求めるのは、与えられた配列内のその長さのすべてのサブ配列の合計がk以下となるようなサブ配列の長さです。 アルゴリズムの考え方 この問題は「累積和(プレフィックスサム)」と「二分探索」を組み合わせることで、O(N log N)の計算量で効率的に解くことができます。 解法の手順 1. 配列の累積和を事前に計算します。これにより、任意の区間の合計をO(1)で取得できます。 2. サブ配列の長さを候補として二分探索を

はじめに このチュートリアルでは、特定の要素を除外した状態で最大となる部分配列和(Maximum Subarray Sum)を求めるプログラムを、C++で実装する方法を解説します。 ここで扱う問題は次の通りです。サイズNの配列Aと、サイズMの配列Bが与えられます。このとき、「部分配列内のどの要素も配列Bに含まれていない」という条件を満たす配列Aの部分配列の中から、要素の合計が最大になるものを見つけてください。 アルゴリズムの考え方 この問題は、最大連続部分配列和を求める有名なKadane(カダネ)のアルゴリズムを応用することで効率よく解けます。手順は以下の通りです。 配列Aを先頭から順に走査

このチュートリアルでは、配列を繰り返し連結して作成される配列における最大サブ配列合計（Maximum Subarray Sum）を求めるC++プログラムについて解説します。具体的には、1つの配列と整数Kが与えられ、元の配列をK回繰り返して連結した配列の中から、要素の合計が最大となる連続する部分配列（サブ配列）を見つけることが課題となります。アルゴリズムのポイントこの問題は、有名なカダネのアルゴリズム（Kadanes Algorithm）を応用することで効率的に解けます。ループは n * k 回実行します（連結後の配列全体を走査）。a[i % n] のように剰余演算を使うことで、実際に大きな配列

このチュートリアルでは、「1の個数が0の個数よりちょうど1つ多くなるような、面積が最大の部分行列」を見つけるプログラムについて解説します。 問題の概要 0と1のみで構成された2次元行列が与えられます。ここで求めたいのは、含まれる1の数が0の数よりも多い部分行列の中で、面積（行数 × 列数）が最大になるものです。 例えば、次のような4×4の行列を考えてみましょう。 { 1, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 1 } この場合、条件を満たす最大の部分行列は左上 (1,1) から右下 (3,3) までの3×3の領域となり、その

本記事では、「同じ位置の要素を3つ連続して選ばない」という制約のもとで、数列から選んだ要素の合計を最大化する問題を解くプログラムについて解説します。具体的には、正の整数列が与えられたとき、部分列として要素を選んでいく過程で3つ連続した要素を同時に選ぶことはできません。この条件下で実現できる合計値の最大値を求めるのが目的です。動的計画法によるアプローチこの問題は動的計画法(DP)を用いることで効率的に解くことができます。位置 i までの最大合計を sum[i] とするとき、i 番目の要素の扱い方は以下の3通りに分けられます。i 番目を選ばない場合: sum[i-1]i 番目だけを選ぶ場合(i-1

はじめにこのチュートリアルでは、二分木（Binary Tree）の中から「二分探索木（BST）」の条件も満たす部分木を探し出し、そのノード値の合計が最大になる部分木を求めるプログラムについて解説します。入力として二分木が与えられ、その中に存在する部分木のうちBSTの性質を満たすものの合計値を計算し、最大のものを出力するのが目的です。アルゴリズムの考え方この問題を効率的に解く鍵は、各ノードを再帰的に走査しながら、次の情報を持ち回ることです。部分木内の最大値（max）部分木内の最小値（min）その部分木がBSTかどうか（isBST）部分木のノード値の合計（sum）それまでに見つかった最大合計（cu

はじめに本記事では、C++を用いて「最大和の交互部分列（Alternating Subsequence）」を求めるプログラムについて解説します。ここで扱う問題は、整数型の配列が与えられたとき、その中から「減少→増加→減少→…」というように増減が交互に入れ替わる部分列を抜き出し、その要素の合計値が最大となるものを見つけるというものです。アルゴリズムの考え方この問題は動的計画法（DP）を用いて解くことができます。具体的には、以下の2つの配列を用意します。dec[i]: i番目の要素で終わる交互部分列のうち、「直前の操作が減少」である場合の最大和inc[i]: i番目の要素で終わる交互部分列のうち、

この問題では、数値を表す文字列が与えられます。C++を用いて、その数値の中からM個の連続する桁で構成される部分列をすべて調べ、和と積がそれぞれ最大となる値(maxSum・maxProd)を求めるプログラムを作成します。問題の概要数値からM個の連続する桁で構成されるすべての部分列を抽出し、その中で最大の和と最大の積を返します。具体例を使って問題を確認してみましょう。入力number = 2379641, M = 4出力maxSum = 26maxProd = 1512説明サイズ4の連続する部分列は「2379」「3796」「7964」「9641」の4つです。maxSum = 7 + 9 + 6 +

この記事では、配列 arr[] が与えられたときに、C++ を使って最大合計のバイトニック部分配列（Bitonic Subarray）を求めるプログラムの作成方法を解説します。バイトニック部分配列とは？バイトニック部分配列とは、ある特定の地点を境にして、それまでの要素が厳密に増加し続け、その後は厳密に減少し続けるという特殊な性質を持つ部分配列のことです。問題を理解するための例入力arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1}出力30説明この入力におけるバイトニック部分配列は [2, 3, 7, 9, 6, 3] です。合計 = 2 + 3 + 7 + 9 + 6 + 3

この問題では、整数の配列 arr[] が与えられ、C++ を使って「最大和ビトニック部分列(Maximum Sum Bitonic Subsequence)」を求めるプログラムを作成します。 ビトニック部分列(Bi-tonic subsequence)とは、要素がまず増加し続け、途中から減少に転じるという特性を持つ特別な部分列のことです。 問題を理解するための例 入力 arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1} 出力 33 説明 合計が最大となるビトニック部分列は {2, 3, 7, 9, 6, 5, 1} です。 合計 = 2 + 3 + 7 + 9 + 6 +

はじめに 本記事では、N個の整数からなる配列 arr[] が与えられたとき、その中から厳密に減少する部分列を抜き出し、要素の合計が最大になる値（最大和減少部分列）をC++で求める方法を解説します。 問題の概要 配列の中から要素を選び、選んだ順序が左から右へ単調減少となるように部分列を作ります。そのとき、部分列の要素の合計として考えられる最大値を求めるのが目的です。 具体例で確認してみましょう。 入力例 arr[] = {3, 1, 6, 10, 5, 2, 9} 出力例 17 解説 この場合、合計が最大となる減少部分列は {10, 5, 2} です。10 + 5 + 2 = 17 が答えとな

このチュートリアルでは、さまざまなプログラミング言語において、2つの変数の値を入れ替える（スワップする）方法を解説します。スワップとは、2つの変数が持つ値をお互いに交換することです。まずは具体例を見てみましょう。 入力 a = 3 b = 5 出力 a = 5 b = 3 それでは、言語ごとに順番に見ていきましょう。 Pythonの場合 Pythonでは、わずか1行のコードで変数をスワップできます。タプルのアンパックという機能を利用した、非常にシンプルな書き方です。以下のコードをご覧ください。 コード例 # 変数の初期化 a, b = 3, 5 # スワップ前の値を出力 print(Befo

本記事では、n個の一意な文字列からなる配列が与えられたとき、以下のルールに従って各単語に対して可能な限り短い略語を生成する問題をC++で解く方法を解説します。問題のルール略語は「最初の1文字 + 省略された文字数 + 最後の1文字」の形式で表します。複数の単語が同じ略語になってしまう衝突（conflict）が発生した場合は、先頭1文字だけではなくより長いプレフィックス（接頭辞）を使うことで、単語から略語への対応が一意になるまで調整します。略語化しても元の単語より短くならない場合は、元の単語をそのまま使用します。入力例と出力例たとえば、次のような入力が与えられたとします。[like, god,