A – Not Overflow
Note that $$$N$$$ has to be read as a signed 64-bit integer type. You could check it by either doing to comparison manually, or casting back and forth between the signed 32-bit integer type.
Time complexity: $$$O(1)$$$
B – Matrix Transposition
Simply construct a $$$W$$$-by-$$$H$$$ matrix, assign $$$B_{i, j} = A_{j, i}$$$ for all relevant $$$i, j$$$, then output it.
Alternatively, if you use Python, the numpy
library installed in AtCoder gives a really short implementation: https://atcoder.jp/contests/abc237/editorial/3344
Time complexity: $$$O(HW)$$$
C – Digital Graffiti
Simulate a "wall-following" algorithm. Specifically, let .
represent empty space, and #
represent walls. Find the first #
character in reading order. Stand to its north, facing east, with your right hand on the "wall". Then walk forwards. If your hand runs out of wall, turn right, if you run into a wall, turn left, incrementing the answer each time you change direction. Stop when you return to your starting position.
Time complexity: $$$O(HW)$$$
D – Circle Lattice Points
Working with double
floating points in this problem may cause precision issues. It's best to multiply the input by $$$10^4$$$ and convert to signed 64-bit integers right away (note that if you're reading the input as a floating point, you need to round before converting). Now the problem becomes the number of points in the circle where $$$X$$$ and $$$Y$$$ are both divisible by $$$10^4$$$.
Iterate through the multiples of $$$10^4$$$ between $$$Y - R$$$ and $$$Y + R$$$ inclusive; let the current value be $$$y$$$.
Now you want to find the minimum and maximum $$$x$$$ that remains in the circle. Either binary search for them, or use sqrt
to solve $$$(x - X)^2 + (y - Y)^2 \leq R^2$$$; however since sqrt
uses floating points, brute force its neighborhood to avoid precision issues. Then add $$$\displaystyle\left\lfloor\frac {max} {10^4} \right\rfloor - \left\lceil\frac {min} {10^4} \right\rceil + 1$$$ to the answer.
One must also be careful with the divisions, as the behavior of the /
operator may differ depending on the sign of the dividend. (In C++ and Java/Kotlin, it truncates, i.e., rounds toward zero, instead of finding the floor consistently.)
Time complexity: $$$O(\lceil R \rceil)$$$ or $$$O(\lceil R \rceil \log \lceil R \rceil)$$$
E – Come Back Quickly
Construct the weighted directed graph and run Dijkstra's algorithm from each node. However we have to deal with the fact that the goal node is the same as the source node. There are several ways:
- Set the cost of the source node to $$$\infty$$$ and prepopulate the priority queue with the nodes directly reachable from the source
- Create a new fictional node $$$n+1$$$ to use as the goal node. Redirect all back-to-source edges there.
- First precalculate the cheapest edge from each node to the source node (or $$$\infty$$$ if there are none). Run Dijkstra as normal, then add the costs and find the minimum.
Time complexity: $$$O(N (N+M) \log (N+M))$$$
F – GCD or MIN
Observe that a value $$$x$$$ could be the final value iff $$$x \leq \min A$$$ AND $$$x$$$ is the gcd of some non-empty subset of $$$A$$$.
For the latter condition to hold, $$$x$$$ must be a divisor of at least one value $$$A_i$$$. Also, if $$$[A_a, A_b, ..., A_c]$$$ are all the values of $$$A$$$ divisible by $$$x$$$, their collective gcd must be equal to $$$x$$$.
Thus we can iterate through the divisors of each $$$A_i$$$ and maintain a hashmap, mapping a divisor to the collective gcd of its multiples in $$$A$$$, then count the number of divisors that satisfy.
Time complexity: $$$O(N (\sqrt M + D \log M))$$$, where $$$M = \max A$$$ and $$$D$$$ is the maximum number of divisors for a value $$$A_i$$$, which can be considered roughly $$$O(M^{1/3})$$$.