AtCoder Introduction au rapport de participation au concours Heuristique

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))

Impressions, points de réflexion, etc.

-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.

Chronologie

Voici une chronologie approximative.

[21:00] Je dormais (Oi).
[21:08] Je me suis levé et je suis devenu ah! Et j'ai accédé précipitamment à https://atcoder.jp/.
[21:12] J'ai lu la phrase de question de A, et en pensant que je ne pouvais pas comprendre la traduction, j'ai donné pour l'instant ce qui suit et j'ai obtenu 13639 points.Je n'ai vu que le nombre de jours d'entrée (rires).

    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)

[21:32] B La réponse de l'exemple d'entrée de la question ne correspond pas facilement. J'ai abandonné l'indexation 0 parce que cela ne peut pas être aidé, et cela correspondait quand je l'ai changé en 1-indexé, alors je l'ai soumis et j'ai réussi.

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)

[21:44] J'ai pu écrire le problème C, alors quand je l'ai soumis, j'ai fait un TLE et il est devenu ???.

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())

[21:49] Réécrivez le problème B en indexé 0 et relancez AC. 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)

[21:49] Presque en même temps, je relance le problème C juste en changeant le langage en PyPy (c'est-à-dire qu'il reste indexé à 1) et à nouveau TLE. Voici la limite de M ≤ 10 ^{5 </ sup> pour la première fois. Regardez et revenez au problème A.}
[22:02] Sur la base de ce que j'ai appris dans le problème C, je l'ai réécrit en un code qui s'améliore aléatoirement jusqu'à 1,5 seconde, et le relance dans le problème A. 0 point. Je ne remarque pas que la mise à jour du score manque. ..

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)

[22:14] J'étais inquiet et j'ai changé le niveau de satisfaction que je savais correct à la question B en critères d'évaluation. À ce moment-là, j'ai remarqué que la mise à jour du score avait été omise, mais la mise à jour était erronée et à nouveau 0 point (Explosion). Également changé en 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

[22:20] Je me suis demandé si je faisais une mauvaise réponse en chemin, j'ai réécrit la sortie pour la rendre au moins valide, mais 0 est invalide en premier lieu (explosion). Donc, 0 point à nouveau.

for e in t:
    if 0 <= e <= 25:
        print(e + 1)
    else:
        print(0)

[22:25] J'ai finalement réalisé que la mise à jour du score était erronée et j'ai obtenu 9634428 points! Dans le classement, c'est à environ 20% du bas. Cependant, si vous regardez de près, c'était un ordre de grandeur erroné et 7,5% (explosion).
[22:30] Quand j'ai changé la langue en PyPy, j'ai obtenu 75379880 points à la fois !! J'ai obtenu environ 60% des premiers points et le classement était de 40% par rapport au sommet.
[22:39] Amélioration renvoyée à évaluer par score au lieu de satisfaction 82463631 points.
[22:44] while time () --start_time + 0.15 <limit_secs:, changé pour penser jusqu'à la dernière minute. 81865683 points (vers le bas).
[22:49] 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.