ABC 080

Atcoder Beginner Contest 080

C - Shopping Street

• 自店の営業時間を決める
• 月～金、AM・PM の10区分の時間帯がある
• 同じ商店街の他の $N$ 個の店の営業時間は既に決まっている
• 「自店と店 $i$ が共通して営業している時間帯の数 $c$」によって、自店が得られる利益 $P_{i,c}$ が決まっている
• 自店の総利益は、$P_{i,c}$ の全他店 $i=1..N$ の和
• 総利益を最大化せよ

$2^{10}=1024$通りなので、全ての営業時間の組み合わせを全探索。店の数も100以下なので、間に合う。

営業時間を10桁の2進数で表すと、「自店と他店の共通して営業している時間帯の数」は、「自店の営業時間を表す数と、他店の営業時間を表す数の、AND（論理積）を取った後に立っているビット数」と表せる。

こうすると、自店の営業時間の全探索も「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)

D - Recording

• $N$ 個のテレビ番組を録画機で全て録画
• 録画機は、あるチャンネルの時刻 $S$ から時刻 $T$ までを録画するとき、時刻 $S-0.5$から、他のチャンネルの録画には使えない
  • つまり、同じチャンネルなら番組の時刻が連続していても録画できるが、違うチャンネルなら時刻0.5以上間隔が無いと録画できない
• 録画機はいくつ必要？

はじめに思いついた解法（WA）

• 番組を開始時刻順にソート
• 優先度キューを使って、早く終わる録画機から次の番組を録画
• 一番早く終わる録画機でも次の番組を録画できない場合、優先度キューに追加（キューの要素数が1増える）
• 最終的な優先度キューの要素数が、必要な録画機数

だが、これだと次のような場合を捉えきれない。

• 時刻$t$で録画が終わる録画機が複数個ある
  • チャンネル$c_1, c_2$を録画中とする
• 次にちょうど時刻$t$からチャンネル$c_2$で始まる番組があった場合
  • 本来は、$c_2$を録画中の録画機で続けて録画できるため、増やさなくてよい
• 優先度キューから先に出されるのは$c_1$を録画中の録画機
  • 録画不可と判断して、録画機を1つ増やしてしまう

なので、以下の応急的な事前処理を施して、AC

• 同じチャンネルで連続している番組は、繋げて1番組とする

ソートを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法が使えるようだ。

いもす法 - いもす研 (imos laboratory)

• $10^5+1$のサイズの配列 $A$ を作る
• 同じチャンネルの連続した番組はまとめる
• 番組の開始・終了時刻を $S,T$ とすると、
  • $A[S-1]$に1加算
  • $A[T]$から1減算
• 全番組を処理後、$A$ の累積和をとり、その中の最大値が答え

加算と減算する$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)))