こんばんは。健康診断に行ったら無限人の人間がいて精神が崩壊したとーです。
ABC103D
横一列に並んだ島のi,i+1番目に橋が架かっていて、与えられた入力の島を行き来できなくするのに落とす必要のある橋の最小本数は？という問題
右側の方に番号の大きい島が書かれているので、それを昇順にソートして、その島の左側の橋が落ちていれば何もしない、落ちていなければ落とす、を繰り返すのが最適なので、これをやるだけ かしこいなあ
ABC097D
ある決まった二組の数字だけが入れ替えられる状況下で、左から数えたその番号の場所iとその番号p_iが一致するようにすると最大いくつ一致させられるか、という問題
行き来できる二組の間に辺を張ったグラフを考える その中で、一致させたい番号と場所の番号が結ばれていれば入れ替えによって一致させられる
例えば、
p_i = 5 3 1 4 2
i = 1 2 3 4 5
で、1,3番目と4,5番目が入れ替え可能だとすると、グラフは1-3,4-5,2となる(ハイフンは連結していることを表す）
そこで、グラフ上で、p_iとiが同じ木の上にあるかどうかを見ると、
P_i = 1,4
i = 3,4
の二組だけが同じ木の上にあると分かる（p_i == iは同じものとみなす）
このような(p_i,i)の組を数えればよい UF木などで数えられる
