C++

問題の概要 今回は、与えられた配列を互いに素な配列（コプライム配列）に変換するために必要な最小の挿入回数を求める、興味深い問題を取り上げます。互いに素な配列とは、隣り合う任意の2つの要素の最大公約数（GCD）が必ず1になる配列のことです。この記事では、必要な挿入回数に加えて、変換後の配列そのものも出力します。 例として、{5, 10, 20} という配列を考えてみましょう。この配列は隣接要素同士のGCDが5や10となるため、互いに素な配列ではありません。しかし、5と10の間、そして10と20の間にそれぞれ「1」を挿入すれば、{5, 1, 10, 1, 20} となり、すべての隣接ペアのGCD

この記事では、最大公約数（GCD）と最小公倍数（LCM）の値が与えられたとき、その両方の条件を満たす整数のペアが全部で何通り存在するかを求める方法を解説します。 例として、GCDが2、LCMが12の場合を考えてみましょう。この条件を満たすペアは (2, 12)、(4, 6)、(6, 4)、(12, 2) の4つです。プログラムの目的は、このペアの総数「4」を計算することです。 解決の鍵となる数学的性質 2つの整数 a と b の間には、次のような重要な関係が常に成り立ちます。 a × b = GCD(a, b) × LCM(a, b) また、a と b はいずれも必ず GCD で割り切れるた

問題概要ある整数 n が与えられたとき、n を「2つの立方数の和」として表せる 2 組の異なるペアを見つけるのが本記事のテーマです。具体的には、n = a3 + b3 = c3 + d3 を満たすようなペア (a, b) と (c, d) を求めます。この種の数は「タクシー数（Taxicab Number）」として知られており、最も有名な例は 1729 = 13 + 123 = 93 + 103（通称：ラマヌジャン数）です。解法の考え方重要なポイントは、a、b、c、d のすべてが n1/3 以下の範囲に収まるという点です。そこで、n1/3 以下の数から作られるすべての異なるペア (x, y)

問題の概要 本記事では、文字列と整数 k が与えられたときに、「長さがちょうど k である部分文字列のうち、構成する各文字のASCII値の合計が k で割り切れるもの」の個数を求めるアルゴリズムを解説します。 例として、文字列が BCGABC、k = 3 の場合を考えてみましょう。部分文字列 BCG のASCII値の合計は 204（B=66、C=67、G=71）であり、また ABC の合計は 198（A=65、B=66、C=67）です。これらはいずれも k = 3 で割り切れるため、答えは 2 となります。 アプローチ：スライディングウィンドウ法 この問題は、スライディングウィンドウ（slid

1の補数とは本記事では、整数の「1の補数」を求める方法について解説します。C++には補数演算子(~)が用意されており、これを使えば非常に高速に補数を計算できます。ただし、この演算子は32ビット(4バイト)全体に対して補数を求めてしまうため、ここでは「与えられた数値のビット数分だけの補数」を取得する方法を考えます。例として、22という数値を取り上げます。22の2進表現は「10110」であり、その1の補数は「01001」、つまり10進数の9になります。では、この値はどのようにして求めればよいのでしょうか。求め方の手順まず、対象の数値のビット数を求めます。この値をcとします(22の場合、c = 5)

Fleuryのアルゴリズムとは Fleury（フルーリー）のアルゴリズムは、与えられたグラフからオイラー路またはオイラー閉路を求めて表示するための古典的なアルゴリズムです。ある辺から出発し、通過した辺を削除しながら隣接する頂点へ移動していくことで、各ステップでグラフを単純化し、オイラー路・オイラー閉路を見つけやすくします。 オイラー路・オイラー閉路を求めるためのルール 経路や閉路を正しく求めるには、あらかじめ次のルールを確認しておく必要があります。 グラフはオイラーグラフ（連結グラフであり、奇数次の頂点が0個または2個）であること。 候補となる辺が2つあり、一方が橋（ブリッジ）、もう一方が

C++において、整数のオーバーフローに対して唯一安全な対策は、オーバーフローが発生する前にチェックを行うことです。ただし、いくつかのテクニック的な方法を使えば、オーバーフローの発生を検出することも可能です。 符号なし整数の加算におけるオーバーフロー検出 例えば、符号なし整数（unsigned int）同士の加算でオーバーフローが起きたかどうかを調べたい場合、「計算結果が加算前のどちらか一方の値より小さくなっていないか」を確認する方法があります。 コード例 unsigned int x, y; unsigned int value = x + y; bool overflow = value &

