無限ナップサック構造型問題
正整数集合による数値構成問題において、合同最短経路アプローチが有効。任意の基準値Mを定義し、f(x)を「x + kM (k∈N)の形式で構成可能な最小k」として最短経路問題に変換。
構成可能数カウント応用
有名問題「スカイスクレイパー機」では、適切なモジュラ数を選択しf(x)を計算することで解が導出可能：
void dijkstra() {
...
while (!queue.empty()) {
int current = queue.top().second;
queue.pop();
int nextNode = (current + step) % modValue;
if (visited[nextNode]) continue;
if (dist[current] + step < dist[nextNode]) {
dist[nextNode] = dist[current] + step;
queue.push({dist[nextNode], nextNode});
}
}
}
非構成可能最大数探索
「牛場圍欄」問題では、gcdチェックと最小値モジュラ分解が重要。基準値選定後にf(x)から逆算して解を求める。
軌道走査法
合同最短経路の新しいアプローチとして、完全ナップサックの軌道分解が有効：
- モジュラ空間Z_m上でgcd(m,v)個の軌道を生成
- 各軌道で最小値探索→順次更新を2回実施
- O(nm)の計算量で実装容易
void optimizedLoop() {
fill(dp, dp+mod, INF);
dp[0] = 0;
for (int i=1; i高次元ナップサック最適化
超大容量クエリ対応型ナップサック問題では：
- 最大コスパアイテム(m,w)を基準に価値関数を補正
- mod m空間で最長経路探索（正閉路排除）
- 最大クエリサイズの1/10^11を満たす解を保証
等差数列最適化
「論戦竹分割」問題のようにborder集合が等差数列出現する場合：
- log|S|個の等差数列に分解
- モジュラ空間間の状態変換技術
- スライディングウィンドウによる軌道最適化
数位和最小化
nの倍数で最小数位和探索問題：
int digitSum(int n) {
vector<int> dist(n, INF);
dist[1%n] = 1; // 初期状態
queue<int> q;
q.push(1%n);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto next : {(cur*10)%n, (cur+1)%n}) {
if (dist[next] > dist[cur] + (next==cur+1?1:0)) {
dist[next] = dist[cur] + (next==cur+1?1:0);
q.push(next);
}
}
}
return dist[0];
}