ABC329Dを解いた

筆者はレート600前後の茶色コーダ

7月4日に開催されたADTで登場した以下の問題を解いていく

ADTのページ(ALL)

実装コード

解説をみずにとりあえず、セグ木を実装し、候補者番号と票数を載せて値更新を回した
値更新するたびに全区間の集計を入れて表示したらACした。

セグ木の実装は以下を使用した

• shakayami/ACL-for-python

from collections import defaultdict
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)


class segtree():
    # 略


def segfunc(a,b):
    if a[1] > b[1]:
        return a
    elif a[1] < b[1]:
        return b
    elif a[0] < b[0]:
        return a
    else:
        return b

def main():
    N, M = rLI()
    A = rLI()
    
    e = (N+1,0)
    
    G = segtree([e for _ in range(N+1)],segfunc,e)
    
    d = defaultdict(lambda: -1)
    c = 0
    
    for a in A:
        if d[a] == -1:
            d[a] = c
            c += 1
            G.set(c,(a,0))
        else:
            i = d[a]
            _, n = G.get(i)
            n += 1
            G.set(i,(a,n))
        m, _ = G.all_prod()
        print(m)
        
if __name__ == '__main__':
    main()

ここで解説をみたが、最大値の番号と各候補者の票数だけを管理すればよかったようだ。

from collections import defaultdict
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)

def main():
    N, M = rLI()
    A = rLI()
    
    d = defaultdict(lambda: 0)
    m = A[0]
    for a in A:
        d[a] += 1
        if d[a] > d[m] : m = a
        elif d[a] == d[m] : m = min(m,a)
        print(m)
        
if __name__ == '__main__':
    main()

まとめ

ABC329Dを解いた、解法にはセグ木を使用した方法と
最大値の番号と各候補者の票数だけ管理した方法で解いた

感想

解説を見ずに問題を解くことができたのは満足だが、この問題の処理にセグ木は過剰装備だった。
必要最低限のラインを見極めるようにするのが今後の課題である。