C++

ここでは、大きなオブジェクト（例として「大きいおもちゃ」）と小さなオブジェクト（「小さいおもちゃ」）が与えられる問題を扱います。オブジェクトの種類は利用者が自由に決められますが、本稿ではサイズの特徴によって大きいもの・小さいものに分けられるおもちゃを例に取り上げます。求めるのは、小さいおもちゃを引き換えに渡すことで手に入る、大きいおもちゃの最大数です。 入出力の例 入力：big_toys = 8, small_toys = 20, a = 6, b = 4出力：大きいものと小さいものの両方を交換できる場合の大きいおもちゃの最大数：11 解説：20個ある小さいおもちゃを使って引き換えられる大きい

整数要素からなるソートされていない配列が与えられたとき、次の2つの条件を満たす区間の最大長を求めるのが課題です。セットビット（2進表現で1になっているビット）の数が互いに等しいことその要素同士が配列内で連続（隣接）していることここでは、C++を使ってこの問題を効率的に解く方法を、具体例とサンプルコード付きで解説します。入力例と出力例例1int arr[] = { 5, 8, 1, 2, 9, 12 }出力 − セットビット数が同じ連続する配列要素の最大数: 3説明 − 各要素を2進数に変換し、セットビットの数を数えます。arr[0] = 5 => 0101 => セットビット数

任意のサイズの整数型配列が与えられたとき、「隣接する要素間の差が0または1」という条件を満たす最大長の部分配列(サブ配列)を見つけることが本記事の課題です。問題例入力 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }出力 − 隣接要素間の差が0または1となる最大長の部分配列の長さ − 2説明 − 差が0または1となる隣接要素の組は {2, 1}、{5, 6}、{3, 4}、{7, 6} の4つです。いずれも長さが2であるため、最大長の部分配列の長さは2となります。入力 − int arr[] = { 2, 1, 7, 6, 5 }出力 − 隣接要素間の差が0また

