今日の競プロ(2020/4/9)

JOI 3問

$1,\ldots,n$ を2番目に大きい約数で分類する。 $n=10$ のとき、

$1 : 1, 2, 3, 5, 7$

$2 : 4$

$3 : 6, 9$

$4 : 8$

$5 : 10$

これを上から順番に使っていく。例えば $k=7$ なら、 $M=\{1,2,3,5,7,4,6\}$ とすることでsmallest imperfectionは $3$ となり、 $I_7=3$ 。

$n$ 頂点のグラフを考え、チーム $i$ がチーム $j$ に勝ったという情報が与えられた（つまり、チーム $i$ の順位がチーム $j$ の順位より高い）とき頂点 $i$ から頂点 $j$ に辺をはる。これはDAGになるので、トポロジカルソートする。

総重量を $1$ としたときの各錘の重さを分数で求める。全ての錘の重さが正整数になるような総重量の最小値は、錘の重さの分母のLCM。

明日25:35までこどふぉで明後日10:00からGCJ　遅寝早起き

gyouzasushi’s diary