CODE FESTIVAL 2016 Grand Final A 1D Matching
問題概要
一次元の世界に 個のパソコンと
個の電源がある。
番目のパソコンの座標は
であり、
番目の電源の座標は
である。
それぞれの電源は一つのパソコンにのみつなぐことができるとき、ケーブルの長さの合計を最小化する場合の数を で割ったあまりを答えよ。
制約
解法
前から順に計算していくことができる。が、証明が難しいので他の人のブログを参考にしてください（最悪）
CODE FESTIVAL 2016 Grand Final: A - 1D Matching · うさぎ小屋
CODE FESTIVAL 2016 Grand Final A - 1D Matching - ferinの競プロ帳
未割り当てのパソコンが 個の状態で電源を見ているとき、その電源につなぐことができるパソコンの数は
個ある。よって答えに
を掛けて、未割り当てのパソコンの数を1減らす。また、電源を見ているときに、未割り当てのパソコンがひとつもない場合は、未割り当ての電源の数を1増やす。（この操作はパソコンと電源が入れ替わっても同じ）
Submission #2065237 - CODE FESTIVAL 2016 Grand Final(Parallel)
