C++

任意の長さの文字列と整数値 k が与えられたとき、ASCII値が k 未満のアルファベットと、k 以上のアルファベットの個数をそれぞれ求めるのが本記事の目的です。アルファベット大文字(A〜Z)のASCIIコード一覧ABCDEFGHIJKLMNOPQRS65666768697071727374757677787980818283TUVWXYZ84858687888990アルファベット小文字(a〜z)のASCIIコード一覧abcdefghijklmnopqrs979899100101102103104105106107108109110111112113114115tuvwxyz116117118

整数 num が与えられたとき、num より小さい数の中で、num との XOR(排他的論理和)を取った結果が num 自身の値よりも大きくなるものの個数を求めるのが、この記事のテーマです。 XOR演算の真理値表 XOR は、2つのビットが異なる場合に 1 を返し、同じ場合に 0 を返すビット単位の演算です。真理値表は以下の通りです。 ABA XOR B 000 101 011 110 入出力例 例1:num = 11 の場合 入力 − int num = 11 出力 − n とのXORがより大きな値になる小さい数の個数 − 4 説明 − num が 11 ということは、11 未満の

整数 x が与えられたとき、x 未満の数 y のうち「y と x の XOR（排他的論理和）を計算すると、結果が x より大きくなる」ような値の個数を数える問題を考えてみましょう。すべての組み合わせを順に調べる必要があるように見えますが、x を2進数で捉えることで少ない計算量で答えを求められる、ビット演算ならではの性質を利用した問題です。 XOR演算の真理値表 ABA XOR B 000 101 011 110 入力例と出力例 例1：x = 11 の場合 入力：int x = 11 出力：条件を満たす値の個数は 4 1〜10 の各数と x との XOR を計算すると、1 XOR 11

配列が与えられたとき、その要素を循環的（リング状）につなげた部分配列の中から、合計が最大となるものを求めるのが本記事の目的です。循環配列では、末尾の要素の次が先頭の要素に戻るため、通常の最大部分配列問題（カデーンのアルゴリズム）よりも少し工夫が必要になります。入出力例例1入力： int arr[] = {1, 2, 8, 4, 3, 0, 7}出力： 最大循環部分配列の合計は 22解説： 配列 {1, 2, 8, 4, 3, 0, 7} が与えられています。循環を考慮すると、末尾の「7」に先頭の「1」「2」をつなげられるため、7 + 1 + 2 + 8 + 4 = 22 が最大の合計となります

本記事では、行と列から構成される2次元配列（行列）が与えられたとき、すべての行と列の合計を計算し、その値が主対角線または副対角線の合計と一致する個数を求める方法を解説します。 入力例1 int arr[row][col] = {     { 4, 1, 7 },     { 10, 3, 5 },     { 2, 2, 11} } 出力 対角線の合計と等しい行・列の個数：2 説明 主対角線の合計は 4 + 3 + 11 = 18、副対角線の合計は 7 + 3 + 2 = 1

整数型の要素からなるソート済み配列と、ある整数 num が与えられたとき、その要素が配列内に何回出現するか（＝頻度）を求めるのが本記事の目的です。入力例と出力例入力：int arr[] = {1, 1, 1, 2, 3, 4}、num = 1出力：ソート済み配列内の出現回数は − 3入力：int arr[] = {2, 3, 4, 5, 5, 6, -7}、num = 5出力：ソート済み配列内の出現回数は − 2入力：int arr[] = {-1, 0, 1, 2, 3}、num = 7出力：ソート済み配列内の出現回数は − 0解法のアプローチこの問題を解くには複数の方法があります。ここでは

