結果

問題 No.286 Modulo Discount Store
ユーザー TatamoTatamo
提出日時 2016-07-19 19:04:38
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 2,496 bytes
コンパイル時間 77 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2024-10-15 17:24:16
合計ジャッジ時間 2,130 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 14 ms
6,912 KB
testcase_06 RE -
testcase_07 AC 16 ms
6,912 KB
testcase_08 AC 14 ms
6,912 KB
testcase_09 AC 13 ms
7,040 KB
testcase_10 RE -
testcase_11 WA -
testcase_12 WA -
testcase_13 RE -
testcase_14 AC 14 ms
7,040 KB
testcase_15 AC 14 ms
6,912 KB
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 AC 15 ms
6,912 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 RE -
testcase_24 WA -
testcase_25 RE -
testcase_26 AC 14 ms
6,912 KB
testcase_27 RE -
testcase_28 RE -
testcase_29 AC 13 ms
6,912 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 13 ms
6,912 KB
testcase_37 RE -
testcase_38 WA -
testcase_39 RE -
testcase_40 AC 13 ms
6,912 KB
testcase_41 AC 14 ms
6,912 KB
testcase_42 WA -
権限があれば一括ダウンロードができます

ソースコード

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
	for c in self.gene:
	    self.value += max(c-discount,0)
	    discount = (discount+c)%1000

NUM_POP = 10 # 少なくとも2以上かつ偶数にして
GENERATION = 20

# 最初の個体群をランダム生成
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

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

print top.value
0