精進メモ 2021/07/05~ - ツバサの備忘録

もうすぐ夏休みですね。コンテスト中の問題を間違えてアップしないよう、週末にアップするようにします。

ランレングス圧縮をして、それぞれの長さ $L$ に対し、 $L(L+1)/2$ を引いていけばOKです。

3重ループを素直に書いたら終わりです。枝刈り。

桁ごとに見て、ビット全探索です。

二分探索 + ワーシャルフロイドです。頭がこんがらがり、1ペナしました。

鳩ノ巣原理です。全探索をして、見つかった時点で探索を打ち切ります。
最近みたのでさすがに大丈夫でした。

しゃくとり + 累積和DPです。
$K$ 以下の転倒数になるようしゃくとりを行い、遷移できる箇所に遷移させます。いもす + 累積和です。

7点。きたまさ、NTT、FPSをぐっと睨みましたがイマイチわからずです(NTT以外は使ったことないので難しいですね)
DPを頑張って高速化すると7点が取れます。自分の解法の計算量はわかっていません。
種類が $\sqrt{K}$ に落ちるのが面白いですね。

E,Fを平行でやったら爆死しました。どっちも自力で通せたので、どちらかに絞るべきでしたね(最近こういうの多くて、Fへ行く勇気が必要なのでつらいです)

一瞬かたまりました。
ソートして、 $C_{i} - i$ をかければいいです。
ところで、0とのmaxを取り忘れていますがこれは正しいのでしょうか…？

偶奇だけであれば一回DFSすればいいことを完全に忘れていました。
LCAをぺたり。

グラフの頂点数と辺数はある程度抑えられるので、後ろからDPすれば良いです。
いろいろ直したせいでコンテスト中にどこにバグがあったのかはわかりません(考察自体は最初から合っていました)…
おそらく、変な頂点を複数回見ていた？のかもしれません。

前から素直にDPすればいいです。
一つ前の要素が大きい場合と小さい場合(どちらも等号含む)で、それぞれ似たような遷移をします。累積和を取りながら数えていけば良いです。