SRM 255 DIV1 Hard OddDigitable
問題
十進表示をした時に全ての数字が奇数である数を"odd-digitable number"と呼ぶ。
(x ≡ M (mod N))であるような最小のodd-digitable numberを求めよ。ただし存在しない場合は"-1"を返せ
解答
Editorialを参考にした。
BFS。
最初に0から始めて、以降右端に(1,3,5,7,9)を足していくことによってodd-digitable numberを生成する。
その状態を(mod N)でメモができる。
これは(x ≡ y (mod N) ならば x * 10 + z ≡ y * 10 + z (mod N))である(単純に加算と乗算のwell-definedness)から
コメント
状態の代表でメモするBFSは初めて知った。面白い。
状態の遷移がwell-defined的な感じならいけるのか。なるほどねえ
コード
#include <string> #include <vector> #include <sstream> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define pb(x) push_back(x) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef long long ll; typedef vector<long long> vl; struct OddDigitable { string findMultiple(int N, int M) { vl q, next; next.pb(0); static ll memoMin[100001]; mset(memoMin, INF); while(!next.empty()) { q.swap(next); while(!q.empty()) { ll x = q.back(); q.pop_back(); //無駄に最小値チェックしてるけど、生成が小さい方からなので単にboolでフラグ立てとくだけでいい if(memoMin[(x != 0) + x % N] <= x) continue; memoMin[(x != 0) + x % N] = x; rep(i, 5) { ll y = x * 10 + (i * 2 + 1); next.pb(y); } } } if(memoMin[M+1] == INFL) return "-1"; stringstream ss; ss << memoMin[M+1]; return ss.str(); } };