🧮 桁和減算操作の詳細解析
📋 問題の概要
操作定義: 整数から「その桁和」を引く
具体例: 108 → 99 → 81 → 72
108
桁和: 1+0+8=9
108-9=99
桁和: 9+9=18
99-18=81
桁和: 8+1=9
81-9=72
最終結果
⚠️ ナイーブ解法の問題点
時間計算量: O(N × K)
N=300,000, K=10⁹の場合: 3×10¹⁴ 回の演算 →
時間切れ!
// ナイーブ解法（遅すぎる） for (let i = 1; i <= N; i++) { let current=i; for
(let step=0; step < K; step++) { current=current - digitSum(current); }
result[i-1]=current; }
🚀 ダブリング手法の概念
アイデア: 2^0, 2^1, 2^2, ... ステップのジャンプ表を事前計算
ジャンプ表の構築例 (K=13の場合)
K = 13 = 1101₂ = 2³ + 2² + 2⁰ = 8 + 4 + 1
| ビット位置 |
ステップ数 |
使用するか |
説明 |
| 0 |
2⁰ = 1 |
使用 (1) |
1ステップジャンプ |
| 1 |
2¹ = 2 |
未使用 (0) |
2ステップジャンプ |
| 2 |
2² = 4 |
使用 (1) |
4ステップジャンプ |
| 3 |
2³ = 8 |
使用 (1) |
8ステップジャンプ |
⚙️ アルゴリズムの詳細ステップ
ステップ 1: 初期化
1ステップジャンプ表を初期化中...
📊 計算量解析
| 項目 |
ナイーブ解法 |
ダブリング解法 |
改善率 |
| 時間計算量 |
O(N × K) |
O(N × log K) |
K/log K 倍 |
| 空間計算量 |
O(N) |
O(N) |
同じ |
実行時間
(N=300K, K=10⁹) |
約3×10⁸ 秒 |
約1-2秒 |
1.5×10⁸ 倍高速 |
改善の鍵:
log₂(10⁹) ≈ 30 回の反復で完了!
(ナイーブ解法の10⁹回 → 30回)
💾 メモリ最適化技術
データ型による メモリ使用量比較
| データ型 |
要素サイズ |
N=300K時の使用量 |
適用可能範囲 |
| number[] (JavaScript) |
8バイト |
2.4MB × 3 = 7.2MB |
汎用 |
| Uint32Array |
4バイト |
1.2MB × 3 = 3.6MB |
0 ≤ 値 ≤ 2³²-1 |
| Uint16Array |
2バイト |
0.6MB × 3 = 1.8MB |
0 ≤ 値 ≤ 65535 |
// メモリ効率的な実装 let jumpTable: Uint32Array = new Uint32Array(n + 1);
// 4バイト×要素数 const currentPositions: Uint32Array = new Uint32Array(n +
1); // 従来の配列との比較 // let jumpTable: number[] = new Array(n + 1); //
8バイト×要素数 (50%多い)
💡 実装のポイント
重要な注意点
BigInt使用
K ≤ 10⁹ のため
ビット演算で必要
負の値対策
Math.max(0, i - digitSum)
で0以下を防ぐ
ガベージ削減
配列の参照を
明示的に更新
高速I/O
fs.readFileSync(0)
Buffer操作
// 正しいダブリング実装パターン while (remainingSteps > 0n) { // 1.
ビットチェック if ((remainingSteps & 1n) === 1n) { // 現在のジャンプ表を適用 for
(let i = 1; i <= n; i++) { currentPositions[i]=jumpTable[currentPositions[i]]; }
} // 2. ジャンプ表を2倍化 (必ず実行!) const nextJumpTable=new Uint32Array(n +
1); for (let i=1; i <=n; i++) { nextJumpTable[i]=jumpTable[jumpTable[i]]; }
jumpTable=nextJumpTable; // 3. 右シフト remainingSteps>>= 1n; }