No Caffeine, No Life

プログラミング(主にPython)

ABC 054 C:One-stroke Path 動的計画法 メモ化再帰 ビットdp

問題:

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

解説:

頂点の数がとても少ないので、頂点の数におけるすべての順列において、すべての点をたどることができるかを深さ優先探索(dfs)で探っていく。

1番目の例は、

  • ある点と点がつながっている状態を1、そうでなければ0

と表現すると、すべての点がつながっている状態は順列間の積で表されることに注目している。(すべてつながっていれば、1 x 1 x 1 x ... x 1 = 1となるが、どこかがつながっていなければ x 0 が入り、= 0となる。これがそのまま、場合の数として使える)

2番目の例は、もう少し素直に、深さ優先探索を用いている。

3番目の例は、ビット演算を用いている。

解答例:

積を用いた方法:

深さ優先探索

ビット演算を用いた方法: