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（論理積）を取った後に立っているビット数」と表せる。

	月AM	月PM	火AM	火PM	水AM	水PM	木AM	金AM	金PM	2進数表現	共通
自店	1	0	1	0	1	1	0	1	1	1010110011
他店	0	1	1	1	0	1	1	1	1	0111011011
AND	0	0	1	0	0	1	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)

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))

            

        
      

解法2

時間の範囲がたかだか $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)))

            

        
      