PKU 1743:Musical Theme

概要
O(N log^2 N)くらいで繰り返しとなる数列(平行移動できる)を求めてください。

一般人の解法
さ

tozangezanの(嘘)解法
ロリハ。いろんなkeyでやったら衝突したしkey2つにしたらTLEが見えているのでkey1つとkeyを1にしたような謎hashでkey1.5みたいなよくわからないことをしたら通った。二分探索×ソートしているのでO(N log^2 N)かかる。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef unsigned int wolf;
int dat[20000];
wolf ma[20001];
wolf ad[20001];
int key=509;
pair<wolf,pair<int,int>  >hash[20001];
int main(){
	int a;
	wolf Nad=1;
	wolf Nma=1;
	for(int i=0;i<20001;i++){
		ad[i]=Nad;
		ma[i]=Nma;
		Nad*=key;
		Nma+=Nad;
	}
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%d",dat+i);
		int left=0;
		int right=a;
		while(left+1<right){
			int M=(left+right)/2;
			wolf now=0;
			bool ok=false;int sum=0;
			for(int i=0;i<M-1;i++){
				now=now*key+dat[i];sum+=dat[i];
			}
			for(int i=M-1;i<a;i++){
				now=now*key+dat[i];
sum+=dat[i];
				wolf fox=now-ma[M-1]*(dat[i-M+1]);
				hash[i-M+1]=make_pair(fox,make_pair(sum-M*dat[i-M+1],i-M+1));
				now-=ad[M-1]*dat[i-M+1];
sum-=dat[i-M+1];
			}
			std::sort(hash,hash+a-M+1);
			int Now=0;
			for(int i=0;i<a-M+1;i++){
				if(i==0||hash[i].first!=hash[i-1].first||hash[i].second.first!=hash[i-1].second.first){
					Now=hash[i].second.second;
				}else if(hash[i].second.second>=Now+M){
					ok=true;
					break;
				}
			}
			if(ok)left=M;
			else right=M;
		}
		if(left<5)printf("0\n");
		else printf("%d\n",left);
	}
}

ロリハ書くのにはtypedefが重宝する。