Python で解く AtCoder ABC131

2019年6月22日に行われたAtCoder Beginner Contest 131のPython3 での実装例です

A - Security

使用テクニック： メモ化、for

B - Bounding

使用テクニック： メモ化 , for

for ループを回して全てのリンゴを使った際の味の総和を求めます(total)。この際、味の絶対値が最も小さいものをs に覚えておき、total から s を引けば答えを求めることができます。

C - Anti-Division

使用テクニック： 包除原理、ユークリッドの互除法、最小公倍数

方針

$A$ 以上 $B$ 以下の整数から、 $C$ の倍数と $D$ の倍数を引いて残った整数の個数が求める答えとなります。

包除原理に従って、 $A$ 以上 $B$ 以下の整数の個数から、 $C$ の倍数の個数と $D$ の倍数の個数を引き、2回引かれている $C$ と $D$ の最小公倍数の倍数を足しなおします。

$C$ と $D$ の最小公倍数は、 $C$ と $D$ の積を $C$ と $D$ の最大公約数で割ることで求めることができます。最大公約数は、ユークリッドの互除法を用いることで求めることができます。

　実装

D - Megalomania

使用テクニック： sort

方針

締め切りの早い順に仕事をソートして、仕事にかかる時間 $A _ i$ 足していき、最後まで $A _ i$ の累積和が $B _ i$ 以下であれば全ての仕事を終わらせることができます。

実装

E - Friendships

使用テクニック： スター（グラフ）

方針

まず、 $N$ 頂点の無向グラフにおいて、最短距離が $2$ である頂点対の最大値が ${} _ {N-1}\mathrm{C} _ 2$ であることを示します。

証明
$N$ 頂点から $2$ つの頂点を選ぶ組合せの数は ${} _ N\mathrm{C} _ 2$ です。また、全ての頂点が連結されるためには少なくとも $N-1$ 本の辺が張られている必要があり、この $N-1$ 組の頂点対の最短距離は $1$ です。よって次の計算から、最短距離が $2$ 以上である頂点対の数は最大でも ${} _ {N-1}\mathrm{C} _ 2$ となります。

${} _ N\mathrm{C} _ 2 - (N-1) = \frac{N (N-1)}{2} - \frac{2(N-1)}{2} = \frac{(N-1) (N-2)}{2} = {} _ {N-1}\mathrm{C} _ 2$

また、 $1$ つの頂点と $N-1$ 個の葉のみからなるグラフであるスター $S _ N$ を考えると、全ての葉間の最短距離が $2$ であるため、最短距離が $2$ である頂点対の個数が ${} _ {N-1}\mathrm{C} _ 2$ 個となるグラフが存在することを示せました。

よって、 $N$ 頂点の無向グラフにおける最短距離が $2$ である頂点対の最大値は ${} _ {N-1}\mathrm{C} _ 2$ であることが証明できました。

さらに、スターの葉同士を結ぶ辺を $1$ 本張ることで最短距離が $2$ である頂点対を $1$ 個減らすことができ、全ての葉間に辺を貼った完全グラフ $K _ N$ では最短距離が $2$ である頂点対の個数は $0$ となります（全ての頂点対の最短距離が $1$ ）。

以上より、最短距離が $2$ である頂点対の個数が ${} _ {N-1}\mathrm{C} _ 2$ 個以下であるグラフであれば構築できることが示せました。

実装

入力 $K$ が ${} _ {N-1}\mathrm{C} _ 2 = \frac{{N-1}(N-2)}{2}$ よりも大きい場合は、 $-1$ を出力します。(7-10 行目)

そうでなければ、頂点 $1$ に残りの頂点を接続した スター グラフを作成し (12行目)、最短距離が $2$ である頂点対の個数が $K$ と等しくなるまで、葉間に辺を貼っていきます。 (13-18 行目)

F - Minimum Bounding Box

使用テクニック： 2部グラフ、深さ優先探索（depth-first search: DFS）、Union-Find

方針

2次元平面上に 3点が L 字状に配置されているとき、新たな点を追加することが出来、追加できる点の最大数を答える問題です。また、追加して点によって新たな L 字状の配置が生まれることもあります。

簡単な実験から、追加できる全ての点を追加し終わった後の２次元平面は、元から配置されていた全ての点の X軸とY軸の交点が埋まった格子状の配置となることが確認できます。

よって、最終的に形成される格子状配置の交点の数から、元の点の数を引くことで答えを求めることが出来ます。

2部グラフを用いた２次元平面の表現

X座標とY座標をノードとして持つ 2部グラフを考えます。この時、2次元平面上の点 $(x _ i, y _ i)$ はノード $x _ i$ と $y _ i$ を結ぶ辺として表現することが出来ます。そのため、入力として与えられる $N$ 個の点を同様に2部グラフの辺として表現すると、いくつかの連結された2部グラフが得られます。

この時、格子状の配置は完全2部グラフ $K _ {m, n}$ で表現されます。よって、各連結された2部グラフにおいて、完全2部グラフを作成するための辺の数を数え上げ、はじめの辺の数を引けば答えを求めることが出来ます。

完全2部グラフを作成するための辺の数は、連結された2部グラフのX座標のノード数 $m$ とY座標のノード数 $n$ の積で求めることが出来ます。

実装 (DFS)

X座標、Y座標の範囲が $1$ 以上 $10 ^ 5$ 以下であるため、list bgraph を作成して $0$ から $10 ^ 5 - 1$ 番目までを X座標用のノードとし、 $10 ^ 5$ 番目以降をY座標用ノードとすることで2部グラフを表現することが出来ます。bgraph[i] が $i$ 番目のノードが接続しているノードを保管する list となっています。 (8-14 行目)
DFS を用いて連結しているノードを探索し、各2部グラフごとに完全2部グラフとした際の辺の数を数え上げます。 (16-32 行目)

実装 (Union-Find)

どのノードがどの連結2部グラフに属しているかを調べる際に、DFS ではなく Union-Find を用いることもできます。
各ノードの root ノードを調べ、同じ root ノードに属している場合は連結しています。
よって、各 root ノードごとに X座標のノード数と Y座標のノードを数をカウントすることで答えを求めることが出来ます。 (44-51行目)