AtCoder Einführung in den Heuristik-Wettbewerbsbericht

Ich habe am Einführung in den Heuristik-Wettbewerb teilgenommen. Dies ist der zweite Marathon-Wettbewerb seit Chokudai-Wettbewerb 004. Das Ergebnis war 83275739 Punkte, 497. von 1731. Der endgültige Code wurde von PyPy unten eingereicht.

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

Eindrücke, Reflexionspunkte usw.

Zum Zeitpunkt des Chokudai-Wettbewerbs 004 habe ich die Punktzahl nicht berechnet und die lokale Suchmethode nicht verwendet. Daher war es gut, die allgemeine Strategie des Marathon-Wettbewerbs zu kennen. Ich dachte. ――Ich denke, die anfängliche Lösung ist nicht schrecklich (lacht). Haben Sie mindestens 26 Arten von Round Robin hergestellt und die beste verwendet (lacht)? → Ich habe 26 Arten von anfänglichen Lösungen ausprobiert, aber die Punktzahl hat sich nicht geändert! Immerhin ist die Live-Militärmethode nutzlos, warten Sie auf die Erklärung. ――Wenn Sie die lokale Suchmethode verwenden, wird die Geschwindigkeit mit der Partitur verknüpft. Selbst wenn das Schreiben länger dauert als bei Python, sollten Sie es in C ++ geschrieben haben. ――Es wurde geschrieben, dass im "nächsten Schritt" von Problem B und Problem C gute Dinge geschrieben wurden, aber ich habe es während des Wettbewerbs leider überhaupt nicht gelesen. Es macht jedoch keinen Sinn, die Live-Militärmethode anzuwenden, also werde ich in Zukunft herauskommen Lassen Sie uns das noch einmal überdenken, nachdem wir im kommenden Kommentar typische Taktiken gelernt haben.

Zeitleiste

Unten finden Sie eine grobe Zeitleiste.

[21:00] Ich habe geschlafen (Oi).
[21:08] Ich stand auf und wurde ah! Und griff hastig auf https://atcoder.jp/ zu.
[21:12] Ich habe den Fragensatz von A gelesen und während ich dachte, dass ich die Übersetzung nicht verstehen könnte, gab ich vorerst Folgendes an und bekam 13639 Punkte. Ich sah nur die Anzahl der Tage für die Eingabe (lacht).

    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 Die Antwort des Eingabebeispiels der Frage stimmt nicht leicht überein. Ich habe 0-indiziert aufgegeben, weil es nicht geholfen werden kann, und es stimmte überein, als ich es in 1-indiziert änderte, also habe ich es eingereicht und bestanden.

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] Ich konnte das C-Problem schreiben, also habe ich TLE gemacht, als ich es eingereicht habe, und es wurde ???.

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] Schreiben Sie das B-Problem auf 0-indiziert um und werfen Sie AC erneut. Last = [0] * 26 war falsch.

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] Fast zur gleichen Zeit stelle ich das C-Problem erneut, indem ich die Sprache auf PyPy ändere (dh es bleibt 1-indiziert) und erneut auf TLE. Hier ist zum ersten Mal die Grenze von M ≤ 10 ^{5 </ sup>. Schauen Sie sich an und kehren Sie zu Problem A zurück.}
[22:02] Basierend auf dem, was ich im C-Problem gelernt habe, habe ich es in einen Code umgeschrieben, der sich zufällig bis zu 1,5 Sekunden verbessert, und es erneut in das A-Problem geworfen. 0 Punkte. Ich bemerke nicht, dass das Score-Update fehlt. ..

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] Ich war besorgt und änderte die Zufriedenheitsstufe, von der ich wusste, dass sie in Problem B korrekt ist, in die Bewertungskriterien. Zu diesem Zeitpunkt bemerkte ich, dass die Aktualisierung der Punktzahl weggelassen wurde, aber die Aktualisierung war falsch und 0 Punkte erneut (Explosion). Auch geändert in while time () --start_time <limit_secs * 0.9:, um es bis zur letzten Minute zu verbessern.

    if new_S < S:
        t[d] = old
        S = new_S

[22:20] Ich habe mich gefragt, ob ich unterwegs eine falsche Antwort gegeben habe. Ich habe die Ausgabe neu geschrieben, um sie zumindest gültig zu machen, aber 0 ist an erster Stelle ungültig (Explosion). Daher wieder 0 Punkte.

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

[22:25] Endlich wurde mir klar, dass das Score-Update falsch war und ich bekam 9634428 Punkte! In der Rangliste sind es ungefähr 20% von unten. Ich denke, dass es gut ist, überhaupt eine Punktzahl von ungefähr 75% zu bekommen. Wenn Sie genau hinschauen, war es jedoch eine Größenordnung falsch und 7,5% (Explosion).
[22:30] Als ich die Sprache in PyPy änderte, bekam ich sofort 75379880 Punkte !! Ich bekam ungefähr 60% der Top-Punkte und die Rangliste war 40% von der Spitze.
[22:39] Zurückgegebene Verbesserung, die nach Punktzahl anstatt nach Zufriedenheit bewertet wird. 82463631 Punkte.
[22:44] while time () --start_time + 0.15 <limit_secs:, geändert, um bis zur letzten Minute zu denken. 81865683 Punkte (nach unten).
[22:49] while time () --start_time + 0.14 <limit_secs:, 83275738 Punkte. Dies war der höchste und letzte Code, und ich habe denselben Code noch zweimal gepostet, aber nur mit einer niedrigen Punktzahl.

[PYTHON] AtCoder Einführung in den Heuristik-Wettbewerbsbericht

AtCoder Einführung in den Heuristik-Wettbewerbsbericht

Eindrücke, Reflexionspunkte usw.

Zeitleiste