[[ABC 080]]

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木PM金AM金PM2進数表現共通
自店10101100111010110011
他店01110110110111011011
AND 001001001100100100114

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

programming_algorithm/contest_history/atcoder/2017/1203_abc080.txt · 最終更新: 2018/07/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0