目盛りの消えた円

目盛りの消えた円

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

設問

有名なパズル問題の一つに「Spacer Ruler(Wikipedia)」があります。
「目盛りの消えたものさし」とも言われ、できるだけ少ない目盛りの数で1cm単位の整数を測ります。

例えば、1cm刻みで目盛りが付いている長さ10cmのものさしの場合、左図の下側にある4つの目盛りが残っていれば、それを組み合わせて図のように1cm～10cmまで測ることが可能です。

これを右図のように円形で考えてみます。
円周を n 個に分割した目盛りのうち、できるだけ多くの目盛りを消して1～nまでを測ります。
例えば、n = 10 のとき、右図の赤色の4点だけ残すと1～nまでを測れます。
3点だけ残して、1～10までを測ることはできませんので、少なくとも4点が必要です。

標準入力から n が与えられたとき、残った目盛りの数が最も少なくなる場合を求め、その残った個数を標準出力に出力してください。
なお、n は30以下の整数とします。

【入出力サンプル】
標準入力
10

標準出力
4

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

簡単なプログラムを作って，n が小さいときの答えを求め，規則性を調べる。

check = function(n, x) {
  x = c(x, n + x)
  m = length(x)
  a = matrix(-1, m, m)
  for (i in seq_along(x)) {
    for (j in seq_along(x)) {
      a[i, j] = (x[j] - x[i]) %% n
    }
  }
  all(1:(n - 1) %in% a[upper.tri(a)])
}

bincombinations = function (p) {
  retval = matrix(0, nrow = 2^p, ncol = p)
  for (n in 1:p) {
    retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))), length = 2^p)
  }
  retval
}

f = function(n) {
  p = bincombinations(n)
  Sum = rowSums(p)
  o = order(Sum)
  p = p[o,]
  for (i in 2:nrow(p)) {
    x = which(p[i,] == 1)
    ans = check(n, x)
    if (ans) {
       cat(length(x), ":", ans, "  ", x, "\n")
       break
     }
  }
}

オンライン整数列大辞典にあるかと思ったら，やはりあった。
A283297 The smallest cardinality of a difference-basis in the cyclic group of order n.
そのままだ。
ただし，一般項は示されていない。
a(n) >= (1+sqrt(4n-3))/2 が挙げられているので，a(n) = ceiling((1+sqrt(4*n-3))/2) とすると n = 20, 29, 30 のとき以外は正しい答えになる。

そこで，

f = function(n) cat(ceiling((1+sqrt(4*n-3))/2+(n==20)))
f(scan(file("stdin", "r")))

ただ，それじゃあんまりなので，先のプログラムをチューニングした。
f(28) は当方では 1 秒を切るが，先方では 1 秒を超える。

f = function(n) {
  n1 = n-1
  for (k in ceiling((1+sqrt(4*n-3))/2):n) {
    p = combn(n, k)
    i2 = rep(1:k, each=k)
    j2 = rep(1:k, k)
    kk = i2 != j2
    i2 = i2[kk]
    j2 = j2[kk]
    for (i in 2:ncol(p)) {
      x = p[, i]
      a = logical(n1)
      a[(x[j2] - x[i2]) %% n] = TRUE
      if (all(a)) {
        return(cat(k))
      }
    }
  }
}
#f(scan(file("stdin", "r")))

# f(6)  # 3
# f(10) # 4
# f(14) # 5
# system.time(f(19)) # 5, 0.011s
# system.time(f(20)) # 6, 0.115s
# system.time(f(21)) # 5, 0.024s
# system.time(f(22)) # 6, 0.093s
# system.time(f(23)) # 6, 0.110s
# system.time(f(28)) # 6, 0.397s
# system.time(f(30)) # 7, 5.789s