SRM 478 250pt: CarrotJumping

TopCoder

問題概要

今の値をxとする。xに対してx = (4*x+3)%MOD or x = (8*x+7)%MODという操作を施す。最低何回で0にできるか求める問題。MAX=10^5回やってたどり着けなかったら-1を返す。

考えたこと

  • (この問題は記憶にあるしネタも覚えているけど当時通していたかどうか忘れた)。
  • f(x) = 2*x + 1とするとこの遷移はf^2とf^3であることが分かる。
  • なので、MAX回までに遷移できるのは高々f^i(x)(i in [0..30000])の個数しかないので全部調べる。
  • そのうち2*a + 3*b = iの不定方程式を解いてa+bを最小化すれば解ける。
  • これでもいけるけど不定方程式とか考えなくても行き先が高々30000個なんだから単純に幅優先で間に合うことが分かる。
  • 幅優先の方を実装。無事通った。

practiceで通ったコード

計算量O(MAX * log MAX)。

#include <map>
#include <queue>
using namespace std;

typedef long long int64;

const int64 MOD = (int)(1e9+7);
const int MAX = (int)(1e5);

struct CarrotJumping {

	int theJump(int init) {
		queue<int64> que;
		map<int64, int> dict;
		dict[init] = 0;
		que.push(init);
		while(!que.empty()){
			int64 tp = que.front(); que.pop();
			int d = dict[tp];
			if(d > MAX){
				break;
			}

			int64 a = (4*tp + 3) % MOD, b = (8*tp + 7) % MOD;
			if(dict.find(a) == dict.end()){
				dict[a] = d + 1;
				que.push(a);
			}
			if(dict.find(b) == dict.end()){
				dict[b] = d + 1;
				que.push(b);
			}
		}

		return dict[0] == 0 || dict[0] > MAX ? -1 : dict[0];
	}

};