AtCoder Introduction au rapport de participation au concours Heuristique

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.

    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())
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)
    if new_S < S:
        t[d] = old
        S = new_S
for e in t:
    if 0 <= e <= 25:
        print(e + 1)
    else:
        print(0)

Recommended Posts

AtCoder Introduction au rapport de participation au concours Heuristique
AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 165 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation
AtCoder Débutant Contest 179 Rapport de participation
Concours AtCoder Débutant 182
AtCoder Beginner Contest 146 Rapport de participation
AtCoder Beginner Contest 152 Rapport de participation
AtCoder Débutant Contest 155 Rapport de participation
AtCoder Beginner Contest 174 Rapport de participation
AtCoder Beginner Contest 171 Rapport de participation
AtCoder Beginner Contest 149 Rapport de participation
AtCoder Beginner Contest 148 Rapport de participation
AtCoder Débutant Contest 170 Rapport de participation
AtCoder Chokudai Contest 005 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
AtCoder Débutant Contest 183 Rapport de participation
Rapport de participation au concours de programmation AtCoder HHKB 2020
Rapport de participation au concours de programmation AtCoder Acing 2020
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
Rapport de participation au concours d'entraînement de la bibliothèque AtCoder (Python)
AtCoder Judge System Update Test Contest 202004 Rapport de participation
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Rapport de participation
Fiche d'inscription au concours ACL pour débutant
Journal de participation Atcoder Beginner Contest 146
AtCoder Hitachi, Ltd.Rapport de participation au concours de programmation de la Division des systèmes sociaux 2020
Rapport de participation au test pratique du 3e algorithme AtCoder
Introduction à MQTT (Introduction)
Introduction à Scrapy (3)
Premiers pas avec Supervisor
Introduction à Tkinter 1: Introduction
rapport de participation abc154
rapport de participation abc155
Concours AtCoder Débutant 179
Concours AtCoder Débutant 180
Introduction à PyQt
Introduction à Scrapy (2)
Concours AtCoder Débutant 173
AtCoder 2nd Algorithm Practical Test Virtual Participation Report
[Linux] Introduction à Linux
Introduction à Scrapy (4)