Atcoder Beginner Contest 080
$2^{10}=1024$通りなので、全ての営業時間の組み合わせを全探索。店の数も100以下なので、間に合う。
営業時間を10桁の2進数で表すと、「自店と他店の共通して営業している時間帯の数」は、「自店の営業時間を表す数と、他店の営業時間を表す数の、AND(論理積)を取った後に立っているビット数」と表せる。
月AM | 月PM | 火AM | 火PM | 水AM | 水PM | 木AM | 木PM | 金AM | 金PM | 2進数表現 | 共通 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
自店 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1010110011 | |
他店 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0111011011 | |
AND | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0010010011 | 4 |
こうすると、自店の営業時間の全探索も「1~1023の数値の全探索」で表現でき、1回の計算も配列で持つよりは速い。
pythonでは、立っているビット数を直接得られる関数は無いが、2進数テキストに変換して'1'の数を数えるのが速いらしい。
bin(x).count('1')
from operator import mul n = int(input()) cof = [1 << x for x in range(10)] fs = [sum(map(mul, map(int, input().split()), cof)) for _ in range(n)] ps = [list(map(int, input().split())) for _ in range(n)] ans = float('-inf') for g in range(1, 1024): ans = max(ans, sum(p[bin(f & g).count('1')] for f, p in zip(fs, ps))) print(ans)
はじめに思いついた解法(WA)
だが、これだと次のような場合を捉えきれない。
なので、以下の応急的な事前処理を施して、AC
ソートを2回もしているため、効率悪い。もっと良い解法がある気がする。
from heapq import heapreplace, heappush n, v = map(int, input().split()) programs = [tuple(map(int, input().split())) for _ in range(n)] programs.sort() tmp = [None] * v combined = [] for s, t, c in programs: c -= 1 prev = tmp[c] if prev is not None: ps, pt, pc = prev if pt == s: tmp[c] = (ps, t, c) else: combined.append((ps, pt, pc)) tmp[c] = (s, t, c) else: tmp[c] = (s, t, c) for prev in tmp: if prev is not None: combined.append(prev) combined.sort() recorders = [(-1, None)] for s, t, c in combined: end, channel = recorders[0] if end < s or c == channel: heapreplace(recorders, (t, c)) else: heappush(recorders, (t, c)) print(len(recorders))
時間の範囲がたかだか$10^5$なので、imos法が使えるようだ。
加算と減算する$A$のインデックスにちょっと迷ったが、時刻 $T$ が含まれない時は $A[T]$ でよい。
こちらの方が少し速い。
from collections import defaultdict from itertools import accumulate n, v = map(int, input().split()) programs = defaultdict(list) for _ in range(n): s, t, c = map(int, input().split()) programs[c].append((s, t)) imos = [0] * (10 ** 5 + 1) for c, p in programs.items(): p.sort() ps, pt = p[0] for s, t in p[1:]: if pt == s: pt = t else: imos[ps - 1] += 1 imos[pt] -= 1 ps, pt = s, t imos[ps - 1] += 1 imos[pt] -= 1 print(max(accumulate(imos)))