異端開発室

木構造と動的計画法の親和性 木（Tree）は再帰的に定義されるデータ構造であり、部分問題に分割して解く動的計画法（DP）と非常に相性が良いです。本稿では、木構造におけるDPの典型的な問題と、その状態遷移および実装について解説します。 グラフ理論における4つの典型問題 一般のグラフにおいて、以下の4つの問題はNP困難またはco-NP完全として知られていますが、木構 ...

1. 1からnまでの総和 整数 n を読み込み、1+2+…+n を出力する。 int n, total = 0; cin >> n; for (int i = 1; i n; for (int v = 2; v > n; for (int i = 0; i < n; ++i) { cin >> x; avg += x; } printf("%.4f", avg / n); 7. 整数列の総和と平均（小数5桁） int n, val, total = 0; cin >> n; for (int i = 0; i < n; ++i) { cin >> val; total += val; } printf("%d ...

問題A: 双方向関係の検出 与えられた順列pにおいて、異なるインデックスi, jが互いを参照し合っているか（つまり p[i] = j 且つ p[j] = i）を判定する。そのようなペアが存在する場合、必要な選択肢の数は2であり、存在しない場合は必ず3必要となる。全探索ではなく配列への直接アクセスにより、線形時間でこの条件を満たすかどうかをチェックできる。 #include <iostre ...

C++は、C言語の「手続き型」のアプローチに対し、「オブジェクト指向」を基盤とした言語です。オブジェクト指向では、複雑な処理を独立したオブジェクト間の相互作用として捉えます。C++における構造体（struct）は、C言語との互換性を保ちつつ、メンバ関数を持つことができる「クラス」へと拡張されています。 クラスの定義とアクセス制御 C++では、classまたはstructキ ...

アプリケーションフレームワークのインターフェース設計 現代のゲームエンジンにおいて、アプリケーションフレームワークはエンジン全体の挙動を制御する背骨のような役割を果たします。これはエンジンのブートストラップ（起動）、メインループの実行、そして終了処理を定義し、開発者が各プラットフォームの差異を意識せずにロジックを記述できる抽象化レイヤーを提供し ...

std::list の基本的な操作方法 C++の標準テンプレートライブラリ（STL）に含まれる std::list は、双方向連結リストとして実装されています。要素の挿入や削除が高速である一方で、ランダムアクセスには適さないという特徴があります。 1. インスタンス化と要素の操作 #include <iostream> #include <list> #include <algorithm> int main() { // ...

概要 Valgrind は、バイナリ動的インタプリテーション技術に基づいた実行時分析用のツールフレームワークです。プロファイリングやデバッグ機能を備えており、特にメモリ管理の不整合を検出するmemcheckツールが中心的な役割を果たします。 インストーレーション ソースコードを取得し、ローカルのディレクトリへビルドします。 # アーカイブの取得 wget https://sourcewa ...

単一始点からグラフ内の全頂点への最短距離を算出する代表的な手法として、ダイクストラ法（Dijkstra's Algorithm）が広く利用されています。本アルゴリズムは、すべての辺の重みが非負である場合に限り、正確な最適解を保証します。 アルゴリズムの動作原理 処理の手順は以下の通りです。 始点の距離を 0 に設定し、他の全頂点の距離を無限大（∞）で初期化します。同時に ...

重要なご案内 このチュートリアルは単一の C++ プロジェクトを作成するものではなく、学習用/開発用の準備済み環境を提供します。C++ の日常学習を容易にするために、個別の .cpp ソースファイル（拡張子必須）またはフォルダ全体を実行・デバッグする簡易スクリプトが組み込まれています。 プロジェクト構成が必要な場合は、CMake を学習し、ルートディレクトリの CMakeLi ...

\[本文の構成\] 序論 テンプレートのインスタンス化 暗黙的なインスタンス化 明示的なインスタンス化 テンプレートの特殊化 明示的特殊化 部分特殊化 関数オーバーロードと特殊化 型推論 暗黙的な型変換 対応する型変換 参照とconst 万能参照、参照の折りたたみ、完全転送 万能参照と右辺値参照 型特性 typename 関連型 型特性 イテレータの特性 特性抽出 - SFINAE特性 ...