ARC108 感想
653rd/4237 でパフォ1701
ARC108 の感想です
前回大きくレート上げたからか思ってたよりレート上がらなくてちょい辛い
A.Sum and Product
問題文に書いてあるとおり $P$ の約数を見ればよし $O(\sqrt P)$
B.Abbreviate Fox
めっちゃこれに似てる
操作の順番が答えに影響しないのでfoxが出てくるたびに貪欲に取り除いていって良い
vectorでも使ってスタックでシミュレートしてあげれば $O(N)$
C.Keep Graph Connected
まず、サンプルに “No” のケースが無いので “No” は無いとして考える
頂点につけた番号が $C_i$ と同じかどうかのbool値を割り当てると二部グラフに似てる
どうせvalidな割り当てのbool値を反転してもvalidな割り当てが存在してるので頂点$1$からDFSしながら適当に番号を振っていけば良い
証明: AC
順位表見てるとなんか通されすぎてる気がするし正当性もちょっと怪しいけどまあ正しそうだしでダメ元で適当にコード書いて出したら通って草って感じだった
D以降
Dで16通りくらい場合分けしてたんだけどよくわからなくて飛ばす
Eもよくわからん トップ層も解けてないしこんなん解けるか！って言って飛ばす
Fは割と希望が見える とりあえず木の直径を軸に考えるべきですねってのはわかる maxの距離を取る対のうち片方は葉にあるだろうなってところで思考が止まっておしまい