結果

問題 No.286 Modulo Discount Store
コンテスト
ユーザー Tatamo
提出日時 2016-07-20 13:01:12
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 4,694 bytes
コンパイル時間 124 ms
コンパイル使用メモリ 7,168 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-10-15 17:34:30
合計ジャッジ時間 4,211 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
import random

# GA

n = input()
m = []
for i in range(n):
    m.append((i,input()))

def generateGene():
    tmp = []
    table = m[:]
    for x in xrange(n):
	i = random.randint(0,len(table)-1)
	tmp.append(table[i])
	del(table[i])
    return tmp

class Individual:
    def __init__(self, gene):
        self.gene = gene
	self.value = 0
	self.eval()
    def eval(self):
	discount = 0
	self.value = 0
	for id,c in self.gene:
	    self.value += max(c-discount,0)
	    discount = (discount+c)%1000

class Solver:
    def __init__(self, data):
        self.NUM_POP = 30 # 少なくとも2以上かつ偶数にして
        self.GENERATION = 100
        self.MUTANTRATE_RATE = 30 # ‰
        self.data = data

    def mutantrate(self, pop):
        # 突然変異を発生させる
        for s in pop:
            rand = random.randint(1,1000)
            if(rand <= self.MUTANTRATE_RATE):
                # ランダムな遺伝子2つを入れ替える
                a,b = (random.randint(0,len(self.data)-1),random.randint(0,len(self.data)-1)) # 選択位置が重複しないとは言っていない
                tmp = s.gene[a]
                s.gene[a] = s.gene[b]
                s.gene[b] = tmp
                s.eval()

    def crossover(self, pop, prob_table):
            # 2個体pickする
            count = 0
            prob_sum = sum(prob_table)
            r1 = random.randint(0, prob_sum)
            r2 = random.randint(0, prob_sum)
            parent1 = parent2 = None
            for i,s in enumerate(pop):
                count += prob_table[i]
                if(count>=r1):
                    parent1 = s
                if(count>=r2):
                    parent2 = s
                if(parent1 != None and parent2 != None):
                    break
            return self.pmx(parent1, parent2)
    #Partially-mapped crossover http://homepage3.nifty.com/ono-t/GA/GA-order.html#PMX
    def pmx(self, parent1, parent2):
        a,b = (random.randint(0,len(self.data)),random.randint(0,len(self.data)))
        first, second = min(a,b), max(a,b)
        child1 = Individual(parent1.gene[:])
        child2 = Individual(parent2.gene[:])
        # まず選択部分を交叉する
        for i in xrange(first, second):
            child1.gene[i] = parent2.gene[i]
            child2.gene[i] = parent1.gene[i]
        c1m = child1.gene[first:second]
        c2m = child2.gene[first:second]

        # 交叉対象に含まれた要素を、対応する要素に変更する
        for i in xrange(len(self.data)):
            for ii in xrange(second-first):
                if(child1.gene[i] == c1m[ii]):
                    child1.gene[i] = c2m[ii]
                if(child2.gene[i] == c2m[ii]):
                    child2.gene[i] = c1m[ii]

        child1.eval()
        child2.eval()
        return (child1, child2)
    def solve(self):
        # 最初の個体群をランダム生成
        pop = [Individual(generateGene()) for x in xrange(self.NUM_POP)]
        for gc in xrange(self.GENERATION):

            min_val = sum([c for i, c in self.data])
            max_val = -1
            top_index = -1
            top2_index = -1

            # 評価補助テーブル生成
            for i,s in enumerate(pop):
               # print "max:" , max_val, "min:", min_val, ",", s.gene, s.value
                if(s.value < min_val):
                    min_val = s.value
                    top2_index = top_index
                    top_index = i
                if(s.value > max_val):
                    max_val = s.value


            pickup_table = [0]*len(self.data)
            for i in xrange(len(self.data)):
                pickup_table[i] = max_val - pop[i].value + 1 # 0にならないよう1足す
            #print pickup_table

            # 評価の高さに基づいた確率により個体を交叉させ新個体を生成
            left = self.NUM_POP - 2
            top_s = Individual([])
            top_s.gene = pop[top_index].gene[:]
            top_s.eval()
            top2_s = Individual([])
            top2_s.gene = pop[top2_index].gene[:]
            top2_s.eval()
            # トップ2個体はそのまま残す
            new_pop = [top_s, top2_s]

            while(left>0):
                new_pop += self.crossover(pop, pickup_table)
                # 生成した新個体をテーブルに追加
                left -= 2
            # 突然変異
            self.mutantrate(new_pop)
            pop = new_pop

        top = pop[0] 
        for s in pop:
            #print s.gene
            if(s.value < top.value):
                top = s

        print top.value


Solver(m).solve()
0