SRM 600 div2

250-概要
座席数xのバスをy本運行する。バスの運行には１台につきbaseCost + (座席数) * seatCost掛かる。
地点tにはcnt[t]人の乗客がいる。これをすべて乗せなければならない。
バスはy本同時に出発し、スタート地点と地点tを１往復する。
（地点tに複数のバスが向かってもよい。）
座席数、バスの本数を調整した時、最小のコストはいくらか。

解法
１台のバスに積む座席の数を1..max(numbers)に変化させた時のコストを全て調べた。
min(numbers)..max(numbers)でよかった。色々冗長。

ソースコード

from math import *

class TheShuttles:
    def getLeastCost(self, cnt, baseCost, seatCost):
        ret = 1 << 30
        for n in map(float,xrange(1,max(cnt)+1)):
            ret = min(ret,sum(baseCost*ceil(c/n)+seatCost*ceil(c/n)*n
                              for c in map(float,cnt)))
        return ret

600-概要
いくつかの数値numbersと目標の数値goalが一つ与えられる。
or演算によってnumbersからgoalを作るゲームをしている人がいる。
numbersから最低いくつの数値を取り除けば、or演算によってgoalを作れなくすることができるか。

解法
numbersから要素nを取り出し、goal | n > goalならnは不用
考慮する必要がない為これらは初めに取り除く
ここでnum=(110, 101, 010)からgoal=111を作り出すことを考える（いずれも2進数）
このとき1桁目のbitを埋めるにはnum[1]が必ず必要。2桁目を埋めるにはnum[0]かnum[2]が必要。
3桁目を埋めるにはnum[0]かnum[1]が必要。
以上から、少なくともnum[1]を取り除けばgoalを作れなくことがわかる。
また、どのようなnum, goalのときも同じ議論で求めることができる。
つまり (取り除くべき最小の要素数) = min(n桁目を埋めるのに使えるnumの要素数)
簡潔に書けて満足。初めに不用な要素を取り除いたのが良かった。

ソースコード

class ORSolitaireDiv2:
    def getMinimum(self, numbers, goal):
        numbers = filter(lambda x:(goal|x)<=goal,numbers)
        bl = len(format(goal,"b"))
        ret = 1 << 30
        for i in map(lambda x:1<<x,xrange(bl)):
            if i & goal > 0:
                ret = min(ret,len(filter(lambda x:i&x>0,numbers))) 
        return ret

1000-概要

解法
わかんない