mayoko’s diary

プロコンとかいろいろ。

2016-02-11から1日間の記事一覧

Educational Codeforces Round 3 E. Minimum spanning tree for each edge

問題 codeforces.com 解法 まず普通に MST を作ります。で, その木に辺 (u, v) を追加したと考えると, 閉路が出来ます。閉路のいずれかの辺を取り除くと再び木になるので, 閉路の中からコストが最大の辺を取り除けば良いです。最大の辺はどうやって取り除け…

Educational Codeforces Round 3 D. Gadgets for dollars and pounds

問題 codeforces.com 解法 冷静に考えるとちょっと前準備をしてから答えに対して二分探索すれば良かったと思うんですが, 答えを 1 つずつ足していって, それが条件を満たすかを 3 分探索で調べる, という方法で AC しました。ある日程 ans について, i あと…

ラグランジュ補間について

なんとなくメモ。 ラグランジュ補間のアイデア に関する N 次多項式 を, というヒントから表したいです。この時, とすれば, と表せることに注目します。 このように書くとハッピーなのは, とすると, を満たす について, が成り立つことです。このことから, …