We will hold AtCoder Beginner Contest 438.
- Contest URL: https://atcoder.jp/contests/abc438
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20251227T2100&p1=248
- Duration: 100 minutes
- Writer: cn449, sounansya
- Tester: sheyasutaka, math957963
- Rated range: ~ 1999
- The point values: 100-200-300-400-475-525-575
We are looking forward to your participation!
Good luck everyone!
I hope my rank will within 400.
Good luck!
hope that i can solve 5 or 6 problems
Happy New Year!
The last Atcoder Beginner Contest in this Year!
Hope Perfect Ending!
:)
I have a terrible ending. so sad.
me,too.I only solve 4 problems
I have a terrible ending too.(only 5)
hope we have a lucky beginning (2026)
yep!
I said today is 2026/1/-4.
Happy New Year!
bro, today is 27 ,there are fours days left to say this after
Due to technical reasons, Atcoder is unable to host any more ABC events this year. Please cherish this final ABC event(:
Funny(
Oh, that's a joke in luogu.org
You mean luogu.com right?
good luck
Happy New Year!
Happy New Year!
How to slove D?
《slove》
Convert the arrays into their prefix sums.
You need to maximize:
Here
C[N]is constant. So you just need to maximize:This can be done using a sweep while maintaining the maximum of either one of the terms.
dp is easier one.
dp [i][k] is the answer from 1,2,3,...,i and if k==0 our i index is on A array if k==1
our i index is on B array otherwise our i index is on C array.
transitions: dp[i][0]=dp[i-1][0]+a[i] dp[i][1]=min(dp[i-1][1]+b[i],dp[i-1][0]+b[i]) dp[i][2]=min(dp[i-1][2]+c[i],dp[i-1][1]+c[i])
our answer is dp[n][2] because last index must be on the C array
I have another DP approach where the problem can be reduced to a standard maximum-sum grid DP.
Consider the three arrays as a 3×N matrix.
Notice that from (r,c), the only allowed moves are (r,c+1) and (r+1,c+1) We can compute this easily , since there is only 3 rows and N col. in o(N)
G is cool. I see number theory problems like that I press upvote.
My wi-fi is bad,so I just finished 4.
:(
In the offcial editorial of problem F, the situation where vertex $$$k$$$ is on the path from $$$x_k$$$ to $$$y_k$$$ is not mentioned (in this case, $$$(x_k,y_k)=(x_{k-1},y_{k-1})$$$).
actually, we can solve F with a O(n) time complexity algorithm. code's here
I only solve 4 problems in the last ABC round of 2025. =(
For problem D,
a[1]+a[2]+...+a[x]+b[x+1]+b[x+2]+...+b[y] can be transformed into a[1]+a[2]+...+a[x]+b[x+1]+b[x+2]+...+b[y]+(b[1]+b[2]+...+b[x])-(b[1]+b[2]+...+b[x]) =(a[1]-b[1]+a[2]-b[2]+...+a[x]-b[x])+(b[1]+b[2]+...+b[y]) =prefix-sum-of-(a[x]-b[x])+prefix-sum-of-b[y].
So, we can enumerate y, and find the maximum value of prefix-sum-of-(a[x]-b[x]), and plus the suffix-sum-of-c[y+1]
Problem E is again the famous binary-lift trick, which has been used in ABC quite a lot.
For problem F, to get the number of pairs which has a value of x, the nodes 0,1,...,x-1 must stay as a "line". A simple dfs is enough to keep updating this "line". (if you would like to send me a message to discuss the problems, both English and Chinese are ok)
well i hate F and my rubbish coding ability. It only left me 8 minutes to solve G and i failed to do that with no doubt...But still Happy New year guys!!!
Problem F is the same as 1527D
At first glance, problem E looked REALLY similar to an old problem from COCI. I'm not sure from which contest but it was here:
https://evaluator.hsin.hr/
Yes, it's pretty similar to the task "Krugomet" (p2) from the first contest of the 25/26 season.
Yea, that one!