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