113. newはやっぱり重いらしい - イバコの生存記録

今日この問題を解いていて、定数倍改善で TLE が取れたのでメモ…。

問題ですが、しばらく考えて幅優先探索しかないかなぁ、と思い、状態をどのように持たせるか考察しました。 $S$ はビットと見なして整数値で持たせられますが、現在のインデックスも必要なので、独自クラスや Tuple で表現したところ普通に TLE 祭りでした。

これ以上改善案も無かったので解説を見ると、ほぼ自分と同じことをやっていました。ということは定数倍が重いのか…となって、まぁ new してるところが重いのかな、と状態を整数で表現し切ることにしました。具体的には、 $S$ が $0$ から $2^N - 1$ の整数で表現されるので、現在のインデックス $i$ は $i \times 2^N$ を足して状態にしてしまおう、という作戦です。