Binary Witch (PKU 2541)

PKU Online Judge

http://poj.org/problem?id=2541

問題

魔法使いが天気予報を行う。a日からのt日間が最近t日と同じ天気の変動をしている場合、明日の天気はa+t日目の天気と一致する。そのような列が複数ある場合は最も最近のものを採用する。そのような列がない場合はt=13,12,11,...,1と減らして行く。それでも無い場合は明日の天気は雨になる。
N日間の天気を与えるので次のL日の天気を答えよ。
1<=N<=1000000
1<=L<=1000

解法

文字列を左から見て出てきた列を全てメモ化すればO(13(N+L)+2^14)で解ける。