【要約】Advent of Code 2024 Day 22 - Monkey Market [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
開発者がAdvent of Codeの課題を解く際、計算量の爆発という問題に直面した。
- ・Part 1では、算術演算を愚直に行うと計算コストが増大する。
- ・Part 2では、全買い手に対して全価格変動パターンを試行する必要がある。
- ・価格変化の組み合わせは約13万通りに及び、全探索は現実的ではない。
// Approach
開発者は、ビット演算による高速化と、探索の方向性を逆転させる手法を採用した。
- ・Part 1では、2のべき乗を用いた演算をビットシフトとANDマスクに置換した。
- ・Part 2では、パターンを全探索せず、買い手ごとに発生するパターンを収集した。
- ・
collections.deque(maxlen=4)を使い、時系列データの管理を効率化した。 - ・
defaultdictとsetを用いて、パターンの集計と重複排除を両立した。
// Result
開発者は、計算量を劇的に削減し、制限時間内での解出に成功した。
- ・ビット演算の導入により、疑似乱数生成のステップを軽量化した。
- ・探索の方向性を変え、計算量を「全パターン数」から「発生パターン数」へ抑えた。
- ・これにより、膨大な組み合わせを持つ価格変動パターンの集計が可能となった。
Senior Engineer Insight
> 計算量のオーダーを制御する重要性が示されている。特に「全探索」から「事象の集計」への転換は、大規模データ処理において極めて実践的な知見だ。ビット演算による低レイテンシ化も、シミュレーション環境の構築において不可欠な技術である。