「タワー・ビルディング」問題

「タワー・ビルディング」問題

締め切りが 2018/01/04 10:00 AM なので，その 1 分後に投稿されるように予約

設問

A を一辺が 1 の立方体のブロックとし、B を縦が 1、横が 1、高さが 2 の直方体のブロックとします。
（下は横から見た図です。）
 
自然数 n, a, b に対し、A を最大 a 個、B を最大 b 個使って、縦が 1、横が 1、高さが n の直方体の塔を作ります。
このときの積み上げ方の場合の数を F(n, a, b) と定義します。
 
例えば F(6, 4, 2)＝11 です。以下に示します。

同様に、F(4, 3, 1)＝3, F(4, 4, 4)＝5, F(5, 2, 1)＝0, F(10, 5, 3)＝35 です。
また、F(100, 50, 50) を 1000003 で割った余りは 765461 となることが確かめられます。
 
標準入力から、自然数 n, a, b（1 ≦ n ≦ 500, 0 ≦ a ≦ n, 0 ≦ b ≦ n）が半角空白区切りで与えられます。
標準出力に F(n, a, b) を 1000003 で割った余りを出力するプログラムを書いてください。
 
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

n, a, b が小さいときの解を図のようにまとめれば，規則性が見える（二項係数である）

i, j は x の添え字

そこで，以下のようにプログラムすれば，爆速である。

f = function(n, a, b) {
  n1 = n + 1
  n2 = n + 2
  x = matrix(0, n1, n2)
  for (i in 1:n1) {
    x[i, i+1] = 1
  }
  for (i in 3:n1) {
    for (j in seq(3-i%%2, i-1, by=2)) {
      x[i,j] = (x[i-1, j-1]+x[i-2, j]) %% 1000003
    }
  }
  count = 0
  for (j in 2:n2) {
    if (a >= j-2 && b >= (n-j+2) %/% 2) {
      count = (count+x[n+1,j]) %% 1000003
    }
  }
  cat(count, "\n")
}

#arg = scan(file("stdin", "r"), sep=" ")
#f(arg[1], arg[2], arg[3])

f(6, 4, 2) # 11
f(100, 50, 50) # 765461
f(7, 5, 2) # 16
f(29, 10, 10) # 92378
f(500, 249, 125) # 0
f(123, 81, 82) # 475012
f(436, 400, 212) # 544100
f(497, 490, 399) # 663760

カエル跳びゲームを一般化して！

カエル跳びゲームを一般化して！

締め切りが 2018/01/02 10:00 AM なので，その 1 分後に投稿されるように予約

パズルで有名な「カエル跳びゲーム」を一般化したものを考えます。
n 個のマスがあり、左側から a マスには右に進むa匹のカエルが、右側から b マスには左に進むb匹のカエルがいます。
1つのマスには1匹のカエルしか入れられず、一度に1匹のカエルを移動します。

このカエルの位置を左右入れ替えることを考えます。
（右向きのカエルをすべて右側に、左向きのカエルをすべて左端に寄せるまで繰り返します。）

それぞれのカエルは、進む方向の隣のマスが空いていれば、その場所に移動できます。
また、隣に相手のカエルがいても、その先が空いていれば、一マスだけ飛び越えることができます。
二匹以上のカエルは飛び越えることはできませんし、同じ向きのカエルを飛び越えることもできません。
当然、逆方向に進むこともできません。

この操作を行い、最短の回数で移動するときの移動回数を求めてください。
なお、それぞれの向きのカエルを交互に移動する必要はありませんので、どちらから始めても構いませんし、同じ向きのカエルを連続して動かしても構いません。

例えば、n = 5, a = 2, b = 2 のとき、以下の図のような手順で移動すると、8回で移動できます。

標準入力から n, a, b がスペースで区切って与えられますので、最短の移動回数を標準出力に出力してください。
なお、n, a, b は n > a + b を満たす整数で、n は最大で14とします。

【入出力サンプル】
標準入力
5 2 2

標準出力
8

==================================================================

n, a, b が小さいときの解を求め，規則性を調べる。

これをプログラム化して，以下を得る。計算は，瞬時に終わる。

f = function(n, a, b) {
  x = array(0, dim = c(n - 2, n - 2, n))
  for (N in 3:n) {
    mx = N - 2
    for (A in 1:mx) {
      B = mx + 1 - A
      x[A, B, N] = A * B + A + B
    }
    if (N >= 4) {
      for (A in 1:(mx - 1)) {
        for (B in 1:(mx - A)) {
          x[A, B, N] = x[A, B, N - 1] + A + B
        }
      }
    }
  }
  cat(x[a, b, n])
}

#arg = scan(file("stdin", "r"))
#f(arg[1], arg[2], arg[3])

f(5, 2, 2) # 8
f(8, 2, 5) # 17
f(10, 3, 3) # 33
f(12, 4, 5) # 47
f(14, 6, 6) # 60

参考までに，n, a, b が小さいときの解を求めるプログラムを以下に示す。
これは，http://www.geocities.jp/m_hiroi/puzzle/kaeru.html に示されている perl によるプログラムを R に書き換えたものである。

f = function(n, a, b) {
  space = rep(" ", n - a - b)
  a = rep("a", a)
  b = rep("b", b)
  start = paste(c(a, space, b), collapse = "")
  goal  = paste(c(b, space, a), collapse = "")
 
  state = integer(50000)        # 状態を格納
  prev_state = integer(50000)   # 前の状態を指す
  state_check = character(50000)  # 状態チェックのハッシュ
 
  # 置換用
  search =  c("ab ", " ab", "a ", " b")
  replace = c(" ba", "ba ", " a", "b ")
 
  w = 2     # ライトカウンタ
  r = 0     # リードカウンタ
  # 初期化
  state[1] = start
  prev_state[1] = -1
 
  print_answer = function(i, disp = FALSE) {
    count = 0
    
    if (disp) {
      cat(state[i], "\n")
    }
    repeat {
      i = prev_state[i]
      if (disp) {
        cat(state[i], "\n")
      }
      count = count + 1
      if (prev_state[i] == -1) {
        break
      }
    }
    #cat(count)
    count
  }
 
  repeat {
    r = r + 1
    if (r >= w) {
      break
    }
    for (i in 1:4) {
      new = state[r]
      sea = sprintf("(.*)%s(.*)", search[i])
      rep = sprintf("\\1%s\\2", replace[i])
      new2 = sub(sea, rep, new)
      if (new != new2) {
        state[w] = new2
        prev_state[w] = r
        if (!any(grepl(new2, state_check[1:w]))) {
          if (goal == new2) {
            return(print_answer(w))
          }
          state_check[w] = new2
          w = w + 1
        }
      }
    }
  }
}