今回は少し面白い文字列処理の問題を取り上げます。与えられたバイナリ文字列（0と1のみで構成された文字列）について、「1」の並びの中に「0」が挟まっていないかどうかを判定します。「0」が含まれていなければその文字列は有効（valid）、含まれていれば無効（invalid）とみなします。問題の例次の3つの文字列を見てみましょう。A：10001111010B：00001111100C：01111101111この中で有効なのは B の「00001111100」だけです。B は先頭から最初の「1」まで、そして最後の「1」以降には「0」がありますが、連続する「1」のブロック内部には「0」が一切存在しないた

今回は、もう一つ興味深い問題を取り上げます。次の条件を満たすバイナリ文字列を受け取り、それが有効かどうかを判定するコードを作成します。連続する「1」のグループは、必ず長さ2であること連続する「1」のグループは、必ず1つ以上の「0」の後に出現することたとえば「0110」という文字列は条件を満たす有効な文字列ですが、「001110」（1が3個連続している）や「010」（1が1個だけ）は無効となります。アプローチ考え方はシンプルです。文字列中の「1」の出現位置を順番に検索し、それぞれが部分文字列「011」の一部として正しい形で現れているかを確認します。どれか一つでも条件を満たさない箇所があれば fa

グラフの連結性（接続性）を確認するには、何らかの探索アルゴリズムを使ってすべてのノードを巡回してみます。探索が完了した時点で、まだ訪問されていないノードが1つでも残っていれば、そのグラフは連結していないと判断できます。有向グラフの場合は、すべてのノードから順に探索を開始して連結性をチェックします。これは、あるエッジが外向きの辺しか持たず内向きの辺を持たない場合、そのノードには他のどの開始ノードからも到達できない可能性があるためです。本記事では、この探索アルゴリズムとして再帰的なDFS（深さ優先探索）を使用します。入力と出力入力 − グラフの隣接行列01000001000001110000010

C++17では、既存のif文の構文が拡張されました。これにより、if文自体の中に初期化処理を直接記述できるようになっています。この新しい構文は「初期化子付きif文（if statement with initializer）」と呼ばれます。この機能強化により、よく使われるコードパターンが簡潔になり、変数のスコープを狭く保つことが容易になりました。その結果、変数が意図せずスコープ外に漏れ出すことを防ぐことができます。 従来の書き方（C++17以前） 例として、ある数値が偶数か奇数かを判定するプログラムを考えてみましょう。C++17以前では、コードは次のように記述していました。 #include

この記事では、文字列が2種類の文字が交互に並んで構成されているかどうかを判定する方法を解説します。例えば「XYXYXY」のように文字が交互に現れる文字列は有効ですが、「ABCD」のように異なる文字が連続して現れる文字列は無効とみなされます。判定の考え方判定方法は非常にシンプルです。すべての i 番目の文字と i+2 番目の文字が一致しているかどうかを順番に確認します。1つでも一致しない箇所があれば false を返し、すべて一致していれば true を返します。さらに、隣接する2文字(0番目と1番目)が同じ場合も無効と判定することで、「XXYY」のような並びを正しく除外できます。サンプルコード

本記事では、ある数値が15で割り切れるかどうかを判定する方法を解説します。ここで扱う数値は非常に大きいため、通常の整数型では表現しきれず、文字列として扱います。 15の倍数判定の考え方 数値が15で割り切れるためには、「5で割り切れる」かつ「3で割り切れる」という2つの条件を満たす必要があります。これは、15 = 5 × 3 であり、5と3が互いに素であるためです。 5で割り切れる条件： 最後の桁（1の位）が「0」または「5」であること 3で割り切れる条件： 各桁の数字の合計が3で割り切れること C++での実装例 #include <bits/stdc++.h> using n

