コンテスト全体の解説 by evima
HintsBelow are some brief hints for each problem. Use them for guidance if you get stuck.
A - ARC Arc
Hint 1
It seems good to try concatenating copies of ARCRARCR....
Hint 2
Consider the cases \(N=4\) or \(N=8\); you should be able to see that it is simple when \(N\) is a multiple of \(4\).
Hint 3
What about the case when \(N\) is odd? It appears difficult when all elements of \(A\) are \(0\).
Hint 4
Try thinking about the string ARCRARC for \(N=7\) or ARCRARCRA for \(N=9\).
Hint 5
Remember that the string is cyclic, so you may shift \(A\).
Hint 6
Consider the case when \(N\) modulo \(4\) is \(2\). It seems difficult when all elements of \(A\) are \(0\) or when \(A\) contains only one \(1\).
Hint 7
In the case \(N\) modulo \(4\) is \(2\), you should be able to construct a string that makes all but two positions become \(1\). Examine the characteristics of the positions that cannot be made \(1\).
B - Fennec VS. Snuke
Hint 1
Since the indices in \(S\) do not need to distinguish between different terms of \(A\), consider setting \(X=\sum_{i\in S}A_i\).
Hint 2
Notice that if a winning strategy for a player exists when \(X=0\), then one also exists when \(X=2\). Why is that?
Hint 3
If the opponent reduces \(X\) in parts that are unrelated to the winning strategy for \(X=0\), you can also reduce \(X\) to keep the overall balance and reduce it by \(2\).
Hint 4
From the above, you may assume that \(X=0\) or \(X=1\).
Hint 5
It turns out that for the elements of \(A\), considering only their parity is sufficient. At this point, experimentation might help.
C - Range Sums 2
Hint 1
It should be easier to identify an index \(i\) for which \(P_i=1\) or \(P_i=N\).
Hint 2
Given a set of points on a line, the farthest point from a given point is one of the two endpoints. What does this imply?
Hint 3
Set \(s\) arbitrarily and send queries for all \(t\). Then, when the returned value is the largest, it holds that \(P_t=1\) or \(P_t=N\). Assume \(P_t=1\).
Hint 4
From an endpoint, the order of distances corresponds directly to the order of the points. Ignoring the constraint \(P_1<P_2\), it seems \(P\) can be determined.
Hint 5
Most of the elements of \(A\) can be determined by taking differences. Use any remaining queries to determine the remaining unknown elements of \(A\).
Hint 6
Consider the constraint \(P_1<P_2\). In the following two cases the query responses are identical. Why is that?
D - Fraction Line
Hint 1
Observe the characteristics of \(f\left(\dfrac{x}{y}\right)\).
Hint 2
It seems that you can consider each prime factor independently.
Hint 3
For each prime factor, a relatively simple DP should suffice to compute the answer.
Hint 4
Once you have computed the answer for each prime factor, you can combine them by taking the product.
E - Snuke’s Kyoto Trip
Hint 1
When every lattice point with \(0\leq x\leq W\) and \(0\leq y\leq H\) has a block and the starting point is \((0,0)\), compute the number of paths as quickly as possible.
Hint 2
If you find (or know) the correct formula in Hint 1, then by transforming that formula you should be able to obtain the number of paths for the case with all lattice points in \(0\leq x\leq W\) and \(0\leq y\leq H\).
Hint 3
Assuming we spend \(O(W+H)\) time on precomputation, it is not necessary to process each subsequent computation in \(O(1)\) time.
Hint 4
Examine all points along the boundary of the forbidden region, and count the paths that pass through the forbidden region appropriately.
投稿日時:
最終更新: