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