Codeforces 355A Vasya and Digital Root (乱択解)
問題: 英語を読むか torusさんのブログ http://d.hatena.ne.jp/torus711/20131013/p3 を参照してください。
Aにしてはどうやって解くのか初見でわからなかった。簡単な解法としては、最初の桁だけdにすれば良いのだけれど、それすら思いつかなかった。 よって、乱択アルゴリズムをつかった。分布がどうなるかはわからないけれど、大体一様だと思うことにすると、確率p(=1/d)で答が出る。 N回計算して、(答が存在する場合には)答が出ない確率は(1-p)Nで、つまり((d-1)/d)Nである。 (ちなみに計算の回数の期待値はd回である.幾何分布より)
このアルゴリズムはモンテカルロ法である(間違った答を出す可能性がある)
#include <iostream> #include <sstream> #include <string> #include <random> #define repeat(i,n) for(signed int i=0;(i)<(n);i++) using namespace std; string to_s(int n){ string ret; stringstream ss; ss << n; ss >> ret; return ret; } int to_i(string s){ int ret; stringstream ss; ss << s; ss >> ret; return ret; } string S(const string n){ int r = 0; for(const char c : n){ r += c-'0'; } return to_s(r); } string dr(const string n){ int s = to_i(S(n)); if(s < 10){ return to_s(s); }else{ return dr(to_s(s)); } } string solve(int k,int d){ // can't compile in codeforces. // random_device seed_gen; // mt19937 engine(seed_gen()); mt19937 engine(time(NULL)); uniform_int_distribution<> dist('0','9'); repeat(i,100){ // first is not 0. string s; while(true){ char c = dist(engine); if(c != '0' or k == 1){ s += c; break; } } while((int)s.size() < k){ s += dist(engine); } if(to_i(dr(s)) == d){ return s; } } return "No solution"; } int main(){ int k,d; cin >> k >> d; cout << solve(k,d) << endl; return 0; }