C++

正の整数を含む配列 arr[] と整数値 match が与えられたとき、要素のXOR(排他的論理和)がちょうど match と一致する部分集合(サブセット)の個数を求めるのがこの問題の目的です。例入力1arr[] = {4, 2, 8, 10}、match = 12出力1特定のXOR値を持つ部分集合の個数: 2説明XORが12になる部分集合は次の2つです。[4, 8]、[4, 2, 10]実際に、4 XOR 8 = 12、4 XOR 2 XOR 10 = 12 となり、どちらも条件を満たしています。入力2arr[] = {3, 5, 2, 7}、match = 5出力2特定のXOR値を持つ部分

3つの整数 R、G、B が与えられ、使用できる文字は「R」「G」「B」の3種類のみとします。この問題の目的は、「R」が少なくともR個、「G」が少なくともG個、「B」が少なくともB個含まれる文字列として作成可能なパターンの総数を求めることです。なお、R＋G＋B の合計は文字列の長さ以下であるものとします。 入力例と出力例 例1 入力： R = 1, G = 1, B = 1, length = 3 出力： 6 説明： 可能な文字列は以下の6通りです。これは RGB の全順列に相当します。 RGB, RBG, BRG, BGR, GRB, GBR 例2 入力： R = 2, G = 0, B

問題概要支払うべき金額 pay_Rupees(ルピー)と、額面がそれぞれ Rupees_amount_1 および Rupees_amount_2 の2種類の紙幣が無限枚あるものとします。このとき、ちょうど distribution_total 枚の紙幣を使って pay_Rupees を支払うという条件のもとで、Rupees_amount_1 の紙幣が何枚必要になるかを求めます。条件を満たす支払い方が存在しない場合は -1 を返します。入力例1Rupees_amount_1 = 1, Rupees_amount_2 = 5, pay_Rupees = 11, distribution_total

問題概要整数のみを含む配列 arr[ ] と、奇数 sum が与えられます。このとき、次のような合計配列 arr_2[ ] を作成することが目的です。各要素 arr_2[i] は、「arr[ ] 内の直前 sum/2 個の要素 ＋ arr[i] 自身 ＋ 直後 sum/2 個の要素」の合計となります。なお、sum が 1 の場合は arr_2[i] = arr[i] となります。入力例と出力例例1入力：arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 }、sum = 3出力：指定範囲の要素の合計によるサム配列の構築結果： 5 12 13 14 16 17 17 9 3説明

グラフ理論において「森」とは、複数の木(連結成分)からなるグラフのことを指します。この記事では、森を構成する頂点情報が与えられたとき、その森に含まれる木の本数を求める方法を解説します。実装にはDFS(深さ優先探索)アルゴリズムを使用します。入力例edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} }出力例森の中の木の本数: 3解説この森には以下のように3つの木が存在します。頂点1・3・5・7で構成される木、頂点2・6・8・4で構成される木、そして孤立した頂点0がそれぞれ独立した木としてカウントされます。アルゴリズムの考え方このアプローチでは

本記事では、2つの文字列 numo と demo を入力として受け取り、両方の文字列に共通する「約数」の個数を求めるC++プログラムを紹介します。ここでいう文字列の約数とは、その部分文字列を任意の回数繰り返すことで元の文字列を完全に構成できるような部分文字列のことです。例えば、str = abcabcabc の場合、abc を3回繰り返すことで元の文字列になるため、abc は str の約数です。入力例と出力例例1入力:numo = abababab demo = abababababababab出力:与えられた文字列の共通約数の個数: 3説明:両方の文字列を生成できる共通の約数は、「ab」「

数値の配列 arr[] と整数 x が入力として与えられたとき、次の条件を満たす部分集合（サブセット）をすべて見つけたいと思います。その条件とは、「部分集合に含まれる各要素が x で割り切れ、かつそれらの合計も x で割り切れる」というものです。 例 入力 arr[] = {1,2,3,4,5,6} x=3 出力 条件を満たす部分集合の個数：3 説明 該当する部分集合は以下の通りです： [3], [6], [3,6] 入力 arr[] = {1,2,3,4,5,6} x=4 出力 条件を満たす部分集合の個数：1 説明 該当する部分集合は以下の通りです： [4] このプログラムで採用しているア

