Xmas Contest 2018 B - Bit Smaller
解法
入力が与えられないので条件を満たす数を予め全列挙するプログラムをローカルで実行しておきその答えをtextで提出すればよい。数nをa1,b1,a2,b2,…,ak,bk,cと切れ目を入れたときに条件を満たしているような切り方があれば数nを答えに追加すればよい。この切り方を全て試すような探索をdfsを用いて実装する。dfs(idx, last, turn, a, ans)として引数を持つ。idx→今見ているのが何桁目か、last→最後に切った位置の次の桁(idxで切った場合区間[last,idx]が該当する数)、turn→現在見ている場所が累乗の底か肩のどちらか(trueであれば底)、a→累乗の底、ans→現在までの積の結果をそれぞれ表す。
idx番目で切る場合と切らない場合の2通りに分けて考える。切らない場合は簡単でidxを1桁進める以外引数の値が変わることはないのでdfs(idx+1, last, turn, a, ans)を呼び出せばよい。切る場合は現在見ている場所が累乗の底か肩か(=turn)によって場合分けする。累乗の底であれば a = (区間[last,idx]が表す数) とする。したがってdfs(idx+1,idx+1,false,(区間[last,idx]が表す数),ans)と呼び出せばいい。累乗の指数であればans += a^(区間[last,idx]が表す数)とする。この場合はdfs(idx+1,idx+1,true,0,ans*(区間[last,idx]が表す数))と呼び出せばいい。累乗は二分累乗等で高速に計算できる。
idx=(数nの桁数)となった時点でdfsを終了し、この切り方でnと等しくなったかの判定をする。turnがfalseで累乗の指数を表している場合最後のcを掛けることができないので条件を満たさない。turnがtrueの場合ansに(区間[last,idx)が表す数)を掛けて、nと等しければ条件を満たす数が存在したと判定できる。
注意点として区間[idx,last]がleading-zeroになるような切り方をしてはいけないこととabが大きくなりオーバーフローしてしまうケースを除くためにnより大きい数になった場合探索を打ち切る処理が必要である。自分のパソコンではこのdfsで数分程度だった。
こういうdfsはあまり競プロででないので書くのに慣れていないと大変そう。手元で愚直解を書いたりするときに使えるので書けるようにしておくとたまに役立ちます。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<40; const ll MOD = 1000000007; ll n; const ll m = 20181224; // 二分累乗 O(funcの計算量*logE) template<typename T=ll> T binpow(T x, ll e, function<T(T,T)> func=[](T a, T b){return a*b;}, T d=1) { T ret = d, p = x; while(e > 0) { if(e%2 == 0) { p = func(p, p); e /= 2; if(p > n) return -1; } else { ret = func(ret, p); e--; if(ret > n) return -1; } } return ret; }; vector<ll> pre; bool ok; string s; ll num[10][10]; void dfs(ll idx, ll last, bool turn, ll a, ll ans) { if(idx == s.size()) { if(!turn) return; // [last,s.size()-1]を掛ける ans *= num[last][idx-1]; if(ans == n) ok = true; return; } // idxで切る if(turn) { if(num[last][idx] != -1) { dfs(idx+1, idx+1, false, num[last][idx], ans); if(ok) return; } } else { if(num[last][idx] != -1) { ll bpow = binpow(a, num[last][idx]); if(bpow != -1) { dfs(idx+1, idx+1, true, 0, (ans==0?bpow : ans * bpow)); if(ok) return; } } } // idxでは切らない dfs(idx+1, last, turn, a, ans); } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); vector<ll> ans; FOR(i, 1, m + 1) { if(i%10000==0) cerr << i << endl; n = i; ok = false; s = to_string(i); REP(j, s.size()) { ll t = 0; bool zerol = false, flag = false; FOR(k, j, s.size()) { if(!flag && s[k]=='0') zerol = true; if(s[k] != '0') flag = true; t *= 10; t += s[k]-'0'; num[j][k] = t; if(zerol) num[j][k] = -1; } } dfs(0, 0, true, 0, 0); if(ok) ans.push_back(i); } REP(i, ans.size()) cout << ans[i] << endl; return 0; }
