解く順番の影響が大きかった回。
https://yukicoder.me/problems/no/884
問題
ある大きな2進数が与えられる。
2の累乗を足すまたは引くことを繰り返し、この値を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と迷ったけどこちらを採用した。