2019-01-05から1日間の記事一覧

AtCoder Grand Contest 028: C - Min Cost Cycle

https://atcoder.jp/contests/agc028/tasks/agc028_c 問題概要 N頂点の有向グラフがあり、各頂点iは2つの値Ai, Biを持っている。このグラフはすべての点対x, yに対して辺x->yが存在し、その重みはmin(Ax, By)である。グラフのすべての頂点をちょうど1回ずつ…

Codeforces Hello 2019: D. Makoto and a Blackboard

https://codeforces.com/contest/1097/problem/D 問題概要 整数N, Kが与えられる。Nの約数のうちひとつを等確率で選び、それでNを割る、という操作をK回繰り返すとき、最終的なNの値の期待値を求めよ。 N <= 1015 K <= 104 解法 Nの約数の数は最大ケースで30…