TopCoder SRM 469 Div1: Easy TheMoviesLevelOneDivOne

SRM練習会に参加。Easyのみ提出ACで183.4pt、本番だと382/754位を取れたようだ。

問題はこちら。

問題

ある映画館には n x m の座席がある。すでにいくつかの座席には観客が座っていてそこには座ることはできない。空いている席のうち、二人が同じ横列で隣り合うように座れる席の組はいくつかあるかを答えよ。

n, m ≦ 1,000,000,000　　座席に座っている観客は47人以下。

解法

n, m が大きいので全探索はもちろん無理。座席に座っている観客が少ないので観客が座っている横列のみに注目して計算していく。n, m が大きいので辞書などをつかって観客がいる横列について何番目の座席に観客が座っているかを格納していく。また、簡単のために0番目とm+1番目の席に観客を置いておく。

まず観客が全くいない場合は n * (m-1) だけ隣り合う席の組がある。ここから観客がいる横列を見ていく。同じの横列の観客間の席数が2以上なら、その数より1ひいた数が、その観客間での隣り合う席の組の数である。これを足し合わせていけば答えが得られる。観客がいる横列の数だけ m-1 を引くのを忘れない。

C++などではlong longへの変換する必要があるのでご注意。

def find(self, n, m, row, seat):
    rc = collections.defaultdict(lambda : [0, m+1])
    for i in xrange(len(row)):
        rc[row[i]].append(seat[i])
    
    ans = n*(m-1)
    for r in rc.keys():
        rc[r].sort()
        ans -= m-1
        for c in xrange(len(rc[r])-1):
            ans += max(0, rc[r][c+1] - rc[r][c] - 2)
    return ans