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;
}