いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

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

C++でもstringとintのかけ算がしたい

できた。O(log n)かなぁ……。

string operator*(const string& s,int k){
    if(k == 0) return "";
    string p = (s+s)*(k/2);
    if(k%2 == 1) p+=s;
    return p;
}


string solve(int n0,int n5){
    string s;
    if(n0 == 0){
        return "-1";
    }else if(n5 < 9){
        return "0";
    }else{
        return string(9,'5')*(n5/9)+string(n0,'0');
    }
}

でも"44"*3とかできないから微妙に不便だ。

C++にもPythonのenumerateがほしかった

Pythonにはenumerateというメソッドがあって、以下の様に使う。

In [1]: vec = [1,2,3,4,5]

In [2]: for i,v in enumerate(vec):
   ...:     print(i,v)
0 1
1 2
2 3
3 4

Pythonでいうところのforは、C++,Javaでいうところの拡張forにあたるもので、C++/Javaのようなfor(init;pred;change)のような、いわゆるforは存在しない。 拡張forを使いたいけれど、インデックスもほしい場合にenumerateは便利なのである。 それがC++にもほしかった。同じようなことを思っている人はたくさんいるようで、StackOverFlowにもいくつかあった。

c++ - Find position of element in C++11 range-based for loop? - Stack Overflow

ここのを見ながら自分流のC++で書いたのでメモ。

#include <iostream>
#include <vector>

using namespace std;

#define debug(x) #x << "=" << x << "(L:" << __LINE__ << ")"

template<typename T,typename IT>
struct Indexer{
    struct iterator{
        typedef IT inner_iterator;
        typedef typename iterator_traits<inner_iterator>::reference inner_reference;
        struct reference : pair<size_t,inner_reference>{
            reference(size_t s,inner_reference i) :
                pair<size_t,inner_reference>(s,i) {}
            const size_t& index = (*this).first;
            const inner_reference& value = (*this).second;
        };

        iterator(inner_iterator i) : pos(0),it(i) {}
        reference operator*() const {
            return reference(pos,*it);
        }
        iterator& operator++(){
            ++pos;++it;
            return *this;
        }
        iterator operator++(int){
            iterator tmp(*this);
            ++(*this);
            return tmp;
        }
        bool operator==(const iterator& rhs) const{
            return it == rhs.it;
        }
        bool operator!=(const iterator& rhs) const{
            return !(*this == rhs);
        }

    private:
        size_t pos;
        inner_iterator it;
    };


    Indexer(T& t): container(t) {};
    iterator begin() const{
        return iterator(container.begin());
    }
    iterator end() const{
        return iterator(container.end());
    }

private:
    T& container;
};

template<typename T>
Indexer<T,typename T::iterator> enumerate(T& t){
    return Indexer<T,typename T::iterator>(t);
}
// value will be readonly.
template<typename T>
Indexer<T,typename T::const_iterator> const_enumerate(T& t){
    return Indexer<T,typename T::const_iterator>(t);
}


// test codes.
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& val){
    os << "[ ";
    for(typename vector<T>::const_iterator it=val.begin();
        it != val.end();++it){
        os << *it << " ";
    }
    os << "]";
    return os;
}


bool vector_ref_check(vector<int> v){
    vector<size_t> e_index = {};
    vector<int>    e_value = {};
    vector<int> org = v;

    for(auto p:enumerate(v)){
        e_index.push_back(p.index);
        e_value.push_back(p.value);
    }

    bool ret = true;
    for(size_t i=0;i<v.size();i++){
        ret = ret and (e_index[i] == i);
        ret = ret and (e_value[i] == v[i]);
    }

    cerr << "vector_change_check(" << org << ") -> " << ret << endl;
    cerr << " info" << endl;
    cerr << " end." << endl;
    return ret;
}



bool vector_change_check(vector<int> v){
    vector<size_t> e_index = {};
    vector<int>    e_value = {};

    vector<int> org = v;
    // remember! you can change p.second! It's reference.
    for(auto p:enumerate(v)){
        p.first = 0;
        e_index.push_back(p.index);
        p.second = -1;
        e_value.push_back(p.value);
    }

    bool ret = true;
    for(size_t i=0;i<v.size();i++){
        ret = ret and (e_index[i] == 0);
        ret = ret and (e_value[i] == -1);
        ret = ret and (v[i] == -1);
    }
    cerr << "vector_change_check(" << org << ") -> " << ret << endl;
    cerr << " info" << endl;
    cerr << " " << v << endl;
    cerr << " end." << endl;
    return ret;
}

bool vector_const_check(vector<int> v){
    vector<int> org = v;

    for(const auto p:const_enumerate(v)){
        // compile error.
        // p.second = -1;
        // p.first = -1;
    }

    bool ret = true;
    for(size_t i=0;i<v.size();i++){
        ret = ret and v[i] == org[i];
    }
    cerr << "vector_const_check(" << org << ") -> " << ret << endl;
    cerr << " info" << endl;
    cerr << " " << v << endl;
    cerr << " end." << endl;
    return ret;
}

int main(int argc,char **argv){
    vector_ref_check({});
    vector_ref_check({1});
    vector_ref_check({1,2}) ;
    vector_ref_check({1,2,3});

    vector_change_check({});
    vector_change_check({1});
    vector_change_check({1,2});

    vector_const_check({1,2});
    vector_const_check({1,2});
}

Where Is My Phone And Watchというアプリをつくりました。

Where Is My Phone And Watch

というアプリをつくりました。

なにができるん？

  • SmartWatch2からAndroid(4.x)をバイブレーション,着信音を鳴らすことができます。
  • AndroidからSmartWatch2のバイブレーションを鳴らすことができます。

デモ

そのうち。

ダウンロード先

Where is my Phone and Watch? - Android Apps on Google Play

からダウンロードできます。 100円ですが、15分以内なら払い戻し可能なので、ためしてみてください。