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)

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2019/0622_abc131.txt · 最終更新: 2019/06/22 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0