棒の長さを最小にするモビール

棒の長さを最小にするモビール

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

設問

おしゃれなインテリアとして「モビール」があります。
Wikipedia：モビール

ここでは、同じ大きさの n 個の飾りを、糸と棒を使ってバランスを取ることを考えます。
ただし、棒の長さは整数で表され、棒の長さを整数で分割した位置にしか糸を吊るせないものとします。
一般的には一つの棒の途中など複数箇所で飾りを吊るしますが、ここでは簡単にするため「棒の両端にのみ」飾りを吊るすことにします。
また、バランスを取るときに糸や棒の重さは考えなくてよいものとします。

例えば、n = 4 のとき、以下のような吊るし方が考えられます。

このとき、左の図では棒の長さの合計が6なのに対し、右の図では9となっています。
そこで、棒の長さの合計が最小になるような吊るし方を考えます。

例えば、n = 5 のときは、以下のような吊るし方をすると棒の長さの合計が11で最小になります。

標準入力から n が与えられたとき、棒の長さの合計が最小になるような吊るし方を求め、その棒の長さの合計を標準出力に出力してください。
なお、n は最大でも500以下の正の整数とします。

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

標準出力
6

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

以前にあった，トーナメントの作成に関連する。

n が小さい場合の状況を考察すると，
f(n) = f(i) + f(j) + n / GCM(i, j)
　　n = i + j
　　GCM は最大公約数
で，i を1 ～ int(n/2) まで変化させて，最小値を求める。
n / GCM(i, j) は，最上位の 2 つのパーツを釣り合わせるために必要な棒の長さ。

R では，採点先のシステムが弱いようで，f(499) が制限時間（1 秒）をオーバーする。

euclid = function(m, n) {
    while ((temp = n%%m) != 0) {
        n = m
        m = temp
    }
    m
}

f = function(n) {
    F = integer(n)
    F[2] = 2
    if (n >= 3) {
        for (k in 3:n) {
           Min = Inf
           for (i in 1:(k %/% 2)) {
                Min = min(Min, F[i] + F[k-i] + k / euclid(i, k-i))
           }
           F[k] = Min
        }
    }
    cat(F[n])
}
# f(scan(file("stdin", "r")))

f(50) # 107
system.time(f(499)) # 1514, 0.151sec.

awk で書き換えれば O.K. となった。

function euclid(m, n) {
      while((temp = n % m) != 0) {
          n = m
          m = temp
      }
      return m
}

function min(x, y) {
    return x < y ? x : y
}

function f(n) {
    F[1] = 0
    F[2] = 2
    if (2 >= n) {
        cat F[n]
    }
    for (k = 3; i < n; k++) {
        Min = 1e15
        for (i = 1; i
            Min = min(Min, F[i] + F[k-i] + k / euclid(i, k-i))
        }
        F[k] = Min
    }
    print F[n]
}

{
    f($1)
}