れんしゅうちょう。

■ Problem D. GoroSort 23:33

問題

"Algorithms are not Goro's strength; strength is Goro's strength."

駄洒落かよ･･･

問題文は比較的読みやすかった。

明らかに既に揃っている所は固定した方が良いのと、ランダムに並べ替えるという事で、あるべき場所でない個数kを用いて、E(k)と表せるだろうと考える。

サンプル見てたら、E(k)=k (k=2,4)が解る。

E(3)は手動で解いたら3だった。

E(k)=kっぽいなーと思いつつsampleの下を読むと、4の時は2つずつ押さえるとか書いてあって、自分が想定していた

「常に"あるべき場所"のだけ全部固定、それ以外をシャッフル」

が正しくないかもしれないと思いつつE(4)をその手法で計算すると4に。

E(5)を漸化式立てながら計算すると、5になる。

漸化式が見えたので、E(k)=kを仮定して変形しまくると、次が成立すれば良い事が解る。

ここで、a_kはモンモール数です。

とりあえずこれを用いて100程度まで正しい事を確認してみました。

$a=[]
def a(n)
    return $a[n] unless $a[n].nil?
    return 1 if n.zero?
    return 0 if n == 1
    return 1 if n == 2
    return $a[n] = (n-1) * (a(n-1) + a(n-2))
end
def C(n,k)
    res = 1
    for i in 0...k
        res *= n-i
        res /= i+1
    end
    res
end
def factorial(n)
    return 1 if n.zero?
    return n*factorial(n-1)
end
def f(n)
    res = 0
    for k in 0...n
        res += (n-k) * C(n,k) * a(k)
    end
    res
end
for n in 1..100
    p n unless f(n)==factorial(n)
end

何も表示されないので正しいようです。

という事で、解答は

geti
getia.each.with_index.map{|x,i|x==i+1?0:1}.inject(&:+)

smallをAC、largeもそのまま投げる。

直感的には、k箇所の間違えがあって、その部分をランダムに並べ替えたら、ある箇所に正しいのが来る確率は1/kくらい。よって、k*(1/k)=1個くらい揃うハズ。

これがどのkでも1個なので、大体k回くらいというのは正しげに見えます。

証明にはならない感じなので、正しい証明が見たい人はこれでも読んで下さい。

自分のチェック用途中生成物は、これ以上うまくまとまらなかった気がします(´・ω・｀)

GoroSortは流行りそうだなー。

ツイートする