動的計画法：完全背包問題の主要パターンと実装ガイド
完全背包問題の基本概念
動的計画法（DP）における完全背包問題（Complete Knapsack Problem）は、各アイテムを無限に選択可能な状態での最適化問題を指します。0-1 背包問題との主な違いは、アイテムの再利用が許可されている点であり、これにより状態遷移の内側ループ順序が重要になります。具体的には、背包の容量を小さい方から大きい方へ順に更新することで、同一ア ...
7月23日 17:01 投稿
三区分割クイックソートと挿入ソートのハイブリッド実装
クイックソートは平均計算量が O(n log n) である一方、ピボット選択が悪い場合に最悪 O(n²) に退化する。本稿では、Java で実装可能な高速化テクニックを段階的に紹介する。
1. 単純な二方向分割
ピボットを末尾に固定したまま、slow / fast という２つの走査ポインタを使って「ピボット未満」を左に集める手法。
static void basicQuick(int[] a, int lo, int hi) {
...
7月5日 18:24 投稿
動的計画法による配列最適化問題の解法パターン
階段登拝における最小コストの算出
配列の各要素が階段のコストを表しており、索引 i の階段を登る際に cost[i] の体力を消費します。支払い済みの場合、1 つまたは 2 つの階段を 건너갈 수 있습니다. 最上部に到達するための最小総コストを求めます。初期位置として索引 0 または 1 を選択可能です。
状態遷移としては、i 番目の階段に到達する最小コストは、i-1 番目から ...
6月12日 16:13 投稿
数論的計算と平方分割を用いた競技プログラミング問題の解説
問題 1：数論的和の計算
この問題では、大きな指数を持つべき乗の和を特定の素数で割った余りを求める必要がある。 naive な快速幂を用いた計算では $O(\sqrt{m} \cdot \log n)$ となり、制限時間を超えてしまう。ここで、法となる数が小さくかつ素数であることに注目する。
フェルマの小定理より、指数部分は法 $p$ に対して $p-1$ で割った余りとして扱ってよい。これに ...
6月1日 04:20 投稿