HHKB Programming Contest 2020 - AtCoder
I made a calculation error in D, which looks easy at first glance, and got into it and solved time was 3 questions. I should have skipped it and done E.
- Counting.
- The code to read the map in one dimension with a guard was created and registered in a snippet. - Putting a guard on when loading a map python
def solve(data):
ret = 0
for i in allPosition():
if data[i] and data[i + 1]:
ret += 1
if data[i] and data[i + WIDTH]:
ret += 1
return ret
python
def solve(N, XS):
used = [0] * (200_000 + 1)
cur = 0
for i in range(N):
used[XS[i]] = 1
while used[cur]:
cur += 1
print(cur)
- It’s a double loop, but the inside is only called 200,000 times at the highest, so it’s okay.
- The size of “used” is N or N+1 and RE.
- The problem that seems simple at first glance but gets bogged down with “Oh, there are times when it overflows” and “Oh, the number of reductions depends on the width of the overflow”.
- Maybe I could have solved it if I’d calmed down and sorted it out, but I’d melted too much time away, and I was too impatient to think straight.
- In addition, the naive solution is like this python
def blute(N, A, B):
ret = 0
for ax in range(0, N - A + 1):
for ay in range(0, N - A + 1):
for bx in range(0, N - B + 1):
for by in range(0, N - B + 1):
if ax <= bx < ax + A or ax < bx + B <= ax + A:
if ay <= by < ay + A or ay < by + B <= ay + A:
continue
ret += 1
return ret
- I confirmed that dividing by (1-x)^5 yields a quadratic equation. python
>>> xs = np.array([blute(20, 10, i) for i in range(1, 11)])
>>> reduce(np.convolve, [[1, -1]] * 5, xs)[:10]
array([ 36300, -151980, 238728, -166632, 43560, 0, 0,
0, 0, 0])
- Related [[Turn a sequence of numbers into a rational expression]].
-
After I saw the big coefficient, I was like, “Oh, this was three variables, what am I supposed to do?
-
I’m not good at math, so computer. - Should I have studied Lagrangian interpolation?
-
Official Explanation
- The part that made the most sense to me was “you don’t have to consider X and Y separately because of symmetry” Dimensionality reduction by symmetry.
- I’d like to count the non-overlapping cases, but it’s hard, so I’ll subtract the overlapping cases from the total.
- I ran out of time in D. I read it later and this one seems easier for me to solve. Maybe I should have read all the problems first or used the Pomodoro timer to avoid getting bogged down.
- Thoughts.
- For example, if a square is illuminated by a square where two lights can be placed, the square will be illuminated by three of the four possible light placement combinations
- If there are N squares in total and they are illuminated by K pieces, they are illuminated by streets.
- Find K for all squares
- For example, to see how many squares continue upward, just look at the square above you and add 1.
- Do this for all four directions.
- I did it unconsciously, but this is change the order of addition.
- The sum of the number of illuminated tiles per lighting pattern is the sum of the number of illuminated lighting patterns per tile
- unAC
- Expected Maximum Value] of random variable
-
max and the probability density function of the rank-deciding statistic containing it are differentiated after finding the cumulative distribution function.
-
max(a,b,c) ⇐ x ⇔ a⇐x and b⇐x and c ⇐ x
-
like that, and inequality is easier to handle.
- https://twitter.com/maspy_stars/status/1314927370105581569?s=21
-
The expected minimum value of K uniformly random numbers in 0,1 is 1/(K+1)
This page is auto-translated from /nishio/HHKB2020 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.