Python3: 長テーブルのうなぎ屋 (paizaランク B 相当)やってみた

よく知られている問題ですが、ちょっと違うやりかたでやってみました。

# 要素を順に評価して、最後の要素を返す
unbox = lambda *xs: xs[-1]

# 循環リストにおいて x は [ start, end ) の範囲内にあるか
inrange = lambda start, end: lambda x: unbox(
    ge := start <= x
    , lt := x < end
    , ge and lt if start < end else
        lt or ge if end < start else
        False
    )
           

LEN_SEATS, LEN_GROUPS = map(int, input().split())

sits = []
total = 0

for _ in range(LEN_GROUPS):
    n, start, end = (lambda n, s:
                     (n, s % LEN_SEATS, (n + s) % LEN_SEATS)
                     )(*map(int, input().split()))
    
    if len(sits) == 0:
        sits = [(start, end)]
        total += n
        continue
    
    for i in range( len(sits) ):
        # 前のグループの end と 今のグループの start の間にあるか
        invacant = inrange( sits[(i-1) % len(sits)][1]
                            , sits[i][0]
                            )
        
        if not invacant( start ):
            continue
        if not invacant( (end-1) % LEN_SEATS ):
            break
        
        total += n
        sits = [*sits[:i], (start, end), *sits[i:]]
        break
            
print(total)

この問題、たいがいは単純に席のリストを作って、座れたかどうかのフラグをチェックするやりかたか、集合演算でするか、みたいな感じだと思います。

ここでのやりかたは前者に似ているのですが、座れているグループとグループの間に、新しいグループの先頭と最後尾が座れればみんなが座れる、という感じ。毎回全部の席をチェックする必要なくない?的なことです。

コンセプトはいいと思ったんだけどなー。書いてみると意外と複雑でした。

せっかくやってみたんでここにあげときます。