BGM: Live-A-Live (SFC) - Megalomania [Boss Battle] - YouTube
どういう順に処理すればよいか考える。
何となく、〆切の早い方から優先的に手を付けた方がよさそう。そしてこれは考えればちゃんと正しい。
時刻0 B1 B2 B3 |---------- | ---------- | ---------- | A1が A1+A2が A1+A2+A3が この範囲内 この範囲内 この範囲内 である必要 である必要 である必要
〆切の早い順にソートして、(仕事の番号をその順で振り直したとして)
が全て成り立つか調べればよい。
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')
なお、実際の仕事では完全に所要時間を見積もることはほぼ不可能で、いろいろと予想外の時間がかかるので、 そういうのの早期発見という意味ではなるべくマルチタスク、複数を並行に進めることも求められるのが悩ましい。
'-1
' を出力せよまず、$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)
長方形の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)