Good Luck Google-code-jam 2013-Round-1A

15172 ワード

Google

この問題はやはりおもしろい.問題を解決するために必要なすべての情報を与えず、一部の情報だけを与えて、正しい答えが何なのかを推測している.一定の確率で正しい結果が推測される.
Table of Contents

1問題の説明

2ソリューション

3実装と結果分析

3.1見積

3.2プロセスを処理して、すべての組み合わせを遍歴して確率の最大の組み合わせを見つけます

3.3自己構築入出力

4まとめ

1問題の説明
2からMまでのN個の数をランダムに選択し、繰り返しを許可します.さらにこのN個の数からランダムにそのサブセットを選択し、このサブセット要素の積$p_を算出する1$. K個の積$p_が得られるまで、前のステップを繰り返します.1,p_2,…,p_k$. 要求:このK個の積を与えて、元のN個数を推測して具体的な入出力要求を出して、詳しく紹介しないで、codejamのウェブサイトの上で見ていきましょう
2ソリューション
2からMまでの中からN個の数を選択し,順序を考えると$(M−1)^N$種があり,順序を考えないと大幅に減少する.
タイトルの2番目の入力N=12,M=8については,順序を考えずに18564種類しかなく,あまり大きくない.では、私たちの任務はこのK個の積に基づいて、確率の最大の組み合わせを選ぶことです.今、私たちは積が$p_であることを計算します.1,p_2,…,p_k$条件では,元の組合せがCである確率:$$P(C|p_1,p_2,...,p_k)=frac{P(C)*P(p_1,p_2,...,p_k|C)}{P(p_1,p_2,...,p_k)}$これがベイズ確率式であり,一般的な形式では,$P(A|B)=frac{P(A)P(B|A)}{P(B)}{P(B)}機械学習において重要な分類方法の一つがこのベイズ式に基づいている.
我々の目標は確率が最も大きいCを見つけることであるので,この式のすべての項を計算する必要はない,例えば分母P(p 1,p 2,...,pk)は特定のK個の積に対してすべての組合せで不変である.$P(C)$と(P(p_1,p_2,ldots,p_k|C))を計算するだけで、Cを組み合わせるため、順序を考慮しないため、各Cが取得される確率は等しくなくなり、例えば234回で6回、333回で1回しか現れず、このP(C):$$P(C)=frac{N!/(c_2!c_3!ldots c_m!)}を計算する.{(M-1)^N}$$そのうち$c_2,c_3,\ldots,c_i$は、組み合わせにおける数字iの出現回数$$P(p_1,p_2,ldots,p_k|C)=P(p_1|C)ldots P(p_2|C)ldots P(p_k|C)$$を表す
ここで,$P(p|C)=frac{要素積がpのサブセット個数}{2^N}$は,Cのすべてのサブセットを列挙して上記$P(p|C)$を算出することができる.すべての組合せに対して条件確率を計算し,その中から確率が最も大きい組合せを選択する方法が分かった.グループ積が多く推測が必要なため,ここでは大量の繰返し計算が行われるので,PとP(p|C)を全て繰り上げて計算することが望ましい.
3実装と結果分析

3.1見積
予測計算:ある組合せの確率と,この組合せのサブ集積の確率を計算する

# coding: UTF-8

import cPickle as pickle

from array import array

from sys import stdout

from sys import stderr

from random import randint



def fact(n):

    if n == 0:

        return 1

    return n * fact(n-1)



def probability(nums):

    p = fact(len(nums))

    i = 1

    c = 1

    while i < len(nums):

        if (nums[i] == nums[i-1]):

            c += 1

        else:

            p /= fact(c)

            c = 1

        i += 1

    p /= fact(c)

    return p



gcount = 0

