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行目)