Codeforces #492 Div1 E. Number Clicker

本番中時間切れだったけど、ツメが甘くて結局ダメだったかも。
http://codeforces.com/contest/995/problem/E

問題

素数Pと、P以下の自然数U,Vが与えられる。
Uに以下の手順を繰り返しVにしたい。
200手以下でできる例を示せ。

• Uを(mod P)でインクリメントする
• Uを(mod P)でデクリメントする
• Uを(mod P)で逆数にする

解法

自分は正しいとは言えないかもしれない方法で解いた。
半分全列挙に相当するかな。

Uから最大15手分を総当たりした数値集合を作り、またVから最大15手分巻き戻し方を総当たりした数値集合を作る。
両者の間に差が170以下の組があれば、インクリメント/デクリメントで遷移できる。

もちろん、そのような組があることは決定的ではないので、ある意味乱択っぽいかも。

ll U,V,mo;

ll rev(ll a) {
	ll r=1, n=mo-2; a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

map<ll,int> D[2];
map<ll,int> F[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>U>>V>>mo;
	D[0][U]=0;
	D[1][V]=0;
	FOR(i,2) {
		queue<int> Q;
		Q.push(D[i].begin()->first);
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			if(D[i][x]>=15) continue;
			FOR(j,3) {
				if((j^i)==0) y=(x+1)%mo;
				if((j^i)==1) y=(x+mo-1)%mo;
				if(j==2) {
					if(x==0) continue;
					y=rev(x);
				}
				if(D[i].count(y)) continue;
				D[i][y]=D[i][x]+1;
				F[i][y]=j;
				Q.push(y);
			}
		}
	}
	
	FORR(d0,D[0]) FORR(d1,D[1]) {
		int lef=200-d0.second-d1.second;
		if(min(abs(d0.first-d1.first),mo-abs(d0.first-d1.first))<=lef) {
			vector<int> VV;
			int cur=d0.first;
			while(cur!=U) {
				VV.push_back(F[0][cur]+1);
				if(F[0][cur]==0) cur=(cur+mo-1)%mo;
				else if(F[0][cur]==1) cur=(cur+1)%mo;
				else if(F[0][cur]==2) cur=rev(cur);
			}
			reverse(ALL(VV));
			
			x=d0.first;
			y=d1.first;
			if(x<y && y-x>lef) x+=mo;
			if(x>y && x-y>lef) y+=mo;
			while(x!=y) {
				if(y>x) VV.push_back(1), x++;
				else if(x>y) VV.push_back(2), x--;
			}
			
			
			cur=d1.first;
			while(cur!=V) {
				VV.push_back(F[1][cur]+1);
				if(F[1][cur]==0) cur=(cur+1)%mo;
				else if(F[1][cur]==1) cur=(cur+mo-1)%mo;
				else if(F[1][cur]==2) cur=rev(cur);
			}
			cout<<VV.size()<<endl;
			FORR(v,VV) cout<<v<<" ";
			cout<<endl;
			return;
			
		}
	}
	
}

まとめ

本番12手あれば十分だろうと思ってたけどダメだった。