JOI 21二次予選 B パンケーキ(難易度8)
パンケーキの味の種類を''A', 'B', 'C'の形そのままで扱うと厳しい(mapなどのlogがつくデータ構造を用いなければならず, しかも定数倍が重い). そこで'A', 'B', 'C'を0, 1, 2の数字に変換し, 3進数として数字の形で扱うことを考える.
そしてせいぜい$ 3^Nしか状態が存在しないことから, グラフに帰着することを考える.
各状態を頂点としたグラフを考えると, そこから行ける状態にコスト1の無向辺を張ってBFSをしていけば各状態についての答えが求まることがわかる.
行ける状態を求める際, 解説コードではbit演算を駆使しているが3進数→文字列の逆変換関数を用意し素直にreverse操作を行っていっても計算量は悪くなるものの間に合う.
BFSの際, 明にグラフを持つ必要はなく, 次の頂点が分かればよい(たぶん明に持つとTLEする).