SRM 443 div1 med:BinaryFlips

SRMの練習会に参加できなかったので後からひっそり練習しました。chokudaiさんの解説で有名な回ですね(僕はeasyしか知りませんでしたが)。

問題:TopCoder Statistics - Problem Statement

解法:やっぱりdiv1 medはたいてい2つくらい良い思いつきをしないと解けないっぽいですね。
まず1つ目の良い思いつきは「0と1をフリップする際には0,1の変わり方は1つ飛びである」ということです。
例えばa=2, b=3, K=2という状態を考えると,次の状態は
a=0, b=5
a=2, b=3
a=4, b=1
という3通りが考えられますが,これはaが0->2->4というように1つ飛びで次の候補になっています。すなわち,aの値としては偶数か奇数,いずれかしかありえないということです。まぁこれはちょっと試せば気づきますかね。
そして大事な2つ目の思いつきは「探索空間が少ないのでちょっと工夫して探索してみる」ということです。
この問題ではKの値が大きいために愚直に探索すると(A+B)*Kの計算量がかかって死にますが,探索する状態としては(A+B)通りしかありません。これを考えると,1回探索したところはもう参照しないようにすれば良さそうです。それを実現するために基本的に幅優先探索+setですでに探索したところの管理というアイデアで探索してみます。
大事なのはpushの部分なのでソースコードのそこの部分を見てください。これは引数としてsetとqueueをとっていますが,まずqueueは幅優先探索でよく使うアレです。最初にsetには探索すべきであるすべてのAの取りうる値が入っていますが,pushでその候補が現れるたび,「そのAの値は探索済み」ということにして,setから削除します。そうすることで,次から調べる時余計なところは探索せずに済みます。Aのありうる値としてlow〜highを指定しておいてsetの中でまだ探索済みでないlow〜highの値をそれぞれ見ていくわけですね。dは幅優先探索で言う距離みたいなものです。

以下ソースコード

void push(set<int>& S, queue<pair<int, int> >& que, int low, int high, int d) {
    auto it = S.lower_bound(low);
    set<int> del;
    for (; *it <= high && it != S.end(); it++) {
        del.insert(*it);
        que.push(make_pair(*it, d));
    }
    for (auto el : del) {
        S.erase(el);
    }
}

class BinaryFlips {
public:
    int minimalMoves(int A, int B, int K) {
        set<int> odd, even;
        int N = A+B;
        for (int i = 0; i <= N; i++) {
            if (i%2) odd.insert(i);
            else even.insert(i);
        }
        queue<pair<int, int> > que;
        que.push(make_pair(A, 0));
        while (!que.empty()) {
            auto p = que.front(); que.pop();
            int a = p.first, d = p.second, b = N-a;
            if (a == 0) return d;
            int high, low;
            {
                int tmp = min(b, K);
                high = a+tmp - (K-tmp);
            }
            {
                int tmp = min(a, K);
                low = a-tmp + (K-tmp);
            }
            if (high % 2) {
                push(odd, que, low, high, d+1);
            } else {
                push(even, que, low, high, d+1);
            }
        }
        return -1;
    }
};