イバコの生存記録

いまは競プロ(AtCoder)記事がメインです。

113. newはやっぱり重いらしい

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

atcoder.jp

 

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

 

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

これだけで普通に通ってしまいました。

 

new を削るだけでここまで差が出るか…という感想でした。特に幅優先・深さ優先探索辺りは計算量が読みづらいので、独自クラスの扱いには慎重になりたいな、と思います。