FunctionalEquation (SRM456hard)

Programming

おもしろかった.

問題:整数1≤C≤16 と, x[i],y[i]が与えられる.
f:Z->Zで,f(2f(x)-x+1)=f(x)+C を満たすという条件のもとでsigma |f(x[i])-y[i]| を最小化せよ.
x,yの長さは<=10000.値は10^9.



まずxに2f(x)-x+1を再代入しするとf(x+2C)=f(x)+2Cが得られる.
逆に,
f(x+2C)=f(x)+2C for any x かつ
f(2f(x)-x+1)=f(x)+C for any x in [0,2C)
が成り立てば元の式も成り立つことがわかるので,これを満たすようなものを考える.
f(0)~f(2C-1)を決めれば自動的にすべての値が決まる.
あるf(x)を決めると,xを代入してf(2f(x)-x+1)の値も決まる.そこから更に何か決まるかというと,できることがxに2f(x)-x+1を代入するしかないが,これはさっきやったf(x+2C)=f(x)+2Cになるのでやる意味がない.

冷静に考えると,xと2f(x)-x+1は(mod 2Cで)偶奇が異なるので, 偶数xに対して,f(x)=a と決めると,元の式から,y=2a-x+1として,f(y)=a+Cが決まる.それ以外(mod 2Cで)は決まらない.
偶数xがどの奇数yとペアを組むかはa mod Cに依存することがわかるので,これを固定する.この時,f(x)=aのとき,f(y)=b(=a+C)とすると,f(x)=a+?Cのときはf(y)=b-?Cになることがわかる,?には任意の整数が入れられる.この時関連する部分(つまりx[i]%2Cがxかy)での値を最小化するには,だいたい中央値っぽいところを?Cとして取れば良いので簡単に計算できる.

さいごにbitDPしておわり.

modが16*2で32になって焦るが,xと2f(x)-x+1の偶奇が違う, というところに気づくのが難しかった.
これ非数オリ勢だとはじめのFEパートどのくらいで気づくんだろう

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
bool B(int x,int y){return (x>>y)&1;}
typedef long long ll;
const int MN=10000;
ll inf=1e18;
ll xs[MN],ys[MN];
ll cost[16][16];
ll dp[17][1<<16];
class FunctionalEquation{
	public:
	long long minAbsSum(int C, int N, int xzero, int xprod, int xadd, int xmod, int yzero, int yprod, int yadd, int ymod){
		xs[0]=xzero,ys[0]=yzero;
		rep(i,N-1) xs[i+1]=(xs[i]*xprod+xadd)%xmod,ys[i+1]=(ys[i]*yprod+yadd)%ymod;
		int M=C*2;
		rep(t,C){
			//f(x)=a+?*C,f(y)=b-?*C
			int x=t*2;
			rep(a,C){
				int yo=2*a-x+1;
				int y=(yo%M+M)%M;
				int b=a+C+(y-yo);
				vector<ll> vc;
				rep(i,N){	// |?*C - tmp|
					if(xs[i]%M==x){
						ll tmp=ys[i]+x-xs[i]-a;
						vc.pb(tmp);
					}
					if(xs[i]%M==y){
						ll tmp=-(ys[i]+y-xs[i]-b);
						vc.pb(tmp);
					}
				}
				sort(all(vc));
				int K=vc.size();
				if(K==0){
					cost[x/2][y/2]=0;
					continue;
				}
				ll med;
				if(K%2==0) med=(vc[K/2-1]+vc[K/2])/2;
				else med=vc[K/2];
				ll qo=med/C;
				ll mn=inf;
				for(ll q=qo-2;q<=qo+2;q++){
					ll sum=0;
					rep(i,K) sum+=abs(q*C-vc[i]);
					chmin(mn,sum);
				}
				cost[x/2][y/2]=mn;
//				printf("f(%d)=%d+?C,  f(%d)=%d+?C,   cost=%lld\n",x,a,y,b,mn);
			}
		}
//		rep(i,C) rep(j,C) printf("cost[%d][%d]=%lld\n",i,j,cost[i][j]);
		rep(i,C+1) rep(j,1<<C) dp[i][j]=inf;
		dp[0][0]=0;
		rep(i,C) rep(b,1<<C) if(dp[i][b]!=inf){
			rep(j,C) if(!B(b,j)){
				chmin(dp[i+1][b|(1<<j)],dp[i][b]+cost[i][j]);
			}
		}
		return dp[C][(1<<C)-1];
	}
};