Codeforces Round #808 (Div. 1)

　A一完で終了。Aはまあまあ早かったのだが。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #808 (Div. 1) A一完です。
A 後ろから見る
B 飛ばした。sum(a_n)の制約が効くんだと思うんだけど
C まずMSTを取って、そこに入らないedge x-yについてxとyの間にあるような頂点はダメ。また、xの正しい行き先よりyが小さいなら、x側の頂点はダメ。だと思うんだけど実装できない！

— titia (@titia_til) July 16, 2022

B. Difference Array

　解法ツイートを見てAC。

　sum(a_n)に関する制約があるのが怪しい。それを利用できないか考える。

　実際に操作をしてみると、すぐ、大半の要素が0になるのは分かる。ので、0の個数を管理して、他は愚直に操作すればOK。

・大半が0になること

・こういう問題では上手い方法はなくて、基本的には真面目に操作を行うしかなさそうなこと

　には気付いていたのに、解法へたどりつかなかったのは良くない。ただ、解法の鍵となる部分は分かっていたので、それ以上反省するのも難しい……。

C. DFS Trees

　解説AC。

　まず、ツイートした解法は間違っていました。問題で与えられたアルゴリズムを勘違いしていました（重みではなく、indexの小さい方からdfsするかと思っていた）。

　これを踏まえると、「MSTに入らないedge x-yについて、xとyの間にあるような頂点はダメ」だけでOK。これをどう実装するかが問題。

　これは、木上のimos法で解ける、という解法ツイートを見て、以下のようにできると分かりました。子孫全てにある値を足す、というのをimos法を使って処理しています。

・頂点xとyのLCAがxでもyでもないとき、xの子孫、およびyの子孫に+1する。

・頂点xとyのLCAがxのとき、yの子孫に+1、xの子でyの先祖であるような頂点kの子孫に-1する。頂点kはダブリングを使えば求まる。

　一つ目の方法では、答え(findMST(i)=1となる)の候補となる頂点に+1しており、二つ目の方法では、答えにならない頂点に-1しています。ので、全て処理した後、値がmaxと一致している頂点たちがこの答えになります。