def pre_compute(N, M):

    fo = open('dump.dat', 'w')

    nums = array('i', xrange(N))

    pset = {}



    def subset(d, p):

        if d >= N:

            if p in pset:

                pset[p] += 1

            else:

                pset[p] = 1

        else:

            subset(d+1, p)

            subset(d+1, p*nums[d])



    def search(d, lt):

        global gcount

        if d >= N:

            gcount += 1

            if (gcount % 100) == 0:

                print "generated %d.." % gcount

            pickle.dump(nums, fo)

            pickle.dump(probability(nums), fo)

            pset.clear()

            subset(0, 1)

            pickle.dump(pset, fo)

        else:

            for i in xrange(lt, M+1):

                nums[d] = i

                search(d+1, i)



    search(0, 2)

    fo.close()

1 m以上かかると予想されていますが、ロードには2 s程度しかかかりません.やはり時間を節約できます.
ロードされたコード:

def load():

    fo = open("dump.dat")

    count = 0

    table = []

    while True:

        try:

            nums=pickle.load(fo)

            prob=pickle.load(fo)

            pset=pickle.load(fo)

            table.append([nums, prob, pset])

            count += 1

            if (count % 1000) == 0:

                stderr.write("loaded %d..
" % count)

        except EOFError:

            break

    return table

3.2プロセスを処理して、すべての組み合わせを遍歴して確率の最大の組み合わせを見つけます

def process_case(case):

    table = load()



    (R, N, M, K) = map(int, raw_input().split())

    print "Case #%d:" % case

    for r in xrange(R):

        products = map(int, raw_input().split())

        max_prob = -1

        nums = []

        for item in table:

            prob = item[1]

            pset = item[2]

            for p in products:

                if p not in pset:

                    prob = 0

                    break

                prob *= pset[p]

            if prob > max_prob:

                max_prob = prob

                nums = item[0]



        for n in nums:

            stdout.write(str(n))

        stdout.write("
")

3.3自己構築入出力
実はこの問題は自分で入力を構築して、それから自分でjudgeのプログラムを書いて、第2の入力に対して、しきい値の要求は1120で、自分で入力を構築して、それから上のプログラムで推測の結果を得て、大体1300ぐらい当てました.
構築入力とjudgeコードは次のとおりです.

#       

def generate(R, N, M, K):

    fi = open('input.txt', 'w')

    fa = open('right-answer.txt', 'w')

    fi.write("1
%d %d %d %d
" % (R, N, M, K))

    nums = array('i', xrange(N))

    for i in xrange(R):

        for j in xrange(N):

            nums[j] = randint(2, M)

            fa.write("%d" % nums[j])

        fa.write('
')

        for j in xrange(K):

            p = 1

            for n in nums:

                if randint(0, 1) == 1:

                    p *= n

            fi.write("%d " % p)

        fi.write('
')

    fi.close()

    fa.close()



def judge(submit_file, answer_file, R):

    fs = open(submit_file)

    fa = open(answer_file)



    fs.readline()

    count = 0

    for i in xrange(R):

        ls = list(fs.readline().strip())

        la = list(fa.readline().strip())

        ls.sort()

        la.sort()

        if ls == la:

            count += 1

    fs.close()

    fa.close()

    return count

4まとめ
Googleの出題構想は技術の発展傾向と一致しており、統計に基づく機械学習方法は広く応用されている.この問題はベイズ式(条件確率式)を用いて推定することである.
ps 1:上のpythonコードは私の機械で3 m実行されていますが、問題の要求は4分以内に答えを提出することで、時間が少しきついので、無理に足ります.C++を使うともっと速くなります.しかし、私は後でpythonというpython解釈器を見つけました.その速度はpython公式の解釈器よりずっと速く、1分で結果が出ます.ps 2:吐くpython

def f():

    x = 1

    def g():

        x += 1

    g()

f()を呼び出すと、python 3がnonlocalキーワードを与えてこの問題を解決するまでエラーが発生します.この点については、デザイン言語があまりにも専門的ではないと言いたいだけです...
Date: 2013-05-10 Fri
Author: liyongmou
Org version 7.9.2 with Emacs version 24
Validate XHTML 1.0

<![CDATA[/*>

TimeZone構造の注意点、およびno dsvのソリューション

Cassandraコンシステンシログ分析