ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

CODE FESTIVAL 2016 Grand Final A - 1D Matching

お題箱より。

A - 1D Matching

解法

まずはケーブルの長さの合計が最小になる条件を考えましょう。

座標点を数直線上に並べて、小さい方(左)から見ていくことを考えましょう。このとき各点について「保留して、それより右側の座標点と繋ぐことにする」か「保留している左側の座標点と繋いでペアを確定させる」かを決めることになります。

直感的には、保留数が多くなってたくさんケーブルを伸ばすと損なので、できるだけ組めるペアは組んでしまって保留数を減らしたい気持ちになります。これをちゃんと考えましょう。

実際、「保留している点と繋げるにも関わらずあえて繋がない」という選択を1度でも行ってしまうと、それは必ず最適でない繋ぎ方になります。これは具体的には「保留しているパソコンが左側にあって、今見ている点が電源なのに、その電源を保留する」こと、あるいはその逆です。その理由は、以下のように繋ぎ変えることでケーブルの長さ合計をより小さくできるからです。

f:id:betrue12:20191211235733p:plain

つまり保留パソコンがある時に電源を見たり、保留電源がある時にパソコンを見た時には、必ず保留しているもののうちいずれかと繋ぐ必要があります。そして逆に、このルールを守ってペアを作っていくならば必ず最適な繋ぎ方になります。これを証明します。

隣り合う座標点の間の区間を通るケーブルの本数について考えてみましょう。座標点をソートした順に  x_{1}, ..., x_{2N} と書くことにして、 x_{i} x_{i+1} の間の区間を通るケーブルの本数を考えます。 x_{1}, ..., x_{i} の内訳がパソコン  p_{i} 個、電源  q_{i} 個あった場合、この区間には少なくとも  |p_{i} - q_{i}| 本のケーブルが必要です。これが「下界」、つまりこれ未満の本数には絶対にできないという値です。

f:id:betrue12:20191212000117p:plain

そして先ほど書いたような手順で繋ぎ方を決めると、必ず全ての区間についてケーブルの本数が  |p_{i} - q_{i}| 本になります。各  i について、 x_{1}, ..., x_{i} の内部で繋げるペアは全て繋いだ状態になり、余った  |p_{i} - q_{i}| 個の座標点からのケーブルだけが  i+1 側に出るからです。よって先ほどの手順で決めた繋ぎ方は全ての区間で下界の本数を実現しているため、長さ合計が最小の繋ぎ方になります。

あとはこのような手順で作られる繋ぎ方の場合の数を求めましょう。ペアを確定させるタイミングで保留点の中から1つ繋ぐ相手を選ぶので、このとき選ぶ相手によって繋ぎ方が変わります。保留点の個数を管理しながら座標点を小さい順に見ていって、ペアを確定させる時の保留点の個数を全て掛け合わせたものが答えになります。

ACコード

Submission #8914618 - CODE FESTIVAL 2016 Grand Final(Parallel)