J'ai participé au Concours d'introduction à l'heuristique. Il s'agit du deuxième concours marathon depuis le Chokudai Contest 004. Le résultat était de 83275739 points, 497e sur 1731. Le code final a été soumis par PyPy ci-dessous.
from time import time
from random import random
limit_secs = 2
start_time = time()
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
def calc_score():
score = 0
S = 0
last = [-1] * 26
for d in range(D):
S += s[d][t[d]]
last[t[d]] = d
for i in range(26):
S -= c[i] * (d - last[i])
score += max(10 ** 6 + S, 0)
return score
def solution():
return [i % 26 for i in range(D)]
t = solution()
score = calc_score()
while time() - start_time + 0.14 < limit_secs:
d = int(random() * D)
q = int(random() * 26)
old = t[d]
t[d] = q
new_score = calc_score()
if new_score < score:
t[d] = old
else:
score = new_score
print('\n'.join(str(e + 1) for e in t))
-Au moment du Chokudai Contest 004, je n'ai pas calculé le score et n'ai pas utilisé la méthode de recherche locale, il était donc bon de connaître la stratégie générale du concours marathon. J'ai pensé. ――Je pense que la solution initiale n'est pas terrible (rires) Avez-vous fait au moins 26 types de round robins et utilisé le meilleur (rires) → J'ai essayé 26 types de solutions initiales, mais le score n'a pas changé! Après tout, la méthode militaire en direct est inutile, attendez l'explication. ――Si vous utilisez la méthode de recherche locale, la vitesse sera liée au score, donc même si l'écriture prend plus de temps que Python, je pense que vous auriez dû l'écrire en C ++. «Il a été écrit que de bonnes choses ont été écrites dans la« prochaine étape »du problème B et du problème C, mais je ne l'ai pas lu du tout pendant le concours, je le regrette. Reconsidérons après avoir appris les tactiques typiques dans le commentaire qui vient.
Voici une chronologie approximative.
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
for i in range(D):
print(i % 26 + 1)
D = int(input())
c = [None] + list(map(int, input().split()))
s = [None] + [[None] + list(map(int, input().split())) for _ in range(D)]
t = [None] + [int(input()) for _ in range(D)]
S = 0
last = [0] * 27
score = 0
for d in range(1, D + 1):
S += s[d][t[d]]
last[t[d]] = d
for i in range(1, 27):
S -= c[i] * (d - last[i])
score += max(10 ** 6 + S, 0)
print(S)
def calc_satisfaction():
S = 0
last = [0] * 27
for d in range(1, D + 1):
S += s[d][t[d]]
last[t[d]] = d
for i in range(1, 27):
S -= c[i] * (d - last[i])
return S
D = int(input())
c = [None] + list(map(int, input().split()))
s = [None] + [[None] + list(map(int, input().split())) for _ in range(D)]
t = [None] + [int(input()) for _ in range(D)]
M = int(input())
for _ in range(M):
d, q = map(int, input().split())
old = t[d]
t[d] = q
print(calc_satisfaction())
Last = [0] * 26 était faux.D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(input()) - 1 for _ in range(D)]
S = 0
last = [-1] * 26
score = 0
for d in range(D):
S += s[d][t[d]]
last[t[d]] = d
for i in range(26):
S -= c[i] * (d - last[i])
score += max(10 ** 6 + S, 0)
print(S)
from time import time
from random import random
start_time = time()
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
def calc_score():
S = 0
last = [-1] * 26
score = 0
for d in range(D):
S += s[d][t[d]]
last[t[d]] = d
for i in range(26):
S -= c[i] * (d - last[i])
score += max(10 ** 6 + S, 0)
return score
def solution():
return [i % 26 for i in range(D)]
t = solution()
score = calc_score()
while time() - start_time < 1.5:
d = int(random() * D)
q = int(random() * 26)
old = t[d]
t[d] = q
new_score = calc_score()
if new_score < score:
t[d] = old
for e in t:
print(e + 1)
while time () --start_time <limit_secs * 0.9: pour l'améliorer à la dernière minute. if new_S < S:
t[d] = old
S = new_S
for e in t:
if 0 <= e <= 25:
print(e + 1)
else:
print(0)
while time () --start_time + 0.15 <limit_secs:, changé pour penser jusqu'à la dernière minute. 81865683 points (vers le bas).while time () --start_time + 0.14 <limit_secs:, 83275738 points. C'était le code le plus élevé et le dernier, et j'ai posté le même code deux fois de plus, mais seulement avec un score faible.Recommended Posts