yukicoder : No.884 Eat and Add

解く順番の影響が大きかった回。
https://yukicoder.me/problems/no/884

問題

ある大きな２進数が与えられる。
２の累乗を足すまたは引くことを繰り返し、この値を0にしたい。
最少何回足し引きを行えばよいか。

解法

DPでも解けるが、自分はEditorialでいう別解で解いた。
下の位から見ていき、1が現れたら以下のようにする。

• 1が1つだけあるなら、2の累乗を引くことでその桁を0にする。
• 1がいくつか連続するなら、最下位桁に相当する2の累乗を足すことで、繰り上がりによってそれらを1つの1にできる。

int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	S='0'+S;
	N=S.size();
	reverse(ALL(S));
	int num=0;
	FOR(i,N) if(S[i]=='1') {
		if(S[i+1]=='0') {
			num++;
			S[i]='0';
		}
		else {
			while(S[i]=='1') i++;
			S[i]='1';
			i--;
			num++;
		}
	}
	cout<<num<<endl;
}

まとめ

DPと迷ったけどこちらを採用した。