一辺の長さ size が与えられ、size × size のチェス盤（正方形のマス目）を考えます。このとき、盤面の中に作ることができる奇数の辺の長さを持つ正方形の総数を求めるのが本記事の目的です。入力例と出力例例1入力:size=3出力:Count of squares with odd side length in Chessboard are: 10説明:3×3 の盤面には、1×1 の小さな正方形が9個、2×2 の正方形が4個、そして盤全体の 3×3 の正方形が1個存在します。このうち辺の長さが奇数となるのは、1×1 の9個と 3×3 の1個、合計 10個 です。例2入力:size=4出力

配列 arr[] と整数 k が与えられたとき、要素の積が k で割り切れる部分配列の個数を求める問題について解説します。ここでは、単純な全探索（ナイーブなアプローチ）と、セグメント木を用いて区間積を高速に取得するアプローチの2つを紹介します。 問題の例 例 1 入力: arr[] = {2, 1, 5, 8}, k = 4 出力: 4 説明: 条件を満たす部分配列は [8], [5,8], [1,5,8], [2,1,5,8] の4つ。 例 2 入力: arr[] = {7, 1, 9, 7}, k = 9 出力: 6 説明: [9], [9,7], [1,9], [1,9,7], [7,

この記事では、二分木（バイナリツリー）と値 x を入力として受け取り、ノードの重みの合計が x と一致するすべての部分木を見つける方法を解説します。例1入力x = 14 の場合。入力された値から構築される木は以下の通りです。出力Count of subtrees that sum up to a given value x are: 1説明与えられた値は x = 14 です。値が 14 である葉ノードは1つだけなので、カウントは 1 となります。例2入力x = 33 の場合。入力された値から構築される木は以下の通りです。出力Count of subtrees that sum up to a

各ノードに重みが割り当てられた二分木が与えられます。この問題の目標は、重みの各桁の合計（桁和）が奇数になるノードの個数を求めることです。たとえば、重みが「12」であれば桁和は 1+2=3 となり奇数なので、このノードはカウントの対象になります。例入力入力された値から作成される木は次のとおりです。出力与えられた木のうち、重みの桁和が奇数であるノードの数：2説明木の各ノードと、それぞれに対応する重みが与えられています。 すべての重みについて桁和を計算し、それが奇数かどうかを判定します。ノード重み桁和奇数？2232+3=5はい11411+4+1=6いいえ42112+1+1=4いいえ31331+3+3

各ノードに「重み」が割り当てられた二分木が与えられます。この記事の目的は、重みが2の累乗（べき乗）になっているノードの個数を求めることです。たとえば重みが32であれば 32 = 25 なので、このノードはカウントの対象となります。 入力例1 入力した値から生成される木は次のようになります。 出力 与えられた木のうち、重みが2の累乗であるノードの数: 3 説明 木の各ノードと、それぞれに対応する重みが与えられています。そこで、すべての重みについて「2の累乗として表せるかどうか」を順に判定していきます。 ノード重み2の累乗での表現判定 282 × 2 × 2 = 23はい 1100表現不可

各ノードに重みが割り当てられた二分木が与えられたとき、「重みが完全平方数であるノード」の個数を求めるのが本記事の目的です。例えば、あるノードの重みが36であれば、36 = 6² と表せるため、このノードはカウント対象となります。例入力値を入力して作成される木は以下の通りです。出力Count the nodes whose weight is a perfect square are: 4説明各ノードとそれに対応する重みが与えられており、それぞれの重みが完全平方数かどうかを確認します。ノード重み完全平方数該当するか212111 × 11はい1819 × 9はい437素数（平方数ではない）いいえ3

各ノードの重みが文字列として与えられた二分木があるとします。この記事の目的は、重みの文字列に母音が含まれているノードの数を求めることです。たとえば、あるノードの重みが「aer」であれば、母音「a」と「e」が含まれているため、このノードはカウント対象になります。 入力例1 値を入力した後に作成される木は以下の通りです。 出力 Count the nodes of the tree whose weighted string contains a vowel are: 5 説明 木の各ノードと、それらに関連付けられた文字列の重みが与えられています。ここで、各ノードの文字列に母音が含まれているかど

言語「L」が与えられ、この言語に対するプッシュダウンオートマトン（PDA）を構築することが課題です。この言語は、記号0の出現回数が記号1と記号2の出現回数の合計に等しいことを表しています。また、1と2はそれぞれ最低1回出現しますが、文字列が空文字列（NULL）となる場合もあり、その場合もオートマトンに受理される必要があります。プッシュダウンオートマトンとは？プッシュダウンオートマトン（PDA）は、正規文法に対して決定性有限オートマトン（DFA）を設計するのと同じように、文脈自由文法を実装するための手法です。DFAは有限のデータしか扱えませんが、PDAは無限のデータを扱うことができます。プッシュ

言語「L = {0m1(n+m)2n | m, n ≥ 0}」が与えられ、この言語を認識するプッシュダウンオートマトン（PDA）を構築することが課題です。この言語では、「1の出現回数が0の出現回数と2の出現回数の合計に等しい」という条件が定められています。さらに、mとnは0以上であるため、0や2が出現しないケースも許容され、文字列が空（NULL）となる場合もオートマトンによって受理されなければなりません。 プッシュダウンオートマトンとは？ プッシュダウンオートマトン（Pushdown Automata：PDA）は、正規文法に対して決定性有限オートマトン（DFA）を設計するのと同じように、文脈自

言語「L」が与えられ、この言語を受理するプッシュダウンオートマトン(PDA)を構築することが課題です。この言語は、0の出現回数と3の出現回数が等しく、1の出現回数と2の出現回数も等しい文字列の集合を表します。さらに、mとnは0以上であるため、すべての記号の出現回数が0となる空文字列(NULL)も受理されなければなりません。 プッシュダウンオートマトンとは? プッシュダウンオートマトン(Pushdown Automata:PDA)は、正規文法に対して決定性有限オートマトン(DFA)を設計するのと同じように、文脈自由文法を実装するための手法です。DFAは有限のデータしか扱えませんが、PDAはよ

ここでは言語「L」が与えられ、この言語に対応するプッシュダウンオートマトン（PDA）を構築することが課題となります。この言語は、文字「a」の出現回数が文字「b」の出現回数のちょうど2倍であり、文字「c」の出現回数が文字「d」の出現回数のちょうど4倍であることを意味しています。また、m と n は 0 以上であるため、m = 0 かつ n = 0 の場合には文字列が NULL（空文字列）になりますが、この空文字列もオートマトンによって受理される必要があります。 プッシュダウンオートマトンとは？ プッシュダウンオートマトン（Pushdown Automata / PDA）は、正規文法に対して決定性

各ノードに数値の重みが割り当てられた二分木が与えられます。この記事の目的は、「ノードの重み + X」の計算結果がフィボナッチ数となるノードの個数を求めることです。フィボナッチ数列とは、0, 1, 1, 2, 3, 5, 8, 13… のように続く数列で、n番目の数は(n−1)番目と(n−2)番目の数の和になります。たとえば重みが13であればフィボナッチ数に該当するため、そのノードはカウント対象となります。入力例1temp = 1 の場合。値を入力すると、以下のような木が構成されます。出力Count the nodes whose sum with X is a Fibonacci number

配列 arr[] には、k分木（k-ary tree）の先行順走査（プレオーダートラバーサル）の結果が順番に格納されています。この記事の目標は、その配列をもとに同じk分木を構築し、後行順走査（ポストオーダートラバーサル）の結果を出力することです。 ここでいう完全k分木（full k-ary tree）とは、各ノードが「0個」または「k個」の子ノードを持つ、すなわち最大でもk個の子しか持たない木のことです。 例 入力 int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2 出力 2つの子を持つ完全k分木を先行順