この回なんかのアニメが元ネタなのかな。
https://codeforces.com/contest/1292/problem/B
問題
2次元座標上で無限個の点が与えられる。
ただ、この点の座標は初期値と漸化式の形で表現される。
また、別の初期位置が与えられる。
初期位置から、上下左右のみの移動を行い、最初の無限点のうちできるだけ多くの点を経由したい。
移動距離T以内で最大いくつの点を経由できるか。
解法
無限個の点といいつつ、漸化式の形から座標は点ごとに倍々以上のペースで増えるため、高々O(logT)個しか考えなくてよい。
また、経由する点は点の区間になる。
そこで、まず最初に到達する点を総当たりし、その後座標の昇順にいくつかたどって戻る場合と、逆に降順にたどってまた戻る場合を総当たりしよう。
対象の頂点数が少ないので、最初の到達点と折り返し位置を総当たりしてO(log^3(T))かかっても十分間に合う。
int N=0; ll X[100],Y[100]; ll AX,AY,BX,BY; ll SX,SY,T; int num[100][100]; void solve() { int i,j,k,l,r,x,y; string s; cin>>X[0]>>Y[0]>>AX>>AY>>BX>>BY; cin>>SX>>SY>>T; for(;;N++) { X[N+1]=X[N]*AX+BX; Y[N+1]=Y[N]*AY+BY; //cout<<N+1<<" "<<X[N+1]<<" "<<Y[N+1]<<endl; if(X[N+1]>2LL*10000000000000000) break; if(Y[N+1]>2LL*10000000000000000) break; } N++; int ma=0; FOR(i,N) { ll lef=T-abs(SX-X[i])-abs(SY-Y[i]); int num=0; for(x=i;x<N;x++) { if(x>i) lef-=abs(X[x-1]-X[x])+abs(Y[x-1]-Y[x]); if(lef<0) break; num++; ma=max(ma,num); int cur=num; ll clef=lef; for(y=i-1;y>=0;y--) { if(y==i-1) clef-=abs(X[x]-X[y])+abs(Y[x]-Y[y]); else clef-=abs(X[y+1]-X[y])+abs(Y[y+1]-Y[y]); if(clef<0) break; cur++; ma=max(ma,cur); } } num=0; lef=T-abs(SX-X[i])-abs(SY-Y[i]); for(x=i;x>=0;x--) { if(x<i) lef-=abs(X[x+1]-X[x])+abs(Y[x+1]-Y[x]); if(lef<0) break; num++; ma=max(ma,num); int cur=num; ll clef=lef; for(y=i+1;y<N;y++) { if(y==i+1) clef-=abs(X[x]-X[y])+abs(Y[x]-Y[y]); else clef-=abs(X[y-1]-X[y])+abs(Y[y-1]-Y[y]); if(clef<0) break; cur++; ma=max(ma,cur); } } } cout<<ma<<endl; }
まとめ
いまいち狙いのわからない問題。