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 字状の配置が生まれることもあります。

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

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

2部グラフを用いた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行目)