Google Code Jam 2006 、練習部屋が用意されていたので早速練習してみました。

まず、250 点問題。スタート都市(index=0)からゴールの都市(index=1)まで、セールスマンを何人派遣できるでしょうか？という問題です。都市通しのつながり(adj)は、

"001111",
"001111",
"110000",
"110000",
"110000",
"110000"

このようにマトリックス形式で与えられます。都市の数は最大 12 です。入力の条件としてスタート都市とゴール都市は、直接つながっていないことが保障されています（adj[0][1] == adj[1][0] == 0 です）。スタート都市とゴールの都市を除いた、途中の通過都市はそれぞれ最大 1 人のセールスマンだけが通過できます。つまりあるセールスマンが通過した都市は、別のセールスマンは通過できません。この入力の場合は、正解は 4 人です([0 -> 2 -> 1], [0 -> 3 -> 1], [0 -> 4 -> 1], [0 -> 5 -> 1]の 4 通り)。

いつもは Java ですが、せっかくですので Python で書いてみました。

class SalesRouting:

  def howMany(self, adj):

      def doit(u, mask):
          if (u, mask) in memo: return memo[u,mask]
          if adj[u][1] == '1': return doit(0, mask) + 1
          memo[u,mask] = max([0] +
                             [doit(v, mask | 1<<v) for v in range(2, len(adj))
                              if adj[u][v] == '1' and (mask & (1<<v)) == 0])
          return memo[u,mask]

      memo = {}
      return doit(0, 0)

状態空間は、現在いる city: u(N 通り) と、 これまで通過した city 全て: mask(2^N 通り)の組み合わせになります。 ワーストケースでもたかだか 12 * 2^12 = 50,000 ほどですので、Python でも十分通ります。