Namaran

Code daily. Without assist.

2026-10-29

VisitOrders.hs

import Data.Array
import Data.Bits

n :: Int
n = 4

linked :: Int -> Int -> Bool
linked u v = (min u v, max u v) `elem` [(0, 1), (0, 2), (1, 3), (2, 3)]

paths :: Integer
paths = memo ! (0, 0)
 where
  full = bit n - 1 :: Int
  memo = listArray ((0, 0), (full, n - 1)) [go s v | s <- [0 .. full], v <- [0 .. n - 1]]
  go s v
    | s == full = 1
    | otherwise = sum [memo ! (setBit s w, w) | w <- [0 .. n - 1], not (testBit s w), linked v w]

main :: IO ()
main = print paths

頂点0から出発し、linked でつながった頂点へ移りながら4つの頂点をちょうど1回ずつ通る道順の数を数えるつもりの paths です。memo ! (s, v) は、ビット s で表した頂点の集合を通り終えて頂点 v にいるときの、残りの道順の数です。4つの頂点は0、1、3、2の順に辺で輪につながっているので、道順は 0→1→3→2 と 0→2→3→1 の2通りで、本来は 2 と出力されるはずが、いまは 4 と出力されます。

Answer

Wrong

paths = memo ! (0, 0)

memo ! (0, 0) は「頂点0にいるが、通り終えた頂点の集合は空」という状態です。集合に0が入っていないので、go は頂点0をまだ通っていない頂点として扱い、隣の頂点から0へ戻る移動を許します。そのうえ、集合が全部そろうには0がどこかで集合に入る必要があるので、数えられるのは、途中か最後にちょうど1回0へ戻ってくる道だけです。

この輪では、0→1→0→2→3、0→2→0→1→3、0→1→3→2→0、0→2→3→1→0 の4通りがその形をしています。どれも0を2回通るので、本来は数えてはいけない道です。本来の2通りは、最後まで0に戻らないので、全部の集合にたどり着かず数えられていません。

Right

paths = memo ! (bit 0, 0)

出発した時点で頂点0はもう通っているので、初めの集合を0番目のビットだけが立った bit 0 にします。すると0へ戻る移動は not (testBit s w) で弾かれ、数えられるのは0から出て残りの3つを1回ずつ通る道だけになり、0→1→3→2 と 0→2→3→1 の2通りが数えられます。