1

この問題は、interviewstreet.comからの引用です。

整数の配列 Y=y1,...,yn が与えられると、線分 i の端点が (i, 0) と (i, yi) となるような n 個の線分があります。各セグメントの上から水平光線が左に発射され、この光線が別のセグメントに触れるか、y 軸に当たると停止すると想像してください。n 個の整数 v1, ..., vn の配列を作成します。ここで、vi はセグメント i の上部から放たれる光線の長さに等しくなります。V(y1, ..., yn) = v1 + ... + vn と定義します。

たとえば、Y=[3,2,5,3,3,4,1,2] の場合、v1, ..., v8 = [1,1,3,1,1,3,1, 2]、下の図に示すように：

ここに画像の説明を入力

[1,...,n] の順列 p ごとに、V(yp1, ..., ypn) を計算できます。[1,...,n] の一様ランダム順列 p を選択すると、V(yp1, ..., ypn) の期待値はいくらになるでしょうか?

入力フォーマット

入力の最初の行には、単一の整数 T (1 <= T <= 100) が含まれます。T テスト ケースが続きます。

各テストケースの最初の行は、単一の整数 N (1 <= N <= 50) です。次の行には、1 つのスペースで区切られた正の整数 y1、...、yN が含まれます (0 < yi <= 1000)。

出力フォーマット

各テスト ケースの出力期待値 V(yp1, ..., ypn) について、小数点以下 2 桁に丸められます。

サンプル入力

6
3
1 2 3
3
3 3 3
3
2 2 3
4
10 2 4 4
5
10 10 10 5 10
6
1 2 3 4 5 6

サンプル出力

4.33
3.00
4.00
6.00
5.80
11.15

説明

ケース 1: V(1,2,3) = 1+2+3 = 6、V(1,3,2) = 1+2+1 = 4、V(2,1,3) = 1+ 1+3 = 5、V(2,3,1) = 1+2+1 = 4、V(3,1,2) = 1+1+2 = 4、V(3,2,1) = 1 +1+1 = 3。これらの値の平均は 4.33 です。

ケース 2: 順列がどうであれ、V(yp1, yp2, yp3) = 1+1+1 = 3 なので、答えは 3.00 です。

ケース 3: V(y1、y2、y3)=V(y2、y1、y3) = 5、V(y1、y3、y2)=V(y2、y3、y1) = 4、V(y3、y1、y2) )=V(y3, y2, y1) = 3 であり、これらの値の平均は 4.00 です。

この問題に対する素朴な解決策は、N=50 に対して永久に実行されます。各スティックの値を個別に計算することで問題を解決できると思います。この問題に対する他の効率的なアプローチがあるかどうかを知る必要があります。各スティックの値を個別に計算する必要がある根拠は何ですか?

4

3 に答える 3

7

これはhttps://cs.stackexchange.com/questions/1076/how-to-approach-vertical-sticks-challengeと同じ質問であり、そこでの私の答え (ここで以前に与えられたものより少し単純です) は次のとおりです。

別の問題を想像してみてください:スロットkに同じ高さのスティックを配置する必要がある場合n、スティック間の予想される距離 (および最初のスティックと概念的なスロットの0間の予想される距離、および最後のスティックと概念的なスロットの間の予想される距離n+1) は次のとおりです。長さに収まる隙間(n+1)/(k+1)があるので。k+1n+1

この問題に戻ると、特定のスティックは、(それ自体を含めて) 何本のスティックが同じ高さかそれ以上であるかに関心があります。これがkである場合、その前に予想されるギャップも (n+1)/(k+1)です。

したがって、アルゴリズムは、各スティックのこの値を見つけて、期待値を合計するだけです。たとえば、 の高さから始めて3,2,5,3,3,4,1,2、それ以上の高さの棒の数は である5,7,1,5,5,2,8,7ため、期待値は9/6+9/8+9/2+9/6+9/6+9/3+9/9+9/8 = 15.25です。

これは簡単にプログラムできます: たとえば、R の 1 行

V <- function(Y){(length(Y) + 1) * sum(1 / (rowSums(outer(Y, Y, "<=")) + 1) )}

元の問題のサンプル出力の値を与える 

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15
于 2013-08-23T22:05:38.420 に答える
7

この問題は、次のことを理解することで解決できます。

k番目の棒がi番目の位置に置かれた場合、この棒の期待される光線の長さはいくらか。

次に、すべての位置のすべてのスティックの予想されるすべての長さを合計することで、問題を解決できます。

をi番目の位置に置かれたk番目のスティックexpected[k][i]の予想される光線の長さ、を に等しい光線の長さでi番目の位置に置かれたk番目のスティックの順列の数とする。num[k][i][length]length

expected[k][i] = sum( num[k][i][length] * length ) / N!

計算方法はnum[k][i][length]？たとえばlength=3、次のグラフを考えてみましょう。

...GxxxI...

位置はどこですかI。3 つの「x」は、厳密に より低い 3 つの棒が必要であることIをG意味し、少なくとも と同じ高さの棒が必要であることを意味しIます。を1 番目のスティックよりs_iも小さいスティックの数とし、を 1 番目 のスティック以上のスティックの数とする。位置なので、次のようになります。kg_ikg_iGlengths_ix

num[k][i][length] = P(s_i, length) * g_i * P(n-length-1-1)

前のすべてのポジションIが よりも小さい場合I、 に大きなスティックは必要ありませんG。つまりxxxI....、次のようになります。

num[k][i][length] = P(s_i, length) * P(n-length-1)

この問題を解決できる Python コードを次に示します。

def solve(n, ys):
    ret = 0
    for y_i in ys:
        s_i = len(filter(lambda x: x < y_i, ys))
        g_i = len(filter(lambda x: x >= y_i, ys)) - 1

        for i in range(n):
            for length in range(1, i+1):
                if length == i:
                    t_ret = combination[s_i][length] * factorial[length] * factorial[ n - length - 1 ] 
                else:
                    t_ret = combination[s_i][length] * factorial[length] * g_i * factorial[ n - length - 1 - 1 ]
                ret += t_ret * length

    return ret * 1.0 / factorial[n] + n
于 2013-03-03T15:47:55.017 に答える
1

ご承知のとおり、スティックごとに個別に問題を解決できます。

F（i、len）を順列の数とし、スティックiからの光線は正確にlenです。
次に答えは

（Sum（by i、len）F（i、len）* len）/（n！）

あとはF（i、len）を数えるだけです。a（i）をスティックの数jとし、y_j<=y_iとします。b（i）-スティックの数、b_j>b_i。

長さlenの光線を取得するには、このような状況が必要です。

B, l...l, O  
   len-1 times

ここで、O-はスティック#iです。B-より長い、または始まりのスティックです。l-高さを維持し、i番目よりも小さい。

これにより、2つのケースが得られます
。1）Bは始まりであり、これはいくつかのP(a(i), len-1) * (b(i)+a(i)-(len-1))!方法で達成できます。
2）Bはより大きなスティックであり、これはいくつかのP(a(i), len-1)*b(i)*(b(i)+a(i)-len)!*(n-len)方法で達成できます。

編集：ケース2のa（i）の代わりに（mul）の第2項としてb（i）を修正しました。

于 2012-04-06T08:17:36.343 に答える