C++

数値の行列が与えられたとき、その中に含まれる魔方陣（マジックスクエア）の個数を見つけるのが本記事の目的です。 魔方陣とは、行列として見た場合に、1から9までの数字がちょうど1回ずつ現れる3×3の行列のことです。数独のグリッドに似た構造を持っています。魔方陣の主な性質は以下のとおりです。 すべての数字がちょうど1回ずつ出現する。 行列内の9つのセルの合計は45になる。 各行（3つの数字）の合計は15になる。 各列（3つの数字）の合計は15になる。 対角線上の3つの数字の合計も15になる。 これらの合計を満たすためには、5が必ず両対角線の交点（中央）に位置する必要がある。 入力例1 int

チューリングマシン（Turing Machine）とは チューリングマシンは、0型文法（タイプ0文法）から生成される言語の語を受理するために用いられる装置です。チューリングマシン（TM）は、セルに区切られた無限長のテープからなる数学的モデルであり、このテープに入力が与えられます。TMは入力テープを読み取るヘッドを備え、状態レジスタがマシンの現在の状態を保持します。入力記号を読み込むと、その記号は別の記号に置き換えられ、内部状態が変化し、ヘッドは左右いずれかのセルへ移動します。TMが最終状態に到達すれば入力文字列は受理され、到達できなければ拒否されます。 TMは次の7つ組（Q, X, Σ, δ,

問題概要数値の配列 Arr1[] と、同じ長さまたは異なる長さの別の配列 Arr2[] が与えられます。Arr1[] の要素は昇順にソートされていますが、ただ一つの要素だけが誤った位置に配置されています。この課題では、Arr2[] から適切な要素を選び、Arr1[] の誤った位置にある要素を置き換えることで、配列全体をソート済みの状態にします。置き換えに使える候補が複数ある場合は、その中で最大の要素を選択しなければなりません。入力例 1Arr1[]= { 1,3,5,7,2,11 }, Arr2[]= { 4,8,7,10,9 }出力例 1Arr1 をソートできる最大の要素: 10解説: Ar

問題の概要 Nルピーが手元にある状態で、このお金で購入できる水の量を最大化することを目指します。水ボトルの価格設定は以下の通りです。 ペットボトル：1リットルあたりAルピー ガラス瓶：1リットルあたりBルピー（空き瓶を返却するとEルピーが返金される） ガラス瓶は返却によってEルピーが戻ってくるため、その実質コストは「B−E」ルピーになります。したがって、以下のように判断します。 ペットボトルの価格AがB−Eより安い場合 → ペットボトルのみを購入するのが得です。 それ以外の場合 → まずガラス瓶を優先的に購入し、残ったお金でペットボトルを補います。 入出力例 例1 N = 6, A =

