AtCoder Regular Contest 106 振り返り

結果

3完40分+1ペナ。パフォ1757でした。

Dが解けなかったのがかなり悔しいです。

A	B	C	D	E	F
2:02	11:03	40:36(1)	(2)	-	-

各頂点が値を持っていて、辺で繋がっている頂点に値を1渡すor1もらう操作を繰り返す。初期状態Aから状態Bにできるか答えよ。

各連結成分で値の和が等しければOK。UnionFindに変な改造を施して値の和を管理できるようにした。

構築問題。区間スケジューリングの正しい解法と嘘解法で答えの差がちょうどMになるものを答える。

高橋くんの方法が区間スケジューリングの最適解だと気づけば、M<0にならないことがわかる。

うーん、悔しい。二項展開したあたりでかなり近い式は出ていたのですが、最初に複雑な解き方を選んだために途中で値が狂ってしまった。

「重複を許して%%(i, j)%%についての総和 → 2×(重複のない%%(i, j)%%のペアについての総和) + %%(i, i)%%についての総和」という言い換えがすぐに浮かべばもう少しシンプルに考察を進められた気がします。

実力不足がよく表れた感じです。

追記→2で割る操作をして壊れていただけだった。逆元を掛ける。だいじ。