ABC333Eを解いた【defaultdict】

筆者はレート800前後の茶～緑コーダ

ABC333のE問題を解いていく

実装コード

後ろから探索して必要なポーションを数え、
対応するものがあれば拾い、
過剰なものは無視する。

所持する個数の最大値と拾ったかどうかの履歴をそれぞれ記憶しておく。

拾ったかどうかの履歴は別にリストでもいいけど反転させるのがなんか嫌だったのでqueueを使用してみた

必要な個数を管理するのにはdefaultdict君が便利

main.py

from collections import defaultdict,  deque
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

d = defaultdict(lambda: 0)

def main():
    N = rI()
    events = [rLI() for _ in range(N)]
    
    action = deque()
    
    total = 0
    ans = 0
    
    for t,x in reversed(events):
        if t == 2:
            d[x] += 1
            total += 1
            ans = max(total,ans)
        else:
            if d[x] > 0:
                d[x] -= 1
                total -= 1
                action.appendleft(1)
            else:
                action.appendleft(0)
    if sum(d.values()) != 0:
        print(-1)
    else:
        print(ans)
        print(*action)
    
if __name__ == '__main__':
    main()

まとめ

問題が剣と魔法の冒険みたいな世界観で好き

後ろから解くという発想は手段の一つとして覚えておきたい。