yukicoder : No.1106 🦉 何事もバランスが大事

平衡N進法って言い方知ってると楽だったんだな。
https://yukicoder.me/problems/no/1106

問題

5^kの重さの分銅が2個ずつある。
これらを左右同じ数の分銅を乗せて量れる重さはN以下では何通りか。

解法

Nを平衡5進数表現する。
あとは上の桁から0,1,2,-1,-2を取るケースをそれぞれ桁DPしていこう。
その際状態として、見ている桁のほかに、N未満確定かどうか、正の数確定かどうか、左右の分銅の数の差がある。

ll N;
ll memo[30][2][2][120];
vector<int> V;


ll dp(int d,int pos,int les,int dif) {
	if(d==V.size()) {
		return (dif==60)&&pos;
	}
	
	if(memo[d][pos][les][dif]>=0) return memo[d][pos][les][dif];
	ll ret=0;
	int i;
	for(i=-2;i<=2;i++) {
		if(les==0 && i>V[d]) continue;
		if(pos==0&&i<0) continue;
		
		ret+=dp(d+1,pos|(i>0),les|i<V[d],dif+i);
		
	}
	return memo[d][pos][les][dif]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(N) {
		x=N%5;
		if(x<0) x+=5;
		if(x>=3) x=x-5;
		V.push_back(x);
		N=(N-x)/5;
	}
	reverse(ALL(V));
	MINUS(memo);
	
	cout<<dp(0,0,0,60)<<endl;
	
	
}

まとめ

本番だともっと面倒なコードにしてそう。