Namaran

Code daily. Without assist.

2026-10-29

Grow.hs

import Data.Array
import Data.Bits

main :: IO ()
main = print (sum [ways ! bit i | i <- [0 .. n - 1]])
 where
  n = 10
  full = bit n - 1 :: Int
  ways = listArray (0, full) (map go [0 .. full]) :: Array Int Integer
  go s
    | s == full = 1
    | otherwise = sum [ways ! setBit s j | j <- [0 .. n - 1], not (testBit s j), touches s j]
  touches s j = (j > 0 && testBit s (j - 1)) || testBit s (j + 1)

これは何を出力するでしょうか?

Answer

512 です。

ways ! s は、ビット s で表した集合から始めて、まだ入っていない番号 j を1つずつ加えて10個全部にする順番の数です。加えてよいのは、j - 1 か j + 1 がすでに集合にある j だけです。ways は自分自身を参照する配列ですが、要素は遅延評価で必要になったときに計算されるので、番号の小さい順に埋める必要はありません。main は、1つの番号だけを入れた10通りの集合から始めた数を足しています。

1024通りの集合を追う代わりに、集合がどんな形をとるかを見ます。最初の集合は1つの番号だけで、隣り合う番号が切れ目なく並んだ区間です。区間に入っていない番号のうち、隣が区間に入っているのは区間の左端のすぐ左と右端のすぐ右だけなので、加えたあとも集合は区間のままです。そのため、どの順番も「区間を左へ1つ広げるか、右へ1つ広げるか」の選択を9回続けたものになります。

番号 i から始めると、9回のうち左を選ぶのはちょうど i 回で、その順番の数は、9回のうち左を選ぶ回を i 回選ぶ組合せの数 9Ci です。i を0から9まで足すと、9回それぞれで左右を自由に選んだ場合の数と同じ 29 = 512 になります。左右の選び方の列1つが、始める番号を決め(左の回数が始めた番号)、順番も決めるからです。

加える条件を見落として、10個を好きな順に並べる数と考えると 10! = 3628800 と答えてしまいます。