POJ(PKU) Jessica's Reading Problem

蟻本にある問題。

蟻本頭良すぎて焦る。

しゃくとり法。

#include <cstdio>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int main(){
  
  int p,a[1000003];
  scanf("%d",&p);
  for(int i = 0;i < p;i++) scanf("%d",&a[i]);
  set<int> all;
  for(int i = 0;i < p;i++){
    all.insert(a[i]);
  }
  
  int n = all.size();
  
  int s = 0,t = 0,num = 0;
  map<int,int> count;
  int ans = p;
  for(;;){
    while(t < p && num < n){
      if(count[a[t++]]++ == 0) num++;
    }
    if(num < n)break;
    
    ans = min(ans,t-s);
    if(--count[a[s++]] == 0) num--;
  }
  
  printf("%d\n",ans);
  
  return 0;
  
}

かなりどうでもいいのだが、TLE黒歴史ソースがこちら。
蟻本みたいな天才な考え方はできなかった。

#include <cstdio>
#include <map>
#include <iostream>

using namespace std;

int ans;

int p,d[1000003];

int main(){
  map<int,int> m;
  scanf("%d",&p);
  ans = p;
  for(int i = 0;i < p;i++){
    scanf("%d",&d[i]);
    m[d[i]] = 0;
  }
  map<int,int>::iterator it;
  bool flag;
  int s = 0,t = 0;
  int ho = -1;
  for(;;){
    flag = true;
    while(flag == true && t < p){
      flag = false;
      if(ho == 0){
	break;
      }else if(ho == -1){
      for(it = m.begin();it != m.end();it++){
	if(it->second == 0){
	  flag = true;
	  break;
	}
      }
      if(flag){
	m[d[t]]++; t++;
      }
      }else{
	for(int i = t;i < p;i++){
	  m[d[i]]++;
	  if(d[i] == ho){
	    ho=0;
	    flag = false;
	    break;
	  }else{
	    flag = true;
	  }
	}
      }
    }
    if(t == p){
    flag = false;
    for(it = m.begin();it != m.end();it++){
      if(it->second == 0){
	flag = true;
	break;
      }
    }
    if(flag)break;
    }
    ans = min(ans,t - s);
    m[d[s]]--; s++;
    if(m[d[s]] == 0) ho = d[s];
  }
  
 
  
  printf("%d\n",ans);
  
  return 0;
  
}