We will hold AtCoder Regular Contest 185.
- Contest URL: https://atcoder.jp/contests/arc185
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241013T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 5
- Writer: Nyaan
- Tester: maspy
- Rated range: 1200 ~ 2799
The point values will be 600-600-600-800-800.
We are looking forward to your participation!
600+600+600+800+800
it's so unusual
It seems like a speedrun. Anyway, gl&hf!
Speedrun Yes. BCDE are all easier than ARC184_B.
This is definitely not an intended solution for E.
Well, I actually managed to squeeze mine to 1.1s... (reduce $$$128^2$$$ to around $$$1200$$$ iterations per index)
Instead of doing it everytime, I cached in memory a simulation of doing this operation for all numbers from 1 to 100'000, and then reducing to $$$128 * 500000 + \sum_{n=1}^{100000} divs(n)^2$$$ from 1694ms to 338ms Link
I got a TLE on this :(
But I optimized my algorithm (not my constant) and got AC. Your code is easy to optimize.
A is way too easy for 600.
How did the question maker come up with this CDE question ?
WhyTF B==C
E is too easy for 800pts.
The problems seem to be pretty different from a "normal" ARC. I feel like C could just as well have been a late problem in an ABC, basically only needing to know a certain standard technique, and then doing some casework. D and E also had some kind of knowledge check inbuilt, but you didn't need to do much observations. I liked other ARC's more.
There's a solution of C slightly simpler than official: Let multisets S={Ai: Ai<=X/3}, T={Ai: Ai>X/3}, then Ai, Aj and Ak cannot all come from T, and if they all come from S then Ai=Aj=Ak=X/3 so we can check if number of occurences of x/3 is at least 3. So in other cases, there could be 1 number from S and 2 from T, or vice versa. For now on we only need to keep 2 occurences for each different numbers. For the first case (second case is similar), Let f(x)=((sum(j)(x^j))^2-sum(j)(x^(2*j)))/2, where j iterates among all elements of T, then f(x)[x^p] will be the number of ways to choose different Ai,Aj from T such that Ai+Aj=p, we can use FFT to calculate them, and find some p<=X/3 such that f(x)[x^(X-p)]>0. Because we only keep at most 2 occurences, each coefficient of f(x) is at most 1000000*2^2=4000000, so we can do FFT by modulo 998244353 safely.
Actually we can limit to one occurrence for each value. If a value is indeed used twice, i.e. $$$2a+b = x$$$, we can just enumerate all possible $$$a$$$ in $$$O(n)$$$
I think the E-questions in this game are easier than the previous ones in ARC. And how to solve C?