本記事では、C++を用いて、ある数が11で割り切れるかどうかを判定する方法を解説します。ここで扱うのは非常に大きな数であるため、int 型や long long 型といった標準的な整数型には収まりません。そこで、数値を文字列として受け取り、桁ごとに処理を行います。 11の倍数判定法とは ある整数が11で割り切れるかどうかは、次の有名な判定法で簡単に確認できます。 左から順に各桁を見て、奇数番目の桁の合計と偶数番目の桁の合計をそれぞれ求める。 両者の差が0、または11の倍数であれば、その数は11で割り切れる。 特に、奇数番目の桁の合計と偶数番目の桁の合計が一致していれば、差は必ず0になるた

本記事では、非常に大きな数値が2・3・5のすべてで割り切れるかどうかを判定する方法を解説します。対象となる数は桁数が非常に大きいため、通常の整数型では扱えません。そこで、数値を文字列（string）として受け取り、各桁を調べることで判定を行います。判定の考え方：最小公倍数を使うある数が2・3・5のすべてで割り切れるということは、その数がこれらの最小公倍数（LCM）で割り切れることと同じです。2、3、5の最小公倍数は 30つまり「30で割り切れるか」を判定すればよいさらに、30で割り切れる条件は次のように分解できます。10で割り切れる → 最後の桁（1の位）が「0」である3で割り切れる → 全桁

この記事では、非常に大きな数値が20で割り切れるかどうかを判定する方法を解説します。数値が int 型や long long 型の範囲を超えるほど大きい場合、通常の数値型では扱えないため、文字列として受け取る必要があります。判定の考え方ある数が20で割り切れるためには、「その数が10で割り切れ、かつ10で割った商が2で割り切れる」という条件を満たす必要があります。これをもっとシンプルに考えると、次の2つの条件に整理できます。条件1: 最後の桁(1の位)が「0」であれば、その数は10で割り切れる条件2: 下から2番目の桁(10の位)が偶数であれば、10で割った商も2で割り切れるつまり、末尾が「0

本記事では、ある数値が25で割り切れるかどうかを判定する方法を解説します。扱う数値が非常に大きい（桁数が多い）場合、通常の整数型では表現しきれないため、数値を文字列として受け取って処理します。25の倍数の判定ルール数値が25で割り切れるかどうかは、下2桁だけを見れば判定できます。具体的には、以下のいずれかの条件を満たしていれば、その数は25で割り切れます。下2桁が「00」である下2桁の数値自体が25で割り切れる（00、25、50、75）これは、100が25で割り切れるため、下2桁より上の部分は必ず25の倍数になるという性質によるものです。サンプルコード#include <bits/std

はじめに本記事では、ある数値が3で割り切れるかどうかを判定する方法を解説します。ここで扱うのは非常に大きな数値であるため、通常の整数型(int や long long)では表現できません。そこで、数値を文字列として受け取り、判定処理を行います。3の倍数判定の原理3の倍数判定には、よく知られた数学的性質を利用します。「各桁の数字の合計が3で割り切れるならば、その数も3で割り切れる」例えば、123 という数値の場合、1 + 2 + 3 = 6 となり、6 は3で割り切れるため、123 も3で割り切れることが分かります。この性質は桁数が何桁であっても成り立つため、文字列として表現された巨大な数値にも

この記事では、ある数値が5で割り切れるかどうかを判定する方法を解説します。ここで扱うのは非常に大きな数値であるため、通常の整数型（int や long long）では表現しきれません。そこで、数値を文字列として受け取って処理します。 5の倍数の判定ルール 5で割り切れるかどうかは、実はとても簡単に判定できます。数値の最後の桁（1の位）が「0」または「5」であれば、その数は必ず5で割り切れるというのが割り算の基本ルールです。 例えば、「154484585745184258458158245285265」のような桁数の多い数値でも、末尾が「5」になっているため、実際に割り算を行わなくても即座に5

本記事では、非常に大きな数値が75で割り切れるかどうかを判定する方法を解説します。扱う数値が大きすぎるため、通常の整数型では表現できない場合があり、そのような数値は文字列として受け取って処理を行います。 75で割り切れるための条件 75 = 3 × 25 であり、3と25は互いに素です。したがって、次の性質が成り立ちます。 ある数が75で割り切れる ⇔ その数が3と25の両方で割り切れる 3で割り切れる条件 各桁の数字の合計が3で割り切れる場合、その数は3で割り切れます。 25で割り切れる条件 下2桁の値が25で割り切れる（つまり「00」「25」「50」「75」のいずれかで終わる）場合、