SRM 255 DIV1 Hard OddDigitable

問題 Editorial

問題

十進表示をした時に全ての数字が奇数である数を"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();
	}
};