SRM555 Div1 Easy - CuttingBitString
問題
長さnで '0' と '1' のみからなる文字列sが与えられる
これを2進数として見るとき、全ての部分列がleading-zeroなしで5の冪乗になるようにいくつかの部分列に分けたい
最小でいくつの部分列に分ける必要があるか求めよ
不可能な場合は-1
1 <= n <= 50
解法
s[L,r]の左端が0じゃなくて5の冪乗になってたら頂点Lから頂点r+1への辺を引く
これを全L,rでやって出来たグラフでdfs
class CuttingBitString { public: vector<int> e[55]; int d[55]; void rec(int v, int dis) { d[v] = dis; each(i,e[v]) rec(i,dis+1); } int getmin(string s) { set<ll> p; ll t = 1; while (t<(1ll<<55)) p.insert(t), t *= 5; int n = s.size(); rep(i,n) reps(j,i,n) if (s[i]!='0') { ll sum = 0; reps(k,i,j+1) sum <<= 1, sum |= s[k]-'0'; if (p.count(sum)) e[i].push_back(j+1); } rep(i,55) d[i] = 1<<30; rec(0,0); return (d[n]==1<<30 ? -1 : d[n]); } };