( ) { } [ ] の6種類の括弧文字のみで構成された文字列が与えられたとき、隣接する文字の交換または文字の削除を行うことで得られる「バランスの取れた文字列」の最大の長さを求めるのが本記事のテーマです。隣接する2文字を比較し、互いに対応関係にあるペアであれば交換が可能です。例えば }{、)(、][ は順序を入れ替えられますが、{{ や ))、[[ のように同じ種類の文字が並んでいる場合は交換できません。さらに、どの文字ともペアを組めない孤立した文字は削除することが許されます。例えば {{}][ の場合、先頭の { を削除すれば、長さ4のバランス文字列が残ります。入力例と出力例例1入力: s

「コンテンツ管理システム（Content Management System：CMS）」という言葉を文字通りに捉えると、それは「コンテンツを管理するためのシステム」を意味します。具体的には、Webコンテンツの作成、デザイン、公開、保守を簡単かつ効率的に行うための、多彩な機能を備えた共同作業プラットフォームとして定義されます。 コンテンツ管理システム（CMS）とは何か？ コンテンツ管理システム（CMS）とは、オンライン上でWebコンテンツを作成・デザインするために使用されるソフトウェアアプリケーションです。データベース操作、スマートレポート機能、アーカイブ、デザインやアニメーション機能などへの

完全順列（Derangement）とは完全順列（撹乱順列、Derangement）とは、N 個の数字の順列のうち、「どの数字ひとつとしても元の位置に現れない」ような並び替えのことです。たとえば {1, 2, 3} の完全順列のひとつが {2, 3, 1} です。この並びでは、どの要素も元々の位置から動いています。ここでの目的は、N 個の数字に対して可能な完全順列の個数を求めることです。これを再帰的な解法で求めていきます。要素数ごとの値は次のとおりです。N = 0 … 並び替えの対象が存在しないため 1 を返すN = 1 … 数字が 1 つしかなく入れ替えられないため 0 を返すN = 2 …

連続ツリー（Continuous Tree）とは連続ツリーとは、ルートノードから葉ノードまでのすべての経路において、親ノードとそのすべての直接の子ノードとの値（重み）の絶対差が常に1となるような木のことです。ルートから葉への経路上の任意のノードを選んだとき、次の条件が必ず成り立ちます。|ノードの値 − 左の子ノードの値| = 1（右の子ノードについても同様に成り立つ）図解と具体例具体例を見ながら理解を深めましょう。下の木は、親ノードとその子ノードの値の絶対差が常に1であるため、連続ツリーとみなされます。一方、下の木は親子ノード間の絶対差が1になっていない箇所があるため、連続ツリーの条件を満たし

はじめに二分木の中間順トラバーサル(Inorder)と先行順トラバーサル(Preorder)の結果が与えられたとき、それらから元の二分木を復元して構築することができます。本記事では、その具体的な考え方と手順をわかりやすく解説します。中間順トラバーサル(Inorder traversal)とは中間順トラバーサルでは、「左部分木 → ノード自身 → 右部分木」の順でノードを訪問します。中間順トラバーサルの手順(root を起点とする場合)root が指すノードの左部分木をたどる(inorder(root→left) を再帰呼び出し)ノード自身(ルート)を訪問するroot が指すノードの右

問題の概要 二分木が与えられたとき、その木の中で形成できる最大長のサイクル（閉路）の長さを求めるのがこの記事のテーマです。基本的な考え方はシンプルで、根ノードから見た左部分木と右部分木それぞれの最大の高さを求め、その2つの最長パスを根ノードでつなぎ合わせることで、最も長いサイクルを構成します。 例えば次のような木の場合、最大長のサイクルは「1-2-3-4-7-6」または「1-6-7-4-3-2-1」となり、その長さは6になります。 入力例と出力例 例1 入力：次の二分木 出力：最大長のサイクルは 5 解説：左部分木の最大の高さは3、右部分木の最大の高さは1です。したがってサイクルの長さは

問題概要 容器の壁の高さが配列として与えられ、その中で最大量の水を溜められる容器を見つけるのがこの問題の目標です。壁の高さは配列の要素で表され、2つの壁の間の距離（インデックスの差）が容器の幅として扱われます。たとえば、高さ Arr[i] と Arr[j] の壁の間の幅は j−i です（0 ≤ i < j ≤ N、N は壁の総数＝配列の長さ）。 水位は低い方の壁の高さまでしか上がりません。Arr[i] < Arr[j] なら水位は Arr[i] となり、幅は j−i なので、溜められる水の面積は次の式で表せます。 面積 ＝ min(Arr[i], Arr[j]) × (j − i)

孤立頂点とは？ グラフ理論において孤立頂点（isolated vertex）とは、どの辺にも接続されていない頂点のことを指します。この記事では、辺の数と頂点の数が与えられたとき、そのグラフに存在しうる孤立頂点の最小数と最大数を求める方法を、C++のコードとともに分かりやすく解説します。 孤立頂点の最小数を求める 孤立頂点を最小化するには、すべての辺が互いに異なる頂点を使うように配置します（どの2つの辺も頂点を共有しない状態）。各辺が必要とする頂点は2つだけなので、次のように計算できます。 非孤立頂点の数 = 2 × 辺の数孤立頂点の数 = 全頂点数 − 非孤立頂点の数 もし頂点数 ≤ 2 ×

この記事では、おもちゃの価格リスト（配列）と手元にある金額Kが与えられたとき、その予算内で購入できるおもちゃの数を最大化する問題をC++で解く方法を解説します。配列の各要素は1つのおもちゃの価格を表しており、配列の要素数がおもちゃの総数に相当します。この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。まず価格の配列を昇順にソートし、できるだけ多くのおもちゃを買えるよう、安いおもちゃから順番に購入していくという戦略です。高価なおもちゃは後回しにすることで、限られた予算で最大数を確保できます。入力例toyprices[] = { 10, 20, 12, 15, 50, 30 }　K =

問題概要正の整数 N が与えられたとき、不等式 x*x + y*y < N を満たす非負整数ペア (x, y) の組み合わせが何通りあるかを求めます。ここで、x と y は 0 以上の整数です。基本的な考え方はシンプルです。x を 0 から x*x < N を満たす範囲、y を 0 から y*y < N を満たす範囲で順番に調べていき、条件 x*x + y*y < N が成立するたびにペアのカウントを 1 増やします。入力例n=4出力例distinct pairs= 4説明 ― 条件を満たすペアは (0,0)、(1,1)、(0,1)、(1,0) の 4 つです。これらは

0と1からなる2進数列が与えられます。ある人が current_pos に格納された位置（地点）にいると仮定します。この位置を起点として、2進数列の値が 0 であれば1ステップ左へ移動し（current_pos - 1）、1 であれば1ステップ右へ移動します（current_pos + 1）。目的は、2進数列をすべて処理し終えた後に、訪れた異なる位置（地点）の数を求めることです。この問題は、各地点が訪問された回数（頻度）を記録することで解けます。頻度がゼロでなければ、異なる地点のカウントを1つ増やします。入力例Path[]= 001100 current_pos=3出力例数直線上で訪れた異なる

はじめに入力として二分探索木（BST）が与えられます。この記事の目的は、ノードの値がすべて指定された範囲（start〜end）に収まっているBST内の部分木の個数を求めることです。たとえば、startが5、endが50である場合、「すべてのノードの値が5以上50以下」という条件を満たす部分木の数を数えます。入出力例入力 − 下図の木、範囲 [3-6]出力 − 範囲内にある木の数：2説明 − 該当するのはノード4と6のみです。これらの部分木（NULL）は3〜6の範囲内にあります。入力 − 下図の木、範囲 [12-20]出力 − 範囲内にある木の数：3説明 − 該当するのはノード16、14、20で

オープンソースとは何か？オープンソースとは、ソフトウェア業界では一般に「オープンソースソフトウェア（OSS）」と呼ばれるものを指します。OSSはインターネット上で自由に入手でき、誰でも利用・改変・テスト、そしてさらなる開発を行うことが許されています。ソースコードが公開されているため、世界中のさまざまなユーザーにとって扱いやすく、自分のニーズに合わせてパッチを追加したり削除したりすることも可能です。オープンソースへの貢献は、プログラマーや開発者、テスターにとって大きなチャンスをもたらし、ソフトウェアの世界を大きく変えてきました。なぜ貢献するのか？知識と教える力を磨くため特定の分野や言語（たとえば

コンピューティングの世界は絶えず進化を続けており、毎日のように新しいデバイスが登場しては、従来の機器を最新の技術変化に対応できないものへと変えています。部屋全体を占めるほど巨大で、計算に何時間もかけていたコンピュータの時代は、すでに遠い昔のものとなりました。 真空管からトランジスタ、集積回路、そしてタッチスクリーンデバイスへの進化の過程で、技術の発展はコンピューティングの手法そのものも大きく変えてきました。新しいデバイス向けのプログラミングスタイルも変化しており、従来どおりのプログラムの書き方はもはや通用しません。組み込まれるソフトウェアには、高い効率性、迅速な応答性、そしてインタラクティブな

問題概要 整数 N と K が与えられたとき、0 と 1 のみから構成される長さ N のバイナリ文字列のうち、隣接する 1(連続する「11」)がちょうど K 回現れるものの総数を求めるのが目標です。 たとえば N=3、K=2 の場合、「11」が 2 回現れる 3 桁のバイナリ文字列をすべて数えることになります。 111:隣接する 1 の組が 2 回現れます(= K 回) 011 / 110:隣接する 1 の組は 1 回しか現れません この問題は、すでに計算した小さいサイズの結果を保存しておくことで、効率よく解くことができます。 解き方の考え方(動的計画法) ここでは 3 次元配列 cou

HH:MM 形式で時刻を表示するデジタル時計を考えてみましょう。この時計は「時」と「分」のみを表示します。ここに、経過時間を「時間」と「分」として入力として与え、表示されるすべての桁が同じ数字になる瞬間（00:00 や 11:11 のような時刻）が何回現れるかを数えるのが本記事の目的です。 同じ数字が並ぶ時刻とは 24時間表記において、全桁が同じ数字になるのは 00:00（真夜中）、11:11、22:22 の3回です。本問題では入力される時間数が 24 を超えてもよいことになっているため、桁のパターンは 11 時間ごとに繰り返し現れるものとして数えます。 入出力例 例1 入力: 12時間 22