任意のサイズの整数配列が与えられ、その中から「隣接する要素同士の差が0または1」という条件を満たす部分列(サブシーケンス)のうち、最も長いものを見つけるのが本記事のテーマです。 問題の例 入力 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 } 出力 − 隣接する要素間の差が0または1となる部分列の最大長は: 3 説明 − 例えば {5, 6, 7} や {6, 7, 6} のように、隣接する要素間の差がすべて0または1となる部分列を選ぶことができます。これらの長さは3となり、これが最大長です。 入力 − int arr[] = { 2, 1, 7, 6, 5

問題の概要任意のサイズの整数配列が与えられたとき、「隣接する要素同士の差が0または1」という条件を満たす部分列(サブシーケンス)の中で、最も長いものの長さを求めるのがこの問題の目的です。素朴にすべての部分列を調べると膨大な時間がかかってしまいますが、unordered_map(ハッシュマップ)を活用すれば、配列を一度走査するだけで O(n) の線形時間で答えを導き出せます。入出力の例例1入力 − int arr[] = { 2, 1, 7, 6, 5 }出力 − 隣接要素の差が0または1となる最長部分列の長さ: 3説明 − 条件を満たす部分列には {7, 6, 5}(差はいずれも1)や {2,

この記事では、与えられた強度Pで倒すことのできる最大人数を求めるアルゴリズムを解説します。 一列に無限の人数が並んでおり、先頭から順に1から始まる番号が割り当てられています。s番目の人の強度は s2 で表され、ある人を倒すと、その人の強度sだけ自分の持つ強度も減少します。つまり、消費した強度の累積合計がP以下である限り、順番に人を倒し続けることができます。 それでは、具体例を使って問題の内容を確認していきましょう。 入力 P = 20 出力 3 説明 1番目の人の強度 = 1 * 1 = 1 < 20、よって1番目の人を倒せる 残りの強度 = P - 1 = 20 - 1 = 19 2番

問題の概要この課題では、与えられた文字列の中から特定の部分列（サブシーケンス）を何回取り除けるか、その最大回数を求めます。具体的には、文字列 s が与えられたとき、その中から部分列 「abc」 を最大で何個削除できるかを計算します。まず、具体例を使って問題を理解しましょう。入力例 1s = dnabcxy出力例 11解説： 文字列「dnabcxy」には「abc」という部分列が1つしか含まれていないため、出力は 1 となります。入力例 2s = zcabcxabc出力例 22解説： 「zcabcxabc」には「abc」が2箇所に含まれているため、2回削除できます。アルゴリズムの考え方この問題は貪

この記事では、「与えられた複数の点を含むことができる線分の数」の最大値を求める問題について解説します。問題概要サイズ n1 の配列 a1[] と、2つの整数 A・B が与えられます。配列 a1[] の各要素からは、始点を a1[i] − A、終点を a1[i] + B とする n1 個の線分を作成できます。さらに、n2 個の点からなる別の配列 a2[] が与えられます。これらの点を各線分に割り当てるとき、点が割り当てられた線分の数を最大化することが目標です。なお、1つの点を同じ線分に複数回割り当てることはできません。具体例で理解しよう入力例 1a1[] = {1, 4, 5}, a2[] =

この記事では、底辺の長さが「s」である直角二等辺三角形の中に、一辺「a」の正方形を最大でいくつ収めることができるかを求める問題を解説します。二等辺三角形とは、少なくとも2つの等しい辺を持つ三角形のことです。 まず、具体例を使って何をすべきかを理解しましょう。 入力例 s=5, a=1 出力 10 説明 − 底辺に並べられる正方形の数は、「s を a で割って 1 を引く」ことで求められます。つまり、底辺の正方形の数 = 5/1 − 1 = 4 個です。 同様に、最下段に4つの正方形を配置すると、その上に底辺が (s−a) の新しい二等辺三角形ができます。同じ手順を繰り返すと3個、さらにその上

本記事では、同じ文字のみで構成される長さKの部分文字列の出現回数の最大値を求める問題について解説します。文字列 s と整数 K が与えられたとき、すべての文字が同一であるサイズ K の部分文字列が何回現れるかを数えます。見つかった部分文字列の中から、最も多く出現するものの出現回数を答えとして返します。具体例を使って、何をすべきかを確認していきましょう。入力例 1s = tuuxyyuuc, K = 2出力例 12説明長さ2で同じ文字から構成される部分文字列には uu と yy があります。しかし、yy は1回しか出現しないのに対し、uu は2回出現しています。そのため、出力は 2 となります。

問題概要 与えられた正方バイナリ配列（2次元配列）において、左上の要素であるインデックス [0][0] から右下の要素であるインデックス [n−1][n−1] まで移動する経路の中で、得られる最大の整数値を求めるのが課題です。 経路の移動中に進むことができるのは、右方向（[i][j+1]）または下方向（[i+1][j]）のみです。 そして整数値は、通過した経路上のビットを用いて計算されます。 それでは、具体例を使って何をすべきか確認していきましょう。 入力 m = { {1, 1, 1, 1}, {0, 0, 1, 0}, {1, 0, 1, 1}, {0,

問題の概要与えられたバイナリ文字列（0と1のみで構成される文字列）から部分文字列を取り出し、その中に含まれる「0」の個数と「1」の個数の差が最大になる値を求めるのがこの問題の目的です。具体的にどのような処理を行うのか、例を使って確認してみましょう。入力例1str = 10010110出力例12解説位置1から4までの部分文字列「0010」に着目すると、「0」が3個、「1」が1個含まれています。したがって個数の差は 3 − 1 = 2 となり、これがこの文字列全体から得られる最大値です。入力例2str = 00000出力例25すべて「0」で構成されているため、文字列全体を部分文字列として選べば差は

この記事では、与えられたバイナリ文字列（「0」と「1」のみで構成される文字列）から部分文字列を取り出し、その中に含まれる「0」の個数と「1」の個数の差の最大値を求める方法を解説します。 問題の確認 具体例を使って、何をすべきかを見ていきましょう。 入力 str = 100100110 出力 3 説明 位置1〜5に対応する部分文字列「00100」には「0」が4個、「1」が1個含まれているため、差は 4 − 1 = 3 となります。これが求められる最大値です。 入力 str = 00000 出力 5 説明 文字列がすべて「0」で構成されている場合は、文字列全体を選ぶことで差は5になります。 アル

この記事では、与えられた文字列の中で、2つの大文字アルファベットに挟まれた区間に存在する「異なる小文字アルファベット」の最大数を求める問題を解説します。 まず、具体的な例を使って、何をする必要があるのかを理解しましょう。 入力 str = “JKyubDoorG” 出力 3 説明 大文字の K と D の間には「yub」が存在し、すべて異なる小文字であるため、カウントは 3 になります。 また、大文字の D と G の間には「oor」が存在しますが、‘o’ が重複しているため、異なる文字として数えると 2 になります。今回は重複しない文字のみを

この問題では、与えられた配列に対して、各要素を合計で最大k回まで増加（+1）できるという条件下で、等しい値にできる要素の最大個数を求めます。 まず、具体例を使って何をすべきか確認してみましょう。 入力例1 a[] = {1, 3, 8}, k = 4 出力例1 2 説明 この例では、要素「1」を3回、「3」を4回（計7回…と見せかけて、実際は各要素への加算回数の合計がk以内に収まるように調整）インクリメントすることで、2つの「4」を作り出せます。結果として配列は a[] = {4, 4, 8} となり、答えは 2 です。 入力例2 arr = {2, 5, 9}, k = 2 出力例2 0 こ

本記事では、2値配列 arr[] と、それぞれ初期値を持つ2つの変数 a、b が与えられたときに、配列の要素を最大でいくつ通過できるかを求める問題を解説します。 問題のルール 配列 arr[] の要素を通過するには、次の2つの方法があります。 arr[i] == 1 の場合： a から1単位を消費できます（b は変化しません）。あるいは b から1単位を消費すると、その代わりに a が1単位増加します。ただし、a の値は元の値を超えて増加できない点に注意してください。 arr[i] == 0 の場合： a または b のどちらかから1単位を消費できます。 それでは、具体例を使って問題を理解

本記事では、まずビットマスキングと動的計画法（DP）の基本概念について学び、その後、実際の実装に関する疑問を解消できる具体例題を一緒に解いていきます。ビットマスクとはビットマスク（マスクとも呼ばれます）とは、要素の集合の部分集合を符号化するためのNビットの列です。マスクの各ビットは「セット（1）」または「未セット（0）」のいずれかの状態を取り、対応する要素が部分集合に含まれているかどうかを表します。例えば、マスクのi番目のビットがセットされていれば、要素iはその部分集合に含まれていることを意味します。N個の要素を持つ集合に対しては、最大で2N通りのマスクが存在し、それぞれが一意の部分集合に対応

バイトニックソート（Bitonic Sort）は、ハードウェアや並列プロセッサアレイでの最適な実装を目的として設計された並列ソートアルゴリズムです。マージソートなどと比較すると単体の効率は最高ではありませんが、比較順序があらかじめ定義されており、ソート対象のデータに依存せずに比較が行えるため、並列実行に非常に適しています。また、バイトニックソートを効果的に機能させるには、要素数が2^n（2の累乗）である必要があるという特徴があります。バイトニック列とはバイトニックソートの中核をなすのが「バイトニック列（Bitonic Sequence）」です。これは、要素の値が最初は増加し、その後減少するよう

本記事では、まずビットとビット演算子の基本をおさらいした上で、実際の開発や競技プログラミングで役立つ重要なビット操作のテクニックを、具体的なコード例とともにわかりやすく解説します。 ビットとビット演算子の基礎知識 ビット（bit）とは「binary digit（2進数の一桁）」の略称で、コンピュータが理解できるデータの最小単位です。ビットが取りうる値は 0（OFFを表す）と 1（ONを表す） の2通りだけです。 ビット演算子とは、プログラム内でビットレベルに直接働きかける演算子の総称です。これらの演算子を使うことで、データを構成する個々のビットを自在に操作できます。 C/C++には、主に次の6

問題の概要 この問題では、2つの整数値 a と b が与えられ、a から b までの範囲に含まれるすべての数値のビット単位AND（&）を求めることが課題となります。つまり、a & (a+1) & (a+2) & … & (b−1) & b の値を計算する必要があります。 具体的な例で問題を確認してみましょう。 入力：a = 3、b = 8 出力：0 説明：3 & 4 & 5 & 6 & 7 & 8 = 0 シンプルな解法 最も単純なアプローチは、a から開始し、1ずつ値を増加させながら b までのすべて