TopCoder SRM 728 Div1 Easy: Halving

するめうめ

tsutaj.hatenablog.com

問題概要

自然数が 個与えられる。各数字 に対して、次の操作を何度でも行える。

• が偶数のとき、その数字を に変える。
• が奇数のとき、その数字を か のどちらかに変える。

操作を何回か行い、 個全てが同じ数字になるようにしたい。これを実現するために必要な操作回数の最小値を求めよ。

解説

ある数字 に対してこの操作をするとき、その状態数は 程度なので、全て列挙することができます。

あとは、ある状態を持ってきたときに全ての要素においてその状態になりえるかをチェックして、最小を求めればよいです。

ソースコード

class Halving {
    public:
    map<int, int> mp[110];
    int minSteps(vector<int> a) {
        int N = a.size();
        for(int i=0; i<N; i++) {
            mp[i].clear();
            queue<int> que;
            mp[i][a[i]] = 0, que.push(a[i]);

            while(que.size()) {
                int cur = que.front(); que.pop();
                vector<int> x;
                if(cur % 2 == 0) {
                    x.push_back(cur / 2);
                }
                else {
                    x.push_back((cur-1) / 2);
                    x.push_back((cur+1) / 2);
                }
                    
                for(auto nxt : x) {
                    if(mp[i].count(nxt)) continue;
                    mp[i][nxt] = mp[i][cur] + 1, que.push(nxt);
                }
            }
        }

        int ans = INF;
        for(auto x : mp[0]) {
            int tmp = 0, val = x.first;
            for(int i=0; i<N; i++) {
                if(mp[i].count(val)) tmp += mp[i][val];
                else tmp = INF;
            }
            ans = min(ans, tmp);
        }
        return ans;
    }
};

状態数が少ないことを見抜くまでに時間がかかって、かなり手間取りました・・・