AtCoder Introduction to Heuristics Contest Participation Report

AtCoder Introduction to Heuristics Contest Participation Report

Participated in Introduction to Heuristics Contest. Marathon contest is the second time since Chokudai Contest 004 The result was 83275739 points, 497th out of 1731. The final code was submitted by PyPy below.

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, reflection points, etc.

-At the time of Chokudai Contest 004, the score was not calculated and the local search method was not used, so it was good to know the general strategy of the marathon contest. I thought. ――I think the initial solution is not terrible (laughs). Did you make at least 26 types of round robin and use the best one (laughs). → I tried 26 types of initial solutions, but the score did not change! After all, the live soldier method is useless, wait for the commentary. ――If you use local search method etc., speed will be linked to the score, so even if it takes longer to write than Python, I think it should have been written in C ++. ――It was written that good things were written in the "next step" of problem B and problem C, but I didn't read it at all during the contest, I regret it. Let's reconsider after learning typical tactics in the commentary that comes.

Timeline

Below is a rough timeline.

-[21:00] I was sleeping (ぉ). -[21:08] I got up and became ah! And hurriedly accessed https://atcoder.jp/. -[21:12] I read the question sentence of A, and while thinking that I couldn't understand the translation, I gave the following for the time being and got 13639 points. I only saw the number of days for input (laughs).

    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 The answer of the input example of the question does not match easily. I gave up 0-indexed because it can not be helped, and it matched when I changed it to 1-indexed, so I submitted it and passed.

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] I was able to write the C problem, so when I submitted it, I did a TLE and it became ???.

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] Rewrite problem B to 0-indexed and re-throw AC. Last = [0] * 26 was wrong.

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] Almost at the same time, I just changed the language to PyPy for the C problem (that is, it remains 1-indexed) and re-throw it again. TLE. Look at, and go back to problem A. -[22:02] Based on what I learned in the C problem, I rewrote it to a code that randomly improves until 1.5 seconds, and re-throw it in the A problem. 0 points. I do not notice that the score update is missing. ..

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] I was worried and changed the satisfaction level that I knew was correct in question B to the evaluation standard. At that time, I noticed that the update of the score was omitted, but the update was wrong and 0 points again (Explosion). Also changed to while time () --start_time <limit_secs * 0.9: to improve it to the last minute.

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

-[22:20] I wondered if I was making an incorrect answer on the way, I rewrote the output to make it at least valid, but 0 is invalid in the first place (explosion). Therefore, 0 points again.

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

-[22:25] I finally realized that the score update was wrong and got 9634428 points! In the ranking, it is about 20% from the bottom. I think that it is good to get a score of about 75% in the first place. However, if you look closely, it was an order of magnitude wrong and 7.5% (explosion). -[22:30] When I changed the language to PyPy, I got 75379880 points at once !! I got about 60% of the top score, and the ranking was 40% from the top. -[22:39] Returned improvement to be evaluated by score instead of satisfaction. 82463631 points. -[22:44] while time () --start_time + 0.15 <limit_secs:, changed to think until the last minute. 81865683 points (down). -[22:49] while time () --start_time + 0.14 <limit_secs:, 83275738 points. This was the highest and final code, and I posted the same code two more times, but only with a low score.

Recommended Posts

AtCoder Introduction to Heuristics Contest Participation Report
AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Library Practice Contest Participation Report (Python)
AtCoder Judge System Update Test Contest 202004 Participation Report
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Participation Report
ACL Beginner Contest Participation Report
Atcoder Beginner Contest 146 Participation Diary
AtCoder Hitachi, Ltd. Social Systems Division Programming Contest 2020 Participation Report
AtCoder 3rd Algorithm Practical Test Participation Report
Introduction to MQTT (Introduction)
Introduction to Scrapy (3)
Introduction to Supervisor
Introduction to Tkinter 1: Introduction
abc154 participation report
abc155 participation report
AtCoder Beginner Contest 179
AtCoder Beginner Contest 180
Introduction to PyQt
Introduction to Scrapy (2)
AtCoder Beginner Contest 173
AtCoder 2nd Algorithm Practical Test Virtual Participation Report
[Linux] Introduction to Linux
Introduction to Scrapy (4)