Блог пользователя atcoder_official

Автор atcoder_official, история, 2 месяца назад, По-английски

We will hold JIJ Programming Contest 2026(AtCoder Beginner Contest 476).

We are looking forward to your participation!

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

CSP-J1/S1 will be held tomorrow. I wish all Chinese OIers like me good luck and hope we all advance to the next round! All in all, wish everyone rp++ !!! (ps:I'll join this ABC tomorrow.)

»
2 месяца назад, скрыть # |
← Rev. 4  
Проголосовать: нравится -22 Проголосовать: не нравится

Well, it seems that the point gap between F and G is very large. It means that G may be more difficult (this is relative, which means that it will be more difficult than the previous times)

UPD: It turns out that problem G is still easy

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Please don't discuss irrelevant content.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

it's my first time joining abc=)

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

RP++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

»
2 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

hope it is not shit

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -23 Проголосовать: не нравится

我超威,这题太难了,

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Maybe E is easier than D???

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My first E!

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

A-E too easy.

F involves 2D prefix sums but implementation is really hard :(

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

fuckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk !!! if there's 2 minutes more,I will AC D !!!

»
2 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Easiest E I've ever seen. Tho I couldn't solve D

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

flipping messed it up... i took way to long to solve such an easy C, and then no time for even D. There is always a next time though

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How G?

  • »
    »
    2 месяца назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Editorial mentions an inequality which I didn't know, I have another solution with dp.

    $$$hbit(mask)$$$ is highest bit in $$$mask$$$ in 0-indexation ($$$-1$$$ if $$$mask = 0$$$)

    We search for the longest non-increasing subsequence in $$$a_L, \ldots, a_R$$$, where $$$a_i = popcnt(i)$$$. Let's go from higher bits to lower. While $$$hbit(L) = hbit(R)$$$ we can just remove the bit. After that let $$$h = hbit(R)$$$. We split the interval into parts $$$[L, 2^h - 1]$$$ and $$$[2^h, R]$$$ and try to merge optimal subsequence from subsequences in these intervals. From the left interval we're only interested in the value of the last element, and from the right interval — only in the first value. Notice also, that the first $$$h$$$ bits in $$$2^h - 1$$$ are on and are off in $$$2^h$$$.

    This leads to following dynamics: $$$suf[k][e]$$$ — length of the longest non-increasing subsequence on the interval $$$[L_k, 2^k - 1]$$$ with the last value being at least $$$e$$$. ($$$L_k$$$ means the first $$$k$$$ bits of $$$L$$$), and $$$pref[k][s]$$$ — length on the interval $$$[0, R_k]$$$ with the first value at most $$$s$$$. Answer is $$$\max_{mid} suf[h][mid] + pref[h][mid - 1]$$$. This $$$-1$$$ comes from the bit $$$h$$$ that is on in the second interval.

    To find $$$suf[k][e]$$$ we will further split the interval by the highest bit. If $$$k$$$-th bit is on in $$$L$$$, then $$$suf[k][e] = suf[k - 1][e - 1]$$$, otherwise the two intervals are $$$[L, 2^{k-1} - 1]$$$ and $$$[2^{k-1}, 2^k - 1]$$$. If we switch bit $$$k-1$$$ off, then the interval becomes $$$[0, 2^{k-1} - 1]$$$, which is good since it doesn't depend on $$$L$$$ and $$$R$$$ at all, which leads to one more dynamic that will be precalced — $$$dp[k][s][e]$$$ — length on the interval $$$[0, 2^k]$$$ with start at most $$$s$$$ and end at least $$$e$$$.

    All of these dps have similar transitions that look as follows:

    $$$dp[k][s][e] = \max_{mid} dp[k - 1][s][mid] + dp[k - 1][mid - 1][\max(0, e - 1)]$$$

    $$$suf[k][e] = \max_{mid} suf[k - 1][mid] + dp[k - 1][mid - 1][\max(0, e - 1)]$$$

    $$$pref[k][s] = \max_{mid} dp[k - 1][s][mid] + pref[k - 1][mid - 1]$$$.

    Let $$$K = 60$$$. $$$dp$$$ is calculated in $$$O(K^4)$$$, $$$suf$$$ and $$$pref$$$ are calculated in $$$O(K^3)$$$, so we get $$$O(\log^3 R)$$$ per testcase, that passes because of good constant factor.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I solved E using segment tree.

My sub

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

I hope AtCoder can ban all the AI players. The gap between me and 1 Dan is approximately like this.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think only D and G is valuable.Besides,F is a bad problem which requires few thinking but with a lot coding complexity.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When will the Rating Changes happen?

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It's my first time to solve all the problems!

»
6 недель назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

D was a nice problem.