DouKaku? 1216 ocean: すでに類似の解答が出てますが・・・。ma...(議席数をドント方式で)

Comment detail

すでに類似の解答が出てますが・・・。max()をkeyパラメータと使うのが独自といえば独自か。（Python2.5以降）

def solve(sheet_count, votes):
    parties = [[vote, 0] for vote in votes] # list of [vote, sheet]
    for _ in xrange(sheet_count):
        party = max(parties, key=lambda party: float(party[0]) / (party[1] + 1))
        party[1] += 1
    return [party[1] for party in parties]

def main():
    print solve(100, [123, 4, 56, 78])

if __name__ == '__main__':
    main()

maxにもkeyパラメータがあったとは知らなかったです。

ええ、本当はall()とany()にも欲しいんですけどね(^^; （トランプのお題では自前で定義）

上のコードをC++(STL)に移植しました。（カバレッジ稼ぎ）

#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

class party
{
public:
    party(size_t vote) : _vote(vote), _sheet(0) {}

    friend bool operator<(const party& lhs, const party& rhs)
    {
        return lhs.key() < rhs.key();
    }

    size_t sheet() const { return _sheet; }

    void add_sheet() { ++_sheet; }

private:
    size_t _vote, _sheet;

    double key() const
    {
        return static_cast<double>(_vote) / (_sheet + 1);
    }
};

void solve(size_t sheet_count, size_t* beg, size_t* end)
{
    if (beg == end) return;

    std::vector<party> parties;

    std::copy(beg, end, std::back_inserter(parties));

    for (size_t i = 0; i < sheet_count; ++i)
    {
        std::max_element(parties.begin(), parties.end())->add_sheet();
    }

    std::transform(parties.begin(), parties.end(), beg, std::mem_fun_ref(&party::sheet));
}

int main()
{
    size_t datas[] = {123, 4, 56, 78};

    size_t* beg = datas;

    size_t* end = datas + sizeof(datas) / sizeof(*datas);

    solve(100, beg, end);

    std::copy(beg, end, std::ostream_iterator<size_t>(std::cout, " "));
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq