2019年6月22日に行われたAtCoder Beginner Contest 131のPython3 での実装例です
A - Security
使用テクニック: メモ化、for
B - Bounding
使用テクニック: メモ化 , for
for
ループを回して全てのリンゴを使った際の味の総和を求めます(total
)。この際、味の絶対値が最も小さいものをs
に覚えておき、total
から s
を引けば答えを求めることができます。
C - Anti-Division
使用テクニック: 包除原理 、ユークリッドの互除法 、最小公倍数
方針
以上
以下の整数から、
の倍数と
の倍数を引いて残った整数の個数が求める答えとなります。
包除原理 に従って、 以上
以下の整数の個数から、
の倍数の個数と
の倍数の個数を引き、2回引かれている
と
の最小公倍数の倍数を足しなおします。
と
の 最小公倍数 は、
と
の積を
と
の 最大公約数 で割ることで求めることができます。最大公約数は、ユークリッドの互除法 を用いることで求めることができます。
実装
D - Megalomania
使用テクニック: sort
方針
締め切りの早い順に仕事をソートして、仕事にかかる時間 足していき、最後まで
の累積和が
以下であれば全ての仕事を終わらせることができます。
実装
E - Friendships
使用テクニック: スター(グラフ)
方針
まず、 頂点の無向グラフにおいて、最短距離が
である頂点対の最大値が
であることを示します。
証明
頂点から
つの頂点を選ぶ組合せの数は
です。また、全ての頂点が連結されるためには少なくとも
本の辺が張られている必要があり、この
組の頂点対の最短距離は
です。 よって次の計算から、最短距離が
以上である頂点対の数は最大でも
となります。
また、 つの頂点と
個の 葉 のみからなるグラフである スター
を考えると、全ての 葉 間の最短距離が
であるため、最短距離が
である頂点対の個数が
個となるグラフが存在することを示せました。
よって、 頂点の無向グラフにおける最短距離が
である頂点対の最大値は
であることが証明できました。
さらに、スターの 葉 同士を結ぶ辺を 本張ることで最短距離が
である頂点対を
個減らすことができ、全ての 葉 間に辺を貼った 完全グラフ
では最短距離が
である頂点対の個数は
となります(全ての頂点対の最短距離が
)。
以上より、最短距離が である頂点対の個数が
個以下であるグラフであれば構築できることが示せました。
実装
入力 が
よりも大きい場合は、
を出力します。(7-10 行目)
そうでなければ、頂点 に残りの頂点を接続した スター グラフを作成し (12行目)、最短距離が
である頂点対の個数が
と等しくなるまで、葉 間に辺を貼っていきます。 (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次元平面上の点 はノード
と
を結ぶ辺として表現することが出来ます。 そのため、入力として与えられる
個の点を同様に2部グラフの辺として表現すると、いくつかの連結された2部グラフが得られます。
この時、格子状の配置は 完全2部グラフ で表現されます。よって、各連結された2部グラフにおいて、完全2部グラフを作成するための辺の数を数え上げ、はじめの辺の数を引けば答えを求めることが出来ます。
完全2部グラフを作成するための辺の数は、連結された2部グラフのX座標のノード数 とY座標 のノード数
の積で求めることが出来ます。
実装 (DFS)
- X座標、Y座標の範囲が
以上
以下であるため、list
bgraph
を作成してから
番目までを X座標用のノードとし、
番目以降をY座標用ノードとすることで2部グラフを表現することが出来ます。
bgraph[i]
が番目のノードが接続しているノードを保管する list となっています。 (8-14 行目)
- DFS を用いて連結しているノードを探索し、各2部グラフごとに完全2部グラフとした際の辺の数を数え上げます。 (16-32 行目)
実装 (Union-Find)
- どのノードがどの連結2部グラフに属しているかを調べる際に、DFS ではなく Union-Find を用いることもできます。
- 各ノードの root ノードを調べ、同じ root ノードに属している場合は連結しています。
- よって、各 root ノードごとに X座標のノード数と Y座標のノードを数をカウントすることで答えを求めることが出来ます。 (44-51行目)