整数型の要素からなる配列が与えられ、その中からGCD(最大公約数)が1となる部分列を見つけ出し、その個数を求めるのが今回の課題です。GCD(最大公約数)とは、2つ以上の整数をすべて余りなく割り切ることができる整数のうち、最も大きいものを指します。 入力例と出力例 入力 − int arr[] = {3, 4, 8, 16} 出力 − GCDが1となる部分列の個数 − 7 説明 −与えられた配列から作成できる、GCDが1となる部分列は (3, 4)、(3, 8)、(3, 16)、(4, 3)、(8, 3)、(16, 3)、(3, 4, 8) の7つです。 入力 − int arr[] = {5

問題概要 相異なる整数のリスト nums が与えられます。この中から、リスト内の数値を最大1つしか含まない区間 [start, end](両端を含む)のうち、最も長いもののサイズを求めましょう。 例えば、nums = [10, 6, 20] が入力された場合、出力は 99990 となります。これは、最も長い区間が [11, 100000] であり、この区間には 20 のみが含まれるためです。 解法のアプローチ この問題は、配列をあらかじめソートしておき、各数値について「その数値のみを含む区間」を隣接する数値の位置から求めることで効率よく解けます。手順は以下の通りです。 ret := −inf

整数のリスト nums があるとします。ここで、「リスト内のいくつかの整数（部分集合）を選び、選んだ値をすべて1つずつ増やす」という操作を考えます。この操作を繰り返してリスト内のすべての値を等しくするとき、必要となる最小の操作回数を求めるのが本問題です。 例えば、入力が [1,3,5] の場合、出力は 4 になります。 解法のポイント 一見複雑な問題に見えますが、実は答えはとてもシンプルで、リスト内の最大値と最小値の差がそのまま最小操作回数になります。 その理由は次のとおりです。1回の操作で増やせるのは選んだ要素だけなので、最小値の要素を最大値まで引き上げるには、少なくとも「最大値 − 最小値

問題概要2次元の区間リストが与えられます。各区間は [start, end]（開始値と終了値）の2つの値で表されます。このリストの中に、別の区間を完全に含んでいる区間が存在するかどうかを判定するのがこの問題の目的です。たとえば、入力が [[2,4],[5,11],[5,9],[10,10]] の場合を見てみましょう。[5,11] という区間が [5,9] を含んでいるため、出力は true（真） となります。解決のためのアプローチこの問題は、区間を適切にソートしてから線形走査を行うことで効率的に解くことができます。具体的な手順は以下の通りです。まず、配列 v を「終了値の昇順」でソートします（

問題の概要整数のリスト nums が与えられたとき、このリストを2つの空でない部分リストに分割できるかどうかを判定します。ただし、左側の部分リストに含まれるすべての数値は、右側の部分リストに含まれるすべての数値よりも厳密に小さい必要があります。例えば、入力が [6, 4, 3, 8, 10] の場合を見てみましょう。left = [6, 4, 3]、right = [8, 10] と分割すると、左側の最大値 6 は右側の最小値 8 より小さいため、出力は true（1）になります。解決のアプローチこの問題は、プレフィックス最大値（左側からの累積最大値）とサフィックス最小値（右側からの累積最小値

問題の概要0と1のみを含む整数配列 nums が与えられます。使用できる操作は次の1種類です。インデックス i を1つ選び、その位置の要素と、それより右側にあるすべての要素を反転する(0を1に、1を0に変更する)というものです。この操作を繰り返して、配列のすべての要素を0にするために必要な最小の操作回数を求めます。具体例例えば、入力が [1, 0, 1] の場合、出力は 3 になります。操作の流れは以下のとおりです。インデックス 0 に対して操作を実行 → 配列は [0, 1, 0] になるインデックス 1 に対して操作を実行 → 配列は [0, 0, 1] になるインデックス 2 に対して操

問題の概要「L」「R」「?」のいずれかの文字で構成される文字列 s があるとします。「L」は左へ1単位移動すること、「R」は右へ1単位移動することを意味し、「?」は「L」または「R」のどちらにでも置き換え可能な文字です。初期位置が0であるとき、「?」を適切に置き換えることで、原点から到達できる最大距離を求めます。例えば、入力が LLRRL?? の場合、出力は 3 となります。「?」をすべて「L」に置き換えると、左へ5単位、右へ2単位移動することになり、最大変位は 5 − 2 = 3 だからです。解法のアプローチこの問題は、次の手順で効率的に解くことができます。カウンタ op（「?」の個数）、l

2値(0と1のみで構成される)行列が与えられたとき、1つの行を反転し、その後1つの列を反転することで、得られる「1」の最大数を求める問題をC++で解く方法を解説します。 問題の例 たとえば、次のような入力行列を考えてみましょう。 101 010 100 この場合、最適な行と列を選んで反転すると、出力は 8 になります。 解法のアプローチ この問題は、全探索を行う代わりに、行ごと・列ごとの「1」の個数を事前に集計することで効率的に解けます。手順は以下の通りです。 n := 行列の行数 m := 行列の列数 ret := 0(答えを格納する変数) サイズ n の配列 row を定義(

この記事では、非負の整数 num が与えられたとき、それが回文数（パリンドローム）であるかどうかを判定する方法を解説します。ポイントは、文字列に変換せずに数値演算だけで判定するという点です。例えば、入力が 1331 の場合、逆から読んでも「1331」となるため、出力は true になります。アルゴリズムの考え方文字列を使わずに回文を判定するには、元の数値を数学的に反転（逆順に並べ替え）し、元の数値と一致するかを比較します。手順は以下の通りです。結果を格納する変数 ret を 0 で初期化する元の値を保存するため、x := num としてコピーしておくnum > 0 の間、以下を繰り返すd

問題概要 重複のない整数のリスト nums が与えられます。このリストの中から、標準的な二分探索（バイナリサーチ）の手順に従って実際に見つけ出せる整数が何個あるかを求めるのが課題です。 たとえば、入力が [2,6,4,3,10] の場合、出力は 3 になります。二分探索で 4 を探すと最初の反復で見つかり、2 と 10 は2回の反復後に見つかるためです。 解き方のアプローチ この問題は、リスト内の各要素を「探索対象」として実際に二分探索を実行し、その探索が成功するかどうかを確認するというシンプルな方針で解けます。具体的には、以下の手順に従います。 help() 関数を定義する：引数として探

問題の概要整数のリスト nums が与えられたとき、以下のルールに従ってリストを並べ替えることを考えます。1番目の要素は最大値2番目の要素は最小値3番目の要素は2番目に大きい値4番目の要素は2番目に小さい値以降も同様に、大きい値と小さい値を交互に配置していきます。たとえば、入力が [6, 3, 10, 4] の場合、出力は [10, 3, 6, 4] となります。解法のアプローチこの問題は、配列をあらかじめ昇順にソートしておき、両端から交互に要素を取り出すことで解決できます。具体的な手順は以下の通りです。結果を格納するための配列 ret を定義します。配列 nums を昇順にソートします。j

この記事では、C++を使って「ビール瓶の交換問題」を解くアルゴリズムを紹介します。数値 n が与えられ、これは満杯のビール瓶が n 本あることを表します。空き瓶3本を満杯のビール瓶1本と交換できる場合、最終的に何本のビールが飲めるかを求めるのが目的です。例えば、入力が 10 の場合、出力は 14 になります。問題の流れ10本の場合を具体的に見てみましょう。まず10本すべて飲みます（合計10本）。空き瓶が10本できます。空き瓶9本を交換して、満杯の瓶3本をもらいます。さらに3本飲みます（合計13本）。この時点で空き瓶は残り1本＋新たな3本＝4本です。うち3本を交換して1本もらい、飲みます（合計1

問題の概要整数の区間を表すリストのリストが与えられます。各要素は [start, end] のような形式の区間です。この中から、最も多くの区間に含まれる数（最頻出数）を見つける必要があります。複数の候補が同数の場合は、その中で最も小さい数を返します。たとえば、入力が [[2, 5], [4, 6], [7, 10], [8, 10]] の場合、出力は 4 になります。解法のアプローチこの問題は、いもす法（差分配列）として知られる手法を使うと効率的に解けます。各区間 [start, end] について、開始位置でカウントを +1、終了位置の次の位置で -1 します。その後、キーを昇順に走査しなが

問題の概要時刻 t にドアの前へ到着した人物が、建物の内側に入りたい(1)のか、外側に出たい(0)のかを表すリクエスト requests[i] = [t, d] のリストが与えられます。ドアは1つだけで、1人の通過に1単位時間かかります。このとき、次のルールに従う必要があります。ドアの初期状態：「内側方向(in)」から始まり、以降は最後に使用した人物の方向にセットされます。1人だけの場合：ある時刻 t にドアの前にいるのが1人だけであれば、その人はすぐにドアを利用できます。複数人がいる場合：2人以上が同時に並んでいるときは、より早く到着した人物が先に通り、その後は直前に使用された方向が優先され