C++

問題概要部屋の床の長さと幅を表す 2 つの整数 n と m が与えられます。この床をサイズ 1×m のタイルで敷き詰める方法が何通りあるかを数えることが目的です。入力例 1n=3 m=2出力例 11 x m サイズのタイルを使用して n x m の床を敷き詰める方法の数は:3説明下図のように、1×2 のタイル 3 枚を並べる方法が 3 通り存在します。入力例 2n=3 m=3出力例 21 x m サイズのタイルを使用して n x m の床を敷き詰める方法の数は:2説明1×3 のタイル 3 枚をすべて縦方向に並べる方法と、すべて横方向に並べる方法があり、合計 2 通りとなります。考え方(アプロー

問題概要 英字からなる文字列 str が与えられます。この記事のゴールは、str のすべての部分文字列に登場する母音の総出現回数を求めることです。 たとえば、文字列が「abcde」の場合、部分文字列は「a」「b」「c」「d」「e」「ab」「bc」「cd」「de」「abc」「bcd」「cde」「abcd」「bcde」「abcde」の15個になります。これらの部分文字列に含まれる母音は a と e であり、その出現回数を合計すると 10 になります。 入力例 1 str = aloe 出力 Count the number of vowels occurring in all the subst

問題の概要正の整数からなる配列 arr[ ] が与えられます。この記事のゴールは、「部分配列に含まれる要素の平均が、部分配列に含まれない残りの要素の平均よりも大きい」という条件を満たす部分配列の個数を求めることです。例 1入力:arr[ ] = { 3, 2, 4 }出力:部分配列内の要素の平均が、部分配列に含まれない要素の平均より大きくなる部分配列の個数: 2説明:考えられる部分配列は次の通りです − [ 3 ], [ 2 ], [ 4 ], [ 3,2 ], [ 2,4 ], [ 3,2,4 ] [ 4 ] の平均は 4 であり、残りの [ 2,3 ] の平均よりも大きい。 [ 3,2,

長方形の各辺の情報と、範囲を表す2つの変数 first と last が与えられたとき、「長さ ÷ 幅」で計算される辺の比率が [first, last] の範囲内に収まる長方形の個数を求めるのが本記事の目的です。入力例1rec[] = { { 200, 210 }, { 100, 50 }, { 300, 190}, {180, 200}, {300, 200}}first = 1.0, last = 1.6出力例1辺の比率が範囲[a,b]内にある長方形の個数: 4説明比率が [1.0, 1.6] の範囲内にあるのは以下の4組です。{200,210}, {300,190}, {180,200

問題の概要 正の整数を含む配列 arr と、GCD（最大公約数）の値を格納した配列 GCD[] が与えられます。この問題の目標は、arr[] の要素から構成されるすべての部分集合のうち、そのGCDが GCD[] に指定された値と一致するものの個数を求めることです。 入力例と出力例 例1 入力: arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5} 出力: 指定されたGCD値と一致する部分集合の個数: 1 2 2 説明: GCDが2となる部分集合は [10, 6] です。 GCDが3となる部分集合は [3] と [6, 3] です。 GCDが5となる部分集合は [

正の数だけを格納した配列 arr[] が与えられます。この記事のゴールは、arr[] の要素から選んだ部分集合のうち、その部分集合の値の中央値が、同じ部分集合の中にも存在するようなものの個数を求めることです。 入力例 arr[] = { 1,2,3 } 出力例 Count of number of subsets whose median is also present in the same subset are: 4 解説 中央値が同じ集合内に存在する部分集合は、次の4つです。 [ 1 ] … 中央値は 1 [ 2 ] … 中央値は 2 [ 3 ] … 中央値は 3 [ 1,2,3 ] …

小文字の英字のみで構成される文字列 str と整数値 k が与えられたとき、文字列 str の部分文字列のうち「ちょうど k 種類の異なる文字」を含むものの個数を求めるのが本記事の目的です。 入力例と出力例 例1 入力: str= pqr k=2 出力: ちょうど2種類の異なる文字を含む部分文字列の個数: 2 説明: ちょうど2種類の異なる文字を含む部分文字列は「pq」と「qr」の2つです。 例2 入力: str= stristr k=4 出力: ちょうど4種類の異なる文字を含む部分文字列の個数: 10 説明: 該当する部分文字列は以下の10個です。 「stri」「tris」「rist」「is

整数 num を入力として与えます。この記事の目標は、積 11 × 22 × 33 × … × numnum の計算結果に含まれる「末尾のゼロ（連続する0）」の個数を求めることです。 具体例 入力 num=5 出力 (1^1)*(2^2)*(3^3)*(4^4)*.. の積における末尾のゼロの個数：5 解説 積に含まれる2と5の個数は次のように数えられます。 1^1 * 2^2 * 3^3 * 4^4 * 5^5 = 1^1 * 2^2 * 3^3 * (2^2)^4 * 5^5 したがって、2は合計10個、5は合計5個となります。このうち小さい方は5なので、末尾のゼロの個数は5になります。

本記事では、整数 num を入力として受け取り、C++の bitset を使ってその2進表現における末尾ゼロ（下位ビット側に連続する0）の個数を求める方法を解説します。bitset は、0と1のビット列を格納するためのコンテナで、いわば「ビットの配列」として扱うことができます。これを利用すると、各ビットに簡単にアクセスして判定を行えます。入力例と出力例例1入力:num = 10出力:Count of number of trailing zeros in Binary representation of a number using Bitset are: 1解説: 数値10を2進数で表すと「

正の整数からなる配列が与えられます。各要素は、そのインデックスから配列の末尾に到達するために一度に進める最大ステップ数（最大ジャンプ長）を表します。この記事では、各要素から出発したときに配列の末尾へ到達できるジャンプ経路の数を求める方法を解説します。たとえば arr[] = {1, 2, 3} の場合、「1」からは 1 ステップのジャンプが 1 通り、「2」からは 1 または 2 ステップのジャンプが可能ですが、末尾に届くのは 1 ステップのときだけです。「3」はすでに末尾にあるため、追加のジャンプは不要です。入力arr[] = {1,2,3}出力末尾に到達するジャンプ方法の数: 1 1 0説

2つの数 e(要素数) と p(分割数) が与えられたとき、「集合の e 個の要素を p 個の部分集合(パーティション)に分割する方法が全部で何通りあるか」を求めるのがこの問題の目的です。 例1 入力 e=4 p=2 出力 Count of number of ways to partition a set into k subsets are: 7 説明 要素が a・b・c・d の4つである場合、これらを2つのグループに分ける方法は次の7通りあります。 (a)−(b,c,d)、(b)−(a,c,d)、(c)−(a,b,d)、(d)−(a,b,c)、(a,b)−(c,d)、(a,c)−(b,

2つの整数 N と K が与えられます。目的は、以下の条件を両方とも満たす数の個数を求めることです。 その数が N 以下であること |その数 − 素数の個数| ≥ K であること（ここで「素数の個数」とは、その数以下に存在する素数の総数を指します） 具体例 入力 N = 5, K = 2 出力 N以下の数のうち、それまでの素数の個数との差がK以上となる数は: 2個 説明 条件を満たす数は次の2つです: 5（5−2≥2）と 4（4−2≥2） 入力 N = 10, K = 6 出力 N以下の数のうち、それまでの素数の個数との差がK以上となる数は: 1個 説明 条件を満たす数は次の1つです:

数値の配列とスタックが与えられます。配列のすべての要素はスタック内に格納されており、各配列要素を取り出すために必要なポップ操作の回数を求めるのが目的です。 スタックには要素が降順で格納されており、最下部の要素が最大値、最上部（トップ）の要素が最小値となります。 入力例 Stack [ 7,6,2,1 ] array : 2,1,6,7 出力 Count of number of pop operations on stack to get each element of the array are: 3 1 0 0 説明 配列を先頭のインデックスから順に走査します。2 を取得するにはスタック

問題概要2つの整数AとBが与えられ、「A % X = B」を満たすような整数Xの取り得る値の個数を求めるのが目標です。この条件式については、AとBの大小関係によって次のように場合分けができます。A == B の場合：Xは無限に多くの値を取り得るため、-1を返します。A < B の場合：解が1つも存在しないため、0を返します。A > B の場合：(A − B) の約数のうちBより大きいものの個数を結果として返します。考え方のポイント剰余演算の性質上、「余りは必ず割る数よりも小さくなる」ため、A % X = B が成り立つには X > B であることが必要です。また、A % X

問題概要整数Nが入力として与えられます。この記事の目的は、次の条件を満たすすべてのN桁の数の個数を求めることです。num + rev(num) = 10N − 1つまり、あるN桁の数と、その数字を逆順に並べ替えた数との和が、9がN個並んだ数（999…9）と等しくなるような数がいくつ存在するのかを数えます。入力例N=4出力num + Rev(num) = 10N − 1 を満たすN桁の数の個数 ― 90説明該当する数は以下の通りです ―1. 1188 + 8811 = 99992. 2277 + 7722 = 99993. 1278 + 8721 = 9999……合計90個入力例N=5出力num

問題の概要 2つの整数 one(配列の長さ)と another(要素の最大値)が与えられます。求めたいのは、次の条件をすべて満たす配列の個数です。 配列の各要素は、1以上「another」以下の範囲に収まる。 隣接するどの2要素についても、一方が他方を割り切る(arr[i] が arr[i+1] を割り切る、またはその逆)。 配列の長さはちょうど「one」である。 入力例 1 one = 3, another = 2 出力例 1 Count of arrays in which all adjacent elements are such that one of them divide

問題概要 整数 N が入力として与えられたとき、N 未満の整数のうち、各桁が 0 と 1 のみで構成された数(いわゆる2進数のように見える数)がいくつあるかを求めるのが、この問題の目標です。たとえば入力 N が 12 の場合、条件を満たすのは 1、10、11 の3つであるため、答えは 3 となります。 入出力例 例1 入力: N=100 出力: Nより小さい2進数字のみの数の個数 − 4 説明: 条件を満たす数は − 1, 10, 11, 100 例2 入力: N=120 出力: Nより小さい2進数字のみの数の個数: 7 説明: 条件を満たす数は: 1, 10, 11, 100, 101,

2次元配列 arr[][] には複数の区間（インターバル）が格納されており、それとは別に整数値 value が与えられます。この記事のゴールは、value が範囲内に含まれる区間の個数を求めることです。たとえば、区間が [ [1,5], [3,7] ] で value = 4 の場合、4 は両方の区間に含まれるため、答えは 2 になります。 入力例と出力例 例1 入力： arr[4][2] = { { 1, 20 }, { 12, 25 }, { 32, 40 }, { 15, 18 } }, value = 16 出力： 指定した値が含まれる区間の数：3 説明： 値 16 は 1〜20、

0から9までの各数字に含まれる「穴」の数を格納した配列 holes[10] が与えられます。ここでいう「穴」とは、数字の字形にできる閉じた空間のことです。たとえば「0」「6」「9」には1個、「8」には2個の穴があります。本記事の目的は、入力として与えられた整数に含まれる穴の総数を求めることです。各数字の穴の数は次のとおりで、holes[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 } として表されます。0、4、6、9 → 1個8 → 2個1、2、3、5、7 → 0個入力例1number = 239143出力例1整数に含まれる穴の数: 2説明239143 の各桁の穴の数を

正の整数を格納した配列 arr[] が与えられます。この問題の目標は、長さ1以上の「非増加(各要素が直前の要素以下)」となる部分配列の個数を求めることです。例えば、arr[] = {1,3,2} の場合、条件を満たす部分配列は {1}、{2}、{3}、{3,2} の4つになります。 入力例と出力例 例1 入力: arr[] = {5,4,5} 出力: 非増加部分配列の個数: 7 説明: 該当する部分配列は以下の通りです。 {5}, {4}, {5}, {5,4} 例2 入力: arr[] = {10,9,8,7} 出力: 非増加部分配列の個数: 10 説明: 該当する部分配列は以下の通りです。