競プロ週記(2022/06/19)

6/14　Codeforces Round #799 (Div. 4)


全完した前回よりはむずかった。


A-Gの7完で、Hだけ解けず。


ADで違う問題を解いてしまい、Bはパッと見で分からずと、かなりタイムをロスった。最近文章読解力の無さを身に染みていて感じる。


Hは

f(l,r,x)=Σg(i, x)　※g(i, x)=((a[i]==x) ? 1 : -1)

の最大値みたいな問題に落ちるのだけど、実装に手間取って通せず。

座圧→RLE→Kadane's Algorithm（コンテスト中にググった）→復元を書いてコンテスト直後に通したけど、積極的に人の実装を盗んでスマートに書けるようにしていきたいところ。

 

6/18　ABC256

A-Eの5完。

 

C　どうせ枝刈り通るやろで9重ループ書いちゃった（照）9重ループでも27msなのね。想定解は4か所決めれば全部決まるってやつ。

E　なんか実装が大変な問題だったらしい。図を書いて睨むと最大全域森（？）みたいなのを作ればよいことがわかるので、クラスカル法の辺ソート順だけ変えたものを貼ってAC。

F　DをAの式で表した後、Dがセグ木に乗らねえかなあをしていた。立てた式を展開してa[i], i*a[i], i^2*a[i]をそれぞれセグ木に乗せるだけでよかったんだけど、展開するという発想が出なかった。黄diffついてるあたり、気づかないもんなのかなあ。

 

8問に増えたんだからA,Bは無、Cはdiff200くらいでいいんじゃねえかなあと思っているけど、なんかそこそこ難しいところで安定しているっぽい。

 

6/19　ARC142

B1完。

Aは問題文の意味がよくわからなかったので、Bから解く。

いつもの蚊取線香だなあと思って書いたけど落ちた。N奇数のときのど真ん中付近が悪さをしていることが分かったので、そこだけ変えたらAC。正当性は不明。

 

Aを解いても手遅れっぽかったのと、そもそも問題文の意味が分からなかったのでCを見た。（1、v)、(2、v)を聞いてから適当にやればよさそう。WA×2までいったが解説見たら本質部分が詰められていない雰囲気だった。これからupsolve。

 

3-4-5-8-9-10のコンテスト、かなりどうなんだという気がするけどレート（強さ）が正義の界隈なのでか、あんまり文句を言っている人は見ないなあ。実は詐称/逆詐称の問題があるのかと思ったけど、それも無かった。

3-4-5が早解きできればレートが上がるしそうすればいいのだけど、そういう問題ではなくないか？という気はする。

CのNが小さいケースも全然入っていなくて、かなりヤバコンテストだったということになるのだけれど、直後に開催された通称インドコンでコンテスト中に問題が消滅したらしい。

無料コンテンツだし、ちゃんと問題が表示されていて、ACになるべき提出でACが出るだけで有難い、くらいの心持ちでいるのがよいのかもしれない。

 

今週はやる気があったので、もすーんバチャ×1とセルフバチャ×1をやった。

水76→83(+7)

青49→52(+3)

黄10→11(+1)

Σ 534→563(+29)

やる気のある時にはやっていきたいね。