異端開発室

多項式 $(ax + by)^k$ を展開したとき、項 $x^n y^m$ の係数を $10007$ で割った余りとして求めよ。ただし、$n + m = k$ が常に成り立つ。 解法の概要 二項定理より、$(ax + by)^k$ の展開における $x^n y^m$ 項の係数は以下の式で表される： $$ \binom{k}{n} \cdot a^n \cdot b^m $$ ここで $\binom{k}{n}$ は二項係数であり、$k \leq 1000$ であるため、動的計画法（パ ...

スマートポインタの概要 スマートポインタの重要性 スマートポインタは、現代のC++アプリケーション開発において不可欠なメモリ管理メカニズムです。従来の生ポインタでは、開発者が明示的にメモリ確保と解放を管理しなければならず、メモリリークやダングリングポインタ、ダブルフリーなどの問題が発生しやすかったのです。スマートポインタを活用することで、オブジェ ...

1. C言語の動的メモリ管理 void Test() { int* p1 = (int*)malloc(sizeof(int)); free(p1); // malloc/calloc/realloc の違い int* p2 = (int*)calloc(4, sizeof(int)); int* p3 = (int*)realloc(p2, sizeof(int) * 10); // p2 を free する必要はあるか？ free(p3); } realloc は元のメモリブロックを拡張（インプレース）するか、新しい ...

A - Happy New Year 2025 2つの整数 $A$ と $B$ が与えられます。$(A + B)^2$ を出力するだけの問題です。計算結果が整数型の範囲に収まるか注意が必要ですが、今回の制約では問題ありません。 #include <iostream> using namespace std; void solve() { long long val1, val2; if (cin >> val1 >> val2) { long long combined = val ...

二分探索木とは 二分探索木（Binary Search Tree: BST）は、以下の条件を満たす二分木構造です： 左部分木に含まれるノードの値は、常に親ノードの値より小さい 右部分木に含まれるノードの値は、常に親ノードの値より大きい 左右の部分木もまた二分探索木を満たす 基本操作 探索（Search） 探索操作は以下のように行われます： ルートノードから比較を開始します 探索 ...

C++の標準ライブラリで提供されるstd::vectorの動作を理解するために、独自の動的配列クラスを実装します。この記事では、イテレータ、メモリ管理、要素アクセス、変更操作などの実装手順をコード例とともに解説します。 メンバ変数 std::vectorと同様に、内部では3つのポインタ（イテレータ）で管理します。std::stringとは異なり、サイズやキャパシティはこれらのポイン ...

C++標準ライブラリはスレッド操作を包括的にサポートしており、特にstd::threadやstd::asyncが頻繁に利用されます。『Effective Modern C++』では、スレッドのネイティブなローカル処理が必要でない限り、タスクベースのプログラミングを推奨しており、std::asyncの使用が望ましいとされています。本記事では、std::asyncを中心にその仕組みと使用法を解説します。 std::as ...

スライディングウィンドウ問題において、各ウィンドウ内の最大値を効率的に求めるには、双方向キュー（deque）を活用した単調キューというデータ構造が有効である。このアプローチにより、O(n)の時間計算量で解を導出できる。 双方向キューの特性と選択理由 通常のキュー（queue）は、要素の追加が末尾から、取り出しが先頭からのみ可能である。一方、双方向キュー（deq ...

1. C++のテンプレート機構について C++におけるテンプレートは、データ型に依存しない汎用的なコード（ジェネリックプログラミング）を実現するための仕組みです。テンプレートを使用することで、異なるデータ型に対して同じロジックを適用するコードを一度記述するだけで済み、コンパイル時に特定の型に応じたコードが生成されます。これにより、コードの再利用性が大幅 ...

オブジェクト指向設計において、生成型デザインパターンはシステムの柔軟性を高める重要な手法です。特にファクトリーメソッドパターンと抽象ファクトリーパターンは、オブジェクト生成のカプセル化を通じて依存関係を解消し、拡張性を確保するための有効なアプローチです。 ファクトリーメソッドパターンの再考 このパターンでは、基底クラスがオブジェクト生成のインタ ...