（追記）解説のうしろのほうにもう少し楽な方法を書きました。

解法は解説放送と大体同じで、経過ターン数をキーにしたビームサーチです。実行時間を調整するためにビームサーチをchokudaiサーチに書き換えるという方法もありますが、ビームサーチでもビーム幅を動的に変更して実行時間を調整できるので書いておきます。

ビーム幅の設定ですが、近傍を計算する関数の実行時間を実際に計測して、そこからビーム幅を算出しました。近傍を計算する関数の実行時間が引数によって大きく変化しないので推定できる感じです。

残り時間を残りターンに等分配して、各ターンに分配された時間を一単位あたりの実行時間で割ることで、各ターンに何単位実行できるかが計算できます。一単位というのは近傍計算のことで、各ターンに何単位実行できるかというのはつまりビーム幅です。

追記

各ターンに残り時間を等分配して、各ターンでは分配された時間を使い尽くすまでループを回せば、時間を推定する必要がなくなります。解説を書いてから気がつきました。