結果

問題 No.286 Modulo Discount Store
コンテスト
ユーザー Tatamo
提出日時 2016-07-19 19:22:02
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 2,976 bytes
コンパイル時間 79 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-10-15 17:24:46
合計ジャッジ時間 24,076 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 21 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
import random

# GA

n = input()
m = []
for i in range(n):
    m.append(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 Solution:
    def __init__(self, gene):
        self.gene = gene
	self.value = 0
	if(len(gene)!=0):
	    self.eval()
    def eval(self):
	discount = 0
	self.value = 0
	for c in self.gene:
	    self.value += max(c-discount,0)
	    discount = (discount+c)%1000

NUM_POP = 30 # 少なくとも2以上かつ偶数にして
GENERATION = 2000
MUTANTRATE_RATE = 30 # ‰

# 最初の個体群をランダム生成
pop = [Solution(generateGene()) for x in xrange(NUM_POP)]

for gc in xrange(GENERATION):

    min_val = sum(m)
    max_val = -1
    top_index = -1
    top2_index = -1

    # 評価補助テーブル生成
    for i,s in enumerate(pop):
	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


    #print "max:", max_val, "min:", min_val

    pickup_table = [0]*n
    probability_sum = 0
    for i in xrange(n):
	pickup_table[i] = max_val - pop[i].value
	probability_sum += pickup_table[i]

    # 評価の高さに基づいた確率により個体を交叉させ新個体を生成
    left = NUM_POP - 2
    #new_pop = [Solution(pop[top_index].gene[:]),Solution(pop[top2_index].gene[:])]
    top_s = Solution([])
    top_s.gene = pop[top_index].gene[:]
    top_s.eval()
    top2_s = Solution([])
    top2_s.gene = pop[top2_index].gene[:]
    top2_s.eval()
    new_pop = [top_s, top2_s]
    #print "top:", top_s.value, top_s.gene

    while(left>0):
	# 2個体pickする
	sum1 = 0
	sum2 = 0
	r1 = random.randint(0,probability_sum)
	r2 = random.randint(0,probability_sum)
	for s in pop:
	    sum1 += s.value
	    if(sum1>=r1):
		solution1 = s
		break
	for s in pop:
	    sum2 += s.value
	    if(sum2>=r2):
		solution2 = s
		break
		
	# 二点交叉
	a,b = (random.randint(0,n),random.randint(0,n))
	first, second = min(a,b), max(a,b)
	new1 = Solution([])
	new1.gene = solution1.gene[:] 
	new2 = Solution([])
	new2.gene = solution2.gene[:] 
	for i in range(first, second):
	    new1.gene[i] = solution2.gene[i]
	    new2.gene[i] = solution1.gene[i] 

	new1.eval()
	new2.eval()
	# 生成した新個体をテーブルに追加
	new_pop.append(new1)
	new_pop.append(new2)
	left -= 2
    pop = new_pop
    
    # 突然変異を発生させる
    for s in pop:
	rand = random.randint(1,1000)
	if(rand <= MUTANTRATE_RATE):
	    # ランダムな遺伝子2つを入れ替える
	    #print "before:", s.gene, s.value
	    a,b = (random.randint(0,n-1),random.randint(0,n-1)) # 重複しないとは言っていない
	    tmp = s.gene[a]
	    s.gene[a] = s.gene[b]
	    s.gene[b] = tmp
	    s.eval()
	    #print "after:", s.gene, s.value



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

print top.value
0