高速なビームサーチが欲しい!!! - Qiita

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はアルゴリズム強化月間の一環として書かれた記事です。 はじめに こんにちは！ rhooというアカウント名で競技プログラミングをやっている者です。 半年ほど前からヒューリスティック系のコンテストにも手を出し始めました。 この記事では私がゲーム実況者xの挑戦という過去問を解くときに使った手法の解説記事となります。 要約 ビームサーチの状態の管理を差分を持った木構造で管理するとコピーコストが発生しなくなり高速になります。 前提知識 ビームサーチについての基礎的な知識と参照カウントベースのスマートポインタ(c++でのshared_ptr