C++

本記事では、整数の範囲(変数 start から end まで)と整数 k が与えられたとき、「ゼロ以外の数字(非ゼロの桁)が k 個以下しか含まれない数値」がその範囲内にいくつあるかを求める方法を解説します。この問題は「桁DP」と呼ばれる手法とメモ化再帰を組み合わせることで、大きな範囲でも効率的に解くことができます。 具体例 入力 - int start = 50, end = 100, K = 2; 出力 - 範囲内で非ゼロの桁がK個以下である数値の個数:50 説明 - 範囲は50から100、k は2です。50〜99の2桁の数値は、どれも非ゼロの桁が最大でも2個であるため条件を満たします。

整数の範囲[start, end]、除数として使う変数m、そして判定対象となる数字dが与えられたとき、その範囲内で「mで割り切れる」かつ「偶数桁の位置に数字dを持つ」数がいくつあるかを計算するのが本記事の課題です。 例 入力 − int start = 20, end = 50, d = 8, m = 4 出力 − 範囲内でmで割り切れ、偶数桁に数字dを持つ数の個数: 2 説明 − 範囲は20から50です。数字8を含む候補は28、38、48で、いずれも2桁目(偶数桁)に8があります。このうち4で割り切れるのは28と48であるため、個数は2となります。 入力 − int start = 10,

整数の範囲(開始値 start から終了値 end まで)と、変数 k および d が与えられます。この課題では、指定された範囲内の数値のうち、数字 d がちょうど k 回出現するものの個数を求めます。具体例入力: start = 10, end = 100, d = 4, K = 2出力: 数字dがちょうどK回出現する範囲内の数値の個数: 1説明: 範囲は10から100までです。この範囲で数字4がちょうど2回出現する数値は「44」のみであるため、個数は1となります。入力: start = 10, end = 100, d = 6, K = 1出力: 数字dがちょうどK回出現する範囲内の数値の

0と1の組み合わせで構成される2つのバイナリ文字列 str_1 と str_2 が与えられたとします。まず、文字列 str_1 から生成できる異なる巡回置換(循環シフト)の集合「SET」を作成し、次に集合内の各要素とバイナリ文字列 str_2 とのXOR演算を実行して、その結果が0になるかどうかを確認します。XORが0になった場合はそのケースをカウントし、そうでない場合は無視します。 具体例で理解しましょう 例1 入力 − string str_1 = 1111、string str_2 = 1111 出力 − 他のバイナリ文字列とのXORが0となる巡回置換の個数: 4

整数 N が与えられます。ここでの課題は、1 から N までの各整数で N を順に割っていき、割る数（除数）のセットビット数が、そのときの商のセットビット数以上になるケースが何回あるかを数えることです。 例で理解する 例 1 入力: int N = 6 出力: N を除算したとき、商以上のセットビットを持つ除数の個数: 5 説明: まず N を 1〜N の各数で割り、除数と商それぞれのセットビット数を比較します。 1 → 6 ÷ 1(1) = 6(2) … 1 ＜ 2 → 対象外 2 → 6 ÷ 2(1) = 3(2) … 2 ＝ 2 → 対象 3 → 6 ÷ 3(2) = 2(1) …

3つの変数 size(要素数)、max_val(最大値)、last_element(末尾の要素) が入力として与えられます。この記事の目的は、次の条件をすべて満たす配列が何通り作れるかを求めることです。 配列はちょうど size 個の要素を持つ 各要素の値は 1 以上 max_val 以下の整数である 先頭の要素は必ず 1、末尾の要素は必ず last_element である 隣り合う2つの要素は同じ値にならない 例で理解しよう 例1 入力: size = 5, max_val = 3, last_element = 3 出力: 隣接する要素が異なる値を持つ配列の数:5 説明: 条件を満た

問題概要 無限の階層を持ちうる木構造が与えられます。変数 child は1つのノードが持てる子の数(= 各辺の重みとして選べる値の上限)、変数 weight は必ず1回以上含めたい辺の重み M、変数 path はパス全体の重みの合計 X を表します。この記事では、重みの合計がちょうど X に等しく、かつ重み M を持つ辺を少なくとも1つ含むパスの個数を求める方法を解説します。 入力例1 入力 − int child = 4, weight = 4, path = 4; 出力 − 重みがちょうどXで、重みMの辺を少なくとも1つ含むパスの個数:1 説明 − ノードには4つの子があり、重み4の辺で構

