Single Round Match 437 (Div2/1000point)

久しぶりに時間が十分余ったので1000点問題にも挑戦。「1からスタートして与えられた整数nまで何回の操作でたどり着けるかこたえなさい。やっていい操作は

• 1増やす
• 1減らす(元の値が1より大きい場合のみ)
• 累乗する(たとえば元の値が2なら4とか8とか16に変える)

の3つ」

単純に計算すると当然3の累乗で可能性が膨らんで行って発散するので「すでに出た数字は探索しない(最短ではないから)」「ゴールを超えた数字はdecrementで戻ってくるしかないので、powerはギリギリ超えるところまで」「ゴールを超えている数はインクリメントしない」という枝刈りを入れたのだけど、それでもまだ枝刈りが足りなくて、10分前から大急ぎでdistanceって変数を入れて「一番ゴール近い数とゴールの距離よりもゴールより上にはなれている数は最短になり得ないので探索しない」「終盤でpowerが使われなくなったらあとはincrementやdecrementでにじり寄るだけなので+distanceして終了」ってやったけど手元でreal 0m4.153s。タイムアウトで全然ダメ。

  int count(long long goal) {
    typedef unsigned long long ULL;
    const ULL MAX_ULL = 18446744073709551615ULL;
    set<ULL> cur;
    cur.insert(1);
    set<ULL> next;
    set<ULL> used;
    ULL distance = goal - 1;
    typedef set<ULL>::iterator siter;
    int result = 0;
    if(goal == 1) return 0;
    while(true){
      used.insert(cur.begin(), cur.end());

      result++;
      bool skip = true;
      for(siter iter=cur.begin(), end=cur.end(); iter != end; ++iter){
	ULL n = *iter;
	ULL x = n;
	if(n == 1) skip = false;
	if(n != 1){
	  // power
	  while(MAX_ULL / n >= x && x < ULL(goal)){
	    x *= n;
	    if(x == ULL(goal)) return result;
	    if(used.find(x) == used.end() && x < ULL(goal) + distance){
	      next.insert(x);
	      skip = false;
	      if(goal - x > 0 && goal - x < distance){
		distance = goal - x;
	      }
	      if(x - goal > 0 && x - goal < distance){
		distance = x - goal;
	      }

	    }
	  }
	  
	  // decrement
	  x = n - 1;
	  if(used.find(x) == used.end() && x < ULL(goal) + distance){
	    if(x == ULL(goal)) return result;
	    next.insert(x);
	    if(goal - x > 0 && goal - x < distance){
	      distance = goal - x;
	    }
	    if(x - goal > 0 && x - goal < distance){
	      distance = x - goal;
	    }
	  }
	}
	// increment
	x = n + 1;
	if(used.find(x) == used.end() && x <= goal){
	  if(x == ULL(goal)) return result;
	  next.insert(x);
	  if(goal - x < distance){
	    distance = goal - x;
	  }
	}
      }
      if(skip) return result + distance;
      cur = next;
      next.clear();
    }
  }