分かりづらい図を用意しました。探索範囲が小さくなってるよみたいな図式。
まあ、言われたとおりにやった。
__builtin_ctz() が便利。
$N-1$ を $5$ 進数にして、すべての桁に $2$ をかけたものが答えになる。
$0$ が出力できていなくて 1WA を出した。
連続部分列について見る問題。 左から $1$ からの $1$ ずつ増加する増加列を作ってみて、途中で作れなくなったときは、 その $i$ を $A_i$ 番目にした増加列として考えられるので、これを左から求めるのと、 同じように右から求めたものについて min をとってあげるとその位置を真ん中としたピラミッド数列の 最大の大きさがわかる。
なにか作ってみて、割り切れるかどうか系は大体 DP 配列にあまりを入れる系が多い気がする。 特に、今回は桁和のバリエーションが $126$ 個しか無いのでかなり考えやすい。 まず桁和の値を決め打ちする。仮に $d$ と置いておく。 すると、このような DP が可能になる。今回は桁 DP である。
なんでこれが思いつかないんだーという感じ。 まず $k$ 回操作を行うときの計算量は、同じ操作を行わないことを利用すると、パターン数が $4 \times 3^{k-1}$ になる。 これに $HW$ がかかってくる感じになる。 自分はヒューリスティックに枝刈りしようと思ってずっとやっていたが、実は半分全列挙ができる。
スタート地点から $10$ 回までの操作をすべて保存しておく。 そしてゴール地点から $10$ 回のまでの操作をすべて保存しておく。 そしてその中から、同じ状態のものを見つけてそれの操作回数を求めて min していくだけだった。
それぞれの状態の数は最大で $4 \times 3^9 = 78732$ であり、データの数で言えば $HW$ がかかってくるので、 $5038848$ 個くらいになる。これを map でそこまでたどり着くための最小コストを持ち、 片方を一つずつ調べていけば解くことができる。
かなり危うそうに見えるが通すことができる。
アルゴの問題なので、ヒューリスティクスな解法はあんまりないよなぁと思えばよかったが、 そっち側で考えて実装し始めたら何も考えなくなってしまうくせがある。 スタートとゴールが与えられたら半分全列挙について考えるのは手癖にしていきたい。 ちなみに A* を実装していた。md が弱いので通らない。
分かりづらい図を用意しました。探索範囲が小さくなってるよみたいな図式。
ABCDE はいい感じだと思う。E は少しテンパって変なコードを書いたがすぐに取り直せたので問題はなかった。 結果として早解きでパフォーマンスが維持できた。
F, いやーこれが思いつかないかという感じだった。ずっと言ってるけどでも本当にそうだと思う。 でも確かに、パズル系の問題を全探索で解くという場合に逆側から考えるという発想をしたことがなかったので、 まあ妥当なのかなと思った。
F についてだが、こういう問題だけじゃなくて何か中継地点を見つけながらやっていく系も半分全列挙が使えそう。 パターンを二次元みたいに考えると、円の重なるところだけを見るような感じで考えるのが良いのかな。
まあ半分全列挙と言うよりかは、双方向探索っていうちゃんとしたワードがあるから知ってればできたんだよなぁ。 Wikipedia を見てみたら、A* との比較で使われているようだから、A* を思いついたらそっちも思いつけると吉かもしれない。
あと、E を半分全列挙でといてみたが、これかなり辛い。列挙する桁和と、最終的な桁和が違うので、それぞれに対応するために計算量が ちょっと多くなる。ただ半分全列挙でよくあるソートはないみたい。これも半分全列挙と呼んで良いのか。