以下の問題は、日刊紙のクロスワードパズルを模した例題です。ここでは2次元文字配列(マトリックス)が与えられ、その中から指定された単語を見つけ出すことが課題となります。探索アルゴリズムは、上から下(Top-to-Bottom)、右から左(Right-to-Left)、およびそれぞれの逆方向に個々の文字を辿っていきますが、斜め方向は探索対象外である点に注意してください。 例で理解しよう 入力- 検索文字列 word:LAYS 2次元文字配列 - { LOAPYS, KAYSOT, LAYSST, MLVAYS, LAYSAA, LAOYLS }; 出力- 2次元文字配列内の指定文字列の出現回数:7

整数要素を含む配列 arr[] が与えられたとき、その中に存在する等差数列（Arithmetic Progression、AP）の部分列がいくつあるかを数えるのが本記事の目的です。配列内の要素の範囲は [1, 1000000] とします。 なお、空の部分列や要素が1つだけの部分列も等差数列としてカウントします。 例で理解する 例1 入力: arr[] = {1, 2, 3} 出力: 配列内のAP（等差数列）部分列の個数: 8 説明: 次の部分列が等差数列となります。 {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} 例2 入力: arr[] = {

はじめに このチュートリアルでは、以下の問題を解いていきます。 a と b の文字のみで構成された文字列が与えられます。ここでのタスクは、文字列から部分文字列 ab を取り除き、最後に残った文字列を出力することです。 この問題を解くアイデアは非常にシンプルです。a と b だけで構成される文字列は、操作を繰り返すうちに必ず a だけの文字列か b だけの文字列へと縮んでいきます。なぜなら、部分文字列 ab を1つ削除するたびに、a と b が1個ずつ減っていくからです。 アルゴリズムの手順 文字列を初期化します。 a 用と b 用の2つのカウンタ変数を初期化します。 与えられた文字列を先頭か

このチュートリアルでは、非常に大きな数 a が与えられたときに、(ab) % m を効率的に計算する方法を解説します。桁数が数十桁を超えるような巨大な整数は、標準の整数型では扱えないため、文字列として受け取りながら処理するのがポイントです。基本となる考え方剰余演算の性質から、次の等式が成り立ちます。(ab) % m = (a % m) × (a % m) × … × (a % m)（b回）つまり、まず a % m の値を求めてしまえば、あとはそれを b 回掛け、毎回 m で剰余を取るだけで答えが得られます。これにより、巨大な数 a を直接扱う必要がなくなります。解法の手順数値 a（文字列）、b

このチュートリアルでは、次の問題の解き方を詳しく解説します。問題の概要整数の配列が与えられたとき、そこから2つの数 A と B を見つける必要があります。配列に含まれる残りの数は、すべて A または B の約数です。また、ある数が A と B の両方の約数である場合、その数は配列の中に2回出現します。解法のアプローチこの問題は、以下の手順で効率的に解くことができます。配列内の最大値は、A と B のどちらか一方に必ず該当します。ここでは、それを A とします。次に、B は「2番目に大きい数」、または「A の約数ではない数」のいずれかになります。考え方のポイント配列を降順に走査しながら、A を割

このチュートリアルでは、2^(2^A) % Bという式の値を求めるプログラムをC++で作成していきます。一見すると巨大な指数計算が必要に思えますが、再帰関数を使うことで、実際に巨大な数を計算することなく効率的に答えを求められます。ここでは、その考え方と実装手順を順番に解説します。解き方の手順この問題は、次のような性質を利用して再帰的に解くことができます。A と B の2つの引数を受け取る再帰関数を作成します。A が 1 の場合、2^(2^1) % B = 4 % B となるため、4 % B を返します（ベースケース）。それ以外の場合は、引数を A - 1 として関数を再帰的に呼び出します。得ら

このチュートリアルでは、次の問題を解説します。 整数 n が与えられたとき、(1n+2n+3n+4n) % 5 の値を求める必要があります。 問題点：直接計算できない理由 n が大きくなると、(1n+2n+3n+4n) の値は爆発的に増大し、long long 型のような整数型にすら収まらなくなります。そのため、実際にべき乗を計算せずに済む別のアプローチが必要になります。 規則性の発見 まず、この式を n = 1, 2, 3, ..., 9 について実際に計算してみると、それぞれ次のような値が得られます。 10, 30, 100, 354, 1300, 4890, 18700, 72354,

このチュートリアルでは、次の問題を解決していきます。与えられた配列の中から、その値がインデックス（添字）と一致する要素を探すという問題です。非常にシンプルな内容ですが、配列操作の基礎を学ぶのに最適な題材です。解き方はシンプルで、配列を先頭から順番に走査し、配列の要素がそのインデックスと一致する箇所を見つけたら、そのインデックスを返すだけです。サンプルコードそれでは、実際のコードを見てみましょう。#include <bits/stdc++.h> using namespace std; int linearSearch(int arr[], int n) { for(int

このチュートリアルでは、与えられた配列の中から、配列内の他の要素によって最も多く割り切れる数(割り切れる回数が最大となる値)を見つける方法を解説します。 アルゴリズムの手順 配列と、結果を格納する変数を初期化します。 外側のループで配列を走査します。 カウンター変数を初期化します。 内側のループでもう一度配列を走査します。 現在の要素が、比較対象の配列要素で割り切れる場合はカウンターをインクリメントします。 現在のカウントがこれまでの最大値より大きければ、結果を更新します。 結果を出力します。 サンプルコード それでは、実際のコードを見てみましょう。 #include <

このチュートリアルでは、「ある数値Xとその各桁の数字の合計を足した値が、与えられた数Nと等しくなる」という条件を満たす数Xを見つける方法を解説します。 解法のアイデア 考え方は非常にシンプルです。与えられた数Nの前後それぞれ100以内の範囲にある数をすべてチェックします。 制約として N ≤ 1,000,000,000(10億)であり、各桁の数字の合計は最大でも100程度にしかなりません。そのため、答えとなる数Xがこの範囲の外側に存在することはありません。 アルゴリズムの手順 対象となる数値Nを初期化します。 0から100まで繰り返すループを作成します。 n - i と n + i の値を

このチュートリアルでは、二分探索木（BST）の中から、合計が指定された数値と等しくなるペアを見つけるプログラムを作成します。 木のノードの値を2つの異なるリストに格納し、それらを比較することでペアを効率的に探します。それでは、問題を解くための手順を見ていきましょう。 二分木用の構造体 Node を作成します。 新しいノードを二分探索木に挿入する関数を書きます。 二分探索木では、根より小さい要素はすべて左側に、大きい要素はすべて右側に配置されることを覚えておきましょう。 木の左側と右側のノードを格納するための空のリストを2つ初期化します。 左または右のノードが NULL になるか、両方のリスト

このチュートリアルでは、C++を使って配列の「パーティションポイント（分割点）」を見つける方法を解説します。パーティションポイントとは、その要素より左側にあるすべての要素が小さく、右側にあるすべての要素が大きいという条件を満たす位置のことです。解決の手順問題を解くための流れは以下の通りです。配列を初期化します。配列を走査します。インデックス 0 から i までの各要素が、現在の値より小さいかどうかを確認します。インデックス i+1 から n-1 までの各要素が、現在の値より大きいかどうかを確認します。両方の条件が満たされた場合、その値を返します。見つかったパーティションポイントを出力します。サ

はじめにこのチュートリアルでは、2次元配列からピーク要素を見つけ出すプログラムをC++で作成していきます。「ピーク要素」とは、上下左右に隣接するすべての要素よりも大きい値を持つ要素のことです。配列内にはピーク要素が複数存在する場合がありますが、このプログラムでは見つかった最初のピーク要素を返します。それでは、問題を解決するための手順を順番に見ていきましょう。解決手順テスト用のダミーデータで2次元配列を初期化します。2次元配列全体を走査します。まず、配列の四隅（左上・右上・左下・右下）の要素をチェックします。四隅は隣接要素が2つしかないため、特別な処理が必要です。次に、最初の行と最後の行に属する