2021 TCO Algo Regional Qualification 1

 　Easyで誤読＆実装方針をミス、解けたと思ったMedはシステムテストで落ちて0完。青に落ちてしまった。

コンテストの結果

コンテスト後のツイート

OlympicShooting

　これは読解＆実装問題。

・スコアの合計が高い方が勝ち

・同じなら、後ろから順に、25回ずつのスコアが高い方が勝ち。

・それも同じなら、より後でスコア獲得した方が勝ち。

　というのを実装する。

　最初、「25回ずつ」というのを読み飛ばして戸惑った。

　その後、上手い実装がないかと考えていたのが失敗（とはいえ、短くコードをまとめている人もいた）。多少時間がかかっても愚直に書けば良かった。

TreeTokens

　解法はすぐに分かり、それであっていたが実装でミスしてしまった。

　ROOTに駒がこないためには、ROOTの隣は1個しかあってはダメ。じゃあ、その隣は、というと、3個までしかあってはダメ。その隣は7個まで。さらにその隣は15個まで。

　つまり、ある頂点の駒が高々i個になるためには、その隣の頂点での駒は高々2*i+1個であれば良い。問題が直線状で、ROOTが端にあれば、N＝（頂点数-1）として、2^N-1個が答えになる。

　では分岐があったときは？　というと、葉が深い方の枝に駒を増やしていく（2*i+1倍していく）のが最善。もう一つの分岐は、駒1個からまた増やしていく。

　そういう感じで、各頂点について「葉までの距離のmax」を前計算した後、ROOTの方がから木DPをしていく感じに解いた。

　……のだが、「葉までの距離のmax」の前計算する箇所で間違えた。

　これはよくある木DPなので、トポロジカルソートの逆順に見ていけば良いのだが、なぜかDFSみたいにしてしまっていた。

　焦っていたとはいえ良くない間違いでした。

　システムテストを通ったコードです。
 

mod=1000000007

class TreeTokens ():
    def placeMax(self, N, G, L, seed):
        state = seed
        E=[[] for i in range(N)]
        for i in range(1,N):
            state = (state * 1103515245 + 12345) % (1<<31)
            tmp = (state // 1000) % L
            p = max(0, i-1-tmp)

            E[i].append(p)
            E[p].append(i)

        #print(E)

        ROOT=G

        QUE=[ROOT] 
        Parent=[-1]*(N+1)
        Parent[ROOT]=N # ROOTの親を定めておく.
        TOP_SORT=[] # トポロジカルソート

        while QUE: # トポロジカルソートと同時に親を見つける
            x=QUE.pop()
            TOP_SORT.append(x)
            for to in E[x]:
                if Parent[to]==-1:
                    Parent[to]=x
                    QUE.append(to)


        CC=[-1]*N

        for x in TOP_SORT[::-1][:-1]:
            if CC[x]==-1:
                CC[x]=1
            if Parent[x]==ROOT:
                continue
            CC[Parent[x]]=max(CC[Parent[x]],CC[x]+1)



        AC=[0]*N
        AC[ROOT]=0
        
        ANS=0

        QUE=[ROOT]
        while QUE:
            x=QUE.pop()

            MAX=-1
            if len(E[x])==1 and x!=ROOT:
                ANS+=AC[x]
                ANS%=mod
                
            for to in E[x]:
                if to==Parent[x]:
                    continue
                MAX=max(CC[to],MAX)

            USE=0
            for to in E[x]:
                if to==Parent[x]:
                    continue
                
                if CC[to]==MAX and USE==0:
                    USE=1
                    AC[to]=(AC[x]*2+1)%mod
                else:
                    AC[to]=1

                QUE.append(to)
                
        return ANS%mod