目次
AtCoder Beginner Contest 131 D,E,F 問題メモ
D - Megalomania
問題
- $N$ 件の仕事があり、$i$ 番目の仕事は $A_i$ 時間かかり、〆切は現在から $B_i$ 時間後
- 全ての仕事を〆切前に終わらせることができるか判定せよ
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i,B_i \le 10^9$
解法
BGM: Live-A-Live (SFC) - Megalomania [Boss Battle] - YouTube
どういう順に処理すればよいか考える。
何となく、〆切の早い方から優先的に手を付けた方がよさそう。そしてこれは考えればちゃんと正しい。
時刻0 B1 B2 B3
|---------- | ---------- | ---------- |
A1が A1+A2が A1+A2+A3が
この範囲内 この範囲内 この範囲内
である必要 である必要 である必要
〆切の早い順にソートして、（仕事の番号をその順で振り直したとして）
- $A_1 \le B_1$
- $A_1+A_2 \le B_2$
- $A_1+A_2+A_3 \le B_3$
- …
が全て成り立つか調べればよい。
import sys
from operator import itemgetter
def solve(tasks):
tasks.sort(key=itemgetter(1))
t = 0
for a, b in tasks:
t += a
if t > b:
return False
return True
n = int(input())
tasks = [tuple(map(int, line.split())) for line in sys.stdin]
print('Yes' if solve(tasks) else 'No')
なお、実際の仕事では完全に所要時間を見積もることはほぼ不可能で、いろいろと予想外の時間がかかるので、 そういうのの早期発見という意味ではなるべくマルチタスク、複数を並行に進めることも求められるのが悩ましい。
E - Friendships
問題
- 以下の条件を満たす $N$ 頂点の無向グラフを構成せよ
- グラフは単純かつ連結
- 各辺の距離は1
- 最短距離が2であるような頂点対 $(i, j)$ が、ちょうど $K$ 個存在する
- 構成できない場合は
'-1' を出力せよ - $2 \le N \le 100$
解法
まず、$K$ が少なすぎたり多すぎたりして、構成できない場合を考える。
少なすぎる方については、完全グラフを考えると全ての最短距離が1なので、$K=0$ でも構成できる。
多い方は、どういうのがペアの数を稼げるかというと、スターグラフ（1つの頂点に、残りの頂点が繋がったやつ）がよさそう。スター_(グラフ理論)
これが最大となる証明はパッと思いつかないので正しいと信じて（解説pdf参照）、この場合、中心以外の任意のペアが条件を満たすので、できるペア数は $\displaystyle \frac{(N-1)(N-2)}{2}$ となる。
$K$ がこれより大きいなら、-1を出力する。
それ以外の場合、中心以外の頂点のどれか2つの間に辺を追加すると、そのペアに関しては最短距離が1となり条件を満たさなくなるが、他の頂点には影響を及ぼさないので、綺麗にペア数を1だけ減らすことができる。
よって、まず頂点1を中心とするスターグラフを作り、それでできるペア数から、$K$ になるまで1本ずつ頂点2以降のペアの間に辺を追加すればよい。
def solve(n, k):
mx = (n - 1) * (n - 2) // 2
if k > mx:
print(-1)
return
buf = []
for i in range(2, n + 1):
buf.append('1 {}'.format(i))
p = 2
q = 3
for _ in range(mx - k):
buf.append('{} {}'.format(p, q))
if q >= n:
p += 1
q = p + 1
else:
q += 1
print(len(buf))
print('\n'.join(buf))
n, k = list(map(int, input().split()))
solve(n, k)
F - Must Be Rectangular!
問題
- 2次元平面上に $N$ 個の点、$i$ 番目の点は $(x_i,y_i)$
- 以下の操作を行える限り繰り返すとき、その操作回数を求めよ
- 座標 $(a,b),(a,d),(c,b),(c,d)$ のうちちょうど3箇所に点が存在するとき、残りの1箇所に点を追加する
解法
長方形の4隅のうち3つに点があれば、残りの1つにも点を追加する。
こんな風に、X座標またはY座標が同じ点を繋げると、
●────●
｜ ｜
●──● ｜
｜ ●─●
｜
●
- ○: 新しく追加された頂点
- ●: 初期または前回以前で追加された頂点
○ ● ○ ●
● ●
● ●
○ ●
● ● ● ●
● ● ○ ○
○ ○ ● ●
● ● ○ ○
というように、連結成分に属するX座標、Y座標の全てに、その点を置くようにできる。
この時、この連結成分に対して操作できる回数は、1回の操作で1点増えるので、以下のようになる。
$(X座標の種類数) \times (Y座標の種類数) - (最初からある個数)$
これを、全ての連結成分に対して調べればよい。
下記の実装では、X座標かY座標が同じ頂点間に辺を張り、DFSで調べている。
import sys
def dfs(s, links, dots, checked):
q = [s]
xs = set()
ys = set()
cnt = 0
while q:
v = q.pop()
if checked[v]:
continue
checked[v] = True
x, y = dots[v]
xs.add(x)
ys.add(y)
cnt += 1
q.extend(links[v])
return max(0, len(xs) * len(ys) - cnt)
n = int(input())
dots = [tuple(map(int, line.split())) for line in sys.stdin]
xs = {}
ys = {}
links = [set() for _ in [0] * n]
for i, (x, y) in enumerate(dots):
if x in xs:
links[i].add(xs[x])
links[xs[x]].add(i)
else:
xs[x] = i
if y in ys:
links[i].add(ys[y])
links[ys[y]].add(i)
else:
ys[y] = i
checked = [False] * n
ans = 0
for i in range(n):
if checked[i]:
continue
ans += dfs(i, links, dots, checked)
print(ans)
