I could use an hour for D, so I implemented a naive solution and started to make a state transition diagram, thinking “if I do it calmly, I’ll be fine”, and with about 15 minutes left, I realized my mistake and lost my composure and went out.
- You can consider it the first to move because the cost is the same no matter at which point you move the building. - independent of the order of operations
- There are two cost 2x ways to move up and down after moving from one building to another: a cost 2x way using the hallway and a cost y way using the stairs. Determine which is cheaper and use the cheaper method. python
def solve(a, b, x, y):
ret = x
if b < a:
a -= 1
if 2 * x < y:
up = 2 * x
else:
up = y
ret += abs(a - b) * up
return ret
- Go from thinking about the smallest to the biggest, and when you want 1-5, buy 6 and split it into 1+2+3, and you’ll find it’s a good deal.
- That is, the problem of finding the largest triangular number that does not exceed n+1
- The problem is to find x such that trigonometric number. python
def solve(N):
from math import sqrt
x = int(sqrt(2 * N + 2)) - 1
if (x + 2) * (1 + x) // 2 <= N + 1:
x += 1
return N - x + 1
- It is doubtful that taking the square root is ant in terms of accuracy.
- Since N is 10^18 and the mantissa part of a double-precision floating-point number is 52 bits, or less than 16 decimal digits, a simple calculation would naturally lack precision.
- So I am checking to see if adding one more is the solution, but I have not properly considered whether this is really sufficient.
- Is there a case for a shift in the direction of reduction or not?
- Since S is cyclic, the outcome of the game is also cyclic, of course.
- I solved it in a wealthy way because I only had to judge the winners and losers a thousand times without having to make detailed calculation savings. python
def solve(N, K, S):
last = [0 if c == "R" else 1 if c == "P" else 2 for c in S]
match = [0, 1, 0, 1, 1, 2, 0, 2, 2]
for _k in range(K - 1, -1, -1):
next = []
for i in range(0, 2 * N, 2):
next.append(match[last[i % N] * 3 + last[(i + 1) % N]])
last = next
return "RPS"[last[0]]
- I thought I could use an hour, so I implemented the naive solution and started to make a state transition diagram, thinking “if I do it calmly, I’ll be fine.
- I was thinking, “I can be in any direction in at least two moves,” or “I can search for a solution within three moves, and if not, I can be in a direction convenient for parallel movement in two moves or less and return in two moves or less,” but then I realized that there might be cases where the convenient direction changes in the middle of a move. But then I realized that there might be a case where the convenient direction changes in the middle of the move.
- Thoughts.
- Let’s make a state transition diagram with the center location and 4 orientations.
- Try to draw a small range of state transitions by hand
- be liable to make a mistake
- I created a code that outputs the transition destination after one step.
- Transition to each state 7 states
- Can be in any orientation in 2 steps.
- If the solution is pre-calculated up to 3 steps later and more than 4 steps not included in it, you could go 2 steps from the start, 2 steps from the goal, maintaining posture and moving in between… can you go?
- Official Explanation
- I made a code ( step→(position, rotation)) to find which state it is in after 1-3 steps from the initial state, but it didn’t occur to me to observe a reversed version of it ( (position, rotation)→step)
This page is auto-translated from /nishio/ARC109 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.