AtCoder Beginner Contest 131 D,E,F 問題メモ

AtCoder Beginner Contest 131

AtCoder Beginner Contest 131 解説放送 - YouTube

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)

            

        
      