天下一プログラマーコンテスト 2012 予選 B D: 大爆発

調べても解説がなかったので

問題概要

原文 → D - 大爆発

日本語なので元の問題文参照

解説

まず自明なケースとして、以下があります。地味に厄介なので最初に弾きましょう。

• ブロックがひとつも存在しない (答えは )
• 全てのマスにブロックが存在する (答えは )

これ以外のケースは、少なくとも 1 つはブロックがないマスであり、そこに爆弾を置くと、置いた列に関して全て爆弾がおける状態になるので、必ず目標を達成可能であることがわかります。それでは次に、最小値がどうなるかを考えましょう。

ここでは 行 列目のマスを と書くことにします。 に爆弾を置くと、以下が成り立ちます。

• 行目にはブロックがひとつも存在しない
• 列目にはブロックがひとつも存在しない

ある場所にいったん爆弾を置いてしまえば行・列方向ともに一掃され、その後は各行に爆弾を置けるため、各行において爆弾は 高々 1 回 置いてしまえばよさそうです。行・列の制約は小さめなので、爆弾を置く行を決め打ち して考えることにしましょう。これは 通りありますが制約が小さいのでひとまず大丈夫です。

行を決め打ちすると、爆弾を置かなければならない列がわかります。具体的には以下の条件を満たす列 については少なくとも 1 つ置かなければなりません。(理由は明らかだと思います)

• 行目が決め打ちで選ばれておらず、 にブロックが存在する場合

これで、「決め打ちした行の集合」と「選ぶべき列の集合」がそれぞれ得られます。図示すると次のようになります。

「決め打ちした行」かつ「選ぶべき列」であって、ブロックが存在しない (= 爆弾をおける) マスを列挙してみましょう。先程までの議論から、爆弾を置くべき行・列それぞれについて、1 個でも置ければ十分ですので、それぞれのマスを頂点と見立てて (行, 列) の二部グラフを作ると、最小辺被覆問題 に帰着されることがわかります。(くわしくは けんちょんさんの記事 を読んでみてください。) 今回のケースにおいては、二部グラフの最大マッチングを求めることで容易に解を求められる問題なので、これで解けそうです。

ただし一点だけ注意しなければならないケースがあります。それは、「決め打ちした行」かつ「選ぶべき列」であるマスに空きマスが 1 つも存在しない場合です。この場合は選択できるマス (= 二部グラフにおける頂点) が存在しないため、そのままでは対応できません。いま、空きマスが全体で少なくとも 1 つ以上存在する場合のみを考えているので、どこかに空きマスがある (= 爆弾をおける) としてよく、そのようなマスに爆弾を置くと元々置きたかった行または列にも置けるようになります。しかし、最初に設置した爆弾は「元々置きたかった行」かつ「元々置きたかった列」に置いているわけではないため、置くべき爆弾の数は合計で 個必要になります。 以上のことに注意すると正答を得られます。

ソースコード

AC コード (tsutaj): Submission #13934922 - 天下一プログラマーコンテスト2012 予選B

// 二部マッチングは略

int main() {
    int H, W; scanf("%d%d", &H, &W);
    int block = 0;
    vector<string> board(H);
    for(int i=0; i<H; i++) {
        cin >> board[i];
        block += count(board[i].begin(), board[i].end(), '#');
    }

    // 自明なケース
    if(block == 0) { cout << 0 << endl; return 0; }
    if(block == H*W) { cout << -1 << endl; return 0; }

    int ans = INF;
    // 行の選び方を全部試す
    for(int bit=0; bit<(1<<H); bit++) {
        vector<int> xs, ys;

        // 選んだ行
        for(int i=0; i<H; i++) if(bit >> i & 1) xs.emplace_back(i);

        // 選んでいない行において、ブロックが存在するような列
        for(int j=0; j<W; j++) {
            for(int i=0; i<H; i++) {
                if(bit >> i & 1 or board[i][j] == '.') continue;
                ys.emplace_back(j);
                break;
            }
        }

        Flow<int> fl(H + W + 2);
        int source = H + W, sink = source + 1;
        int N = xs.size(), M = ys.size();
        for(int i=0; i<H; i++) fl.add_edge(source, i, 1);
        for(int i=0; i<W; i++) fl.add_edge(H+i, sink, 1);
        for(auto x : xs) {
            for(auto y : ys) {
                if(board[x][y] == '.') fl.add_edge(x, H+y, 1);
            }
        }

        // 行と列の二部マッチング
        int bm = fl.max_flow(source, sink);

        // bm が 0 であるとき (どの board[x][y] にもブロックがあるとき)
        // -> xs, ys の union? であってブロックがないマスが存在するか探す
        if(bm == 0) {
            bm = -1;
            for(auto x : xs) for(int y=0; y<W; y++) if(board[x][y] == '.') bm = 0;
            for(auto y : ys) for(int x=0; x<H; x++) if(board[x][y] == '.') bm = 0;
        }
        if(bm == -1) chmin(ans, min(N, M) - bm);
        else chmin(ans, N + M - bm);
    }
    cout << ans << endl;
    return 0;
}

iwiwi さんのコードをかなり参考にしました (ありがとうございます)

Educational Codeforces Round 87 G: Find a Gift

こういうの典型なんですかね？結構面白い気がしたのでブログに残しておく

問題概要

原文 → Problem - G - Codeforces

個の箱が一列に並んでいる。箱の中身は石またはギフトである。石が入っている箱はすべて同じ重さであり、ギフトが入っているどの箱よりも真に重い。ギフトが入っている箱どうしは重さが異なる可能性がある (注意: 石が入っている箱より軽いことは保証される)

高々 50 回、以下の形式の質問をすることで、最も左に位置する、ギフトが入っている箱の番号 を当てよ。

• 積集合が空 (つまりお互いに要素に被りがない) であるような、空でない添字集合 をジャッジに投げて質問する。これは、「 に属する箱の重さの総和と、 に属する箱の重さの総和を比較したときに、どちらが重いか (どちらも同じであるばあいは同じであること) 」を質問しており、ジャッジからはその回答が得られる。

解説

※この解説は 公式の解説 をベースに書いています。

最も左に位置するものを当てる必要があるので、左に位置する箱から順に情報が得られるのが望ましいだろう、という直感を働かせましょう。まずはじめに、最も左の箱に入っているものが石であるかギフトであるかを特定できるかを考えてみましょう。

質問時に使用する の要素数を、それぞれいったん に限定しましょう。 は必ず最も左の要素のために使うことにします。さて、 はどのように選択すれば良さそうでしょうか？実は、これについて以下のことが言えます。

ランダムに要素を選び、それを の元とする戦略を何度か取ると、高い確率で最も左の要素が石であるかどうかがわかる。

制約を見ると分かるとおり、ギフトの数は 高々 の半分以下 であるため、適当に要素を選んだ際にそれが石である確率は半分以上はあることになります。最も左の要素がギフトであることを特定するためには、 の要素として石であるものを選ぶ必要がりますが、半分以上の確率で石を選択できるため、だいたい 回程度試行しますと石を選べる確率が くらいになるため、十分大きい確率で判定できることになります。よって、最も左の箱がギフトである場合には、 回程度の質問で答えが得られること・そうでない場合にも「最も左の箱が石である」という情報が得られることがわかりました。

以下、最も左の箱がギフトではない (石である) 状況を考えます。今は最も左の箱、つまり 番目の箱のみについて情報が得られていますが、ここから情報を効率的に増やすにはどうすればよいでしょうか？これについては、以下のことを利用して戦略を取ると良いです。

番目の箱について全て石が含まれている場合、「 番目の箱まで全て石が含まれていること」または「 番目から 番目の箱の中にギフトが少なくともひとつ含まれること」のいずれかの情報が得られる

ギフトは石よりも軽いため、質問する集合に含まれている要素数が同じで、かつ一方が全て石であるような場合、もう一方が軽いと判定された時点でそこにギフトがあることがわかります。逆にそのような判定をされなかった場合は、もう一方もすべて石であることがわかります。いま、 番目が石であるという情報をすでに持っているわけですから、この戦略が利用できるというわけです。

さて、この戦略を利用すると 「添字区間 の間に少なくともひとつギフトが存在する」ことまでは特定できます。この後にどうすればよいかと言うと、二分探索をすると良いです。というのも、 に関しては全て石が含まれているので、片方の集合を から、もう片方の集合を から要素数が同じになるように質問すれば、先ほどと同様に「全部石の箱たち」と「一部はギフトかもしれない箱たち」との比較ができ、二分探索が可能です。

ソースコード

#ifdef LOCAL を使ってローカルでもテストできるようにしてあるので、若干冗長です、、、

enum Verdict {
    EQUAL,
    LEFT,
    RIGHT,
};

const int STONE_WEIGHT = 10;
vector<int> ref_vec;

Verdict ask_to_judge(int l1, int r1, int l2, int r2) {
    vector<int> A, B;
    for(int i=l1; i<r1; i++) A.emplace_back(i);
    for(int i=l2; i<r2; i++) B.emplace_back(i);

    printf("? %zu %zu\n", A.size(), B.size());
    for(size_t i=0; i<A.size(); i++) printf("%d%c", A[i]+1, " \n"[i + 1 == A.size()]);
    for(size_t i=0; i<B.size(); i++) printf("%d%c", B[i]+1, " \n"[i + 1 == B.size()]);
    fflush(stdout);

    int verdict;
    
#ifdef LOCAL
    int SA = 0, SB = 0;
    for(auto &a : A) SA += ref_vec[a];
    for(auto &b : B) SB += ref_vec[b];

    if(SA < SB) verdict = RIGHT;
    else if(SA > SB) verdict = LEFT;
    else verdict = EQUAL;

    vector<string> v_to_s = {"EQUAL", "LEFT", "RIGHT"};
    fprintf(stderr, "# verdict: %s\n", v_to_s[verdict].c_str());
    return (Verdict)verdict;
#endif

    string s; cin >> s;
    if(s == "FIRST") verdict = LEFT;
    if(s == "SECOND") verdict = RIGHT;
    if(s == "EQUAL") verdict = EQUAL;
    assert(s != "WASTED");
    return (Verdict)verdict;
}

void answer(int x) {
    printf("! %d\n", x+1);
    fflush(stdout);

#ifdef LOCAL
    assert(ref_vec[x] < STONE_WEIGHT);
    for(int i=0; i<x; i++) assert(ref_vec[i] == STONE_WEIGHT);
    puts("[ OK ]");
#endif
}

void solve() {
    int N, K; scanf("%d%d", &N, &K);
#ifdef LOCAL
    ref_vec.resize(N);
    printf("# Input weights.\n");
    printf("# if you want to choose stone_weight, input '-1'.\n");
    printf("# otherwise, you have to choose the weight less than STONE_WEIGHT (%d).\n", STONE_WEIGHT);
    for(int i=0; i<N; i++) {
        int v; scanf("%d", &v);
        if(v < 0) ref_vec[i] = STONE_WEIGHT;
        else {
            assert(v < STONE_WEIGHT);
            ref_vec[i] = v;
        }
    }
#endif

    Rand rnd(1333);
    for(int i=0; i<25; i++) {
        int x1 = 0, x2 = rnd.NextInt(1, N-1);
        Verdict q = ask_to_judge(x1, x1+1, x2, x2+1);
        if(q == RIGHT) {
            answer(x1);
            return;
        }
    }

    // 1st elem is stone
    int len = 1, lb = -1, ub = -1;
    for(; ; len<<=1) {
        int cnt = min(len, N - len);
        int l1 = 0, r1 = l1 + cnt;
        int l2 = len, r2 = l2 + cnt;
        Verdict q = ask_to_judge(l1, r1, l2, r2);
        if(q != EQUAL) {
            assert(q == LEFT);
            lb = l2, ub = r2;
            break;
        }
    }

    int ll = lb;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2, w = mid - ll;
        Verdict q = ask_to_judge(0, w, ll, ll+w);
        if(q == EQUAL) lb = mid;
        else ub = mid;
    }
    answer(lb);
}

int main() {
    int T; scanf("%d", &T);
    while(T--) solve();
    return 0;
}

乱択 + うまく選んで ベキに持っていく + 二分探索できる形にする が必要で、けっこう勉強になりました。

分割統治法メモ

はじめに

これは自分の備忘録的に書いているだけであり、体系的に書いているわけではありません。ご了承ください。

ちなみに蟻本 +α くらいの情報をまとめている資料が以下にあります (ダイマ)

https://hcpc-hokudai.github.io/archive/algorithm_divide_and_conquer_001.pdf

オフラインにおける分割統治

Rollback をするテク

いくつかのデータ構造では、そのデータ構造がサポートしている操作の「逆」は難しいという話があります。たとえば UnionFind では辺の追加は普通に行えますが、削除は難しいといった問題があります。では、以下のようなクエリが要求されたときはどのように解けばよいでしょうか？

$$N$$ 個の頂点があり、はじめは辺がひとつも存在しない。以下のクエリを $$Q$$ 回処理せよ。($$N, Q \leq 10^{5}$$)

• 頂点 $$u, v$$ 間に辺が存在しないなら辺を追加する。
• 頂点 $$u, v$$ 間に辺が存在するなら辺を削除する。
• 頂点 $$u, v$$ が同じ連結成分に属するかどうかを判定する。

クエリがオフラインであるとき、これは普通の UnionFind と分割統治を用いて処理できます。なお、これの類題が Educational Codeforces Round #22 F: Bipartite Checking です。

クエリで与えられるそれぞれの辺 $$(u, v)$$ について、その辺がクエリ全体においていつ存在したかを区間として覚えておきます (要するに奇数回目に出てきたときに開いて、偶数回目に出てきたときに閉じるようにして区間を作る、ということです)。こうしてできた区間の数は明らかに高々 $$O(Q)$$ 個です。以降の説明ではこれを「辺区間」と呼ぶことにします。

この区間それぞれを分割統治法で処理することを考えます。クエリのインデックスの区間 $$[L, R)$$ を分割統治するとき、$$[L, R)$$ を完全に覆うような辺区間は UnionFind に反映させて、より細かい区間 $$[L, \mathrm{mid}), [\mathrm{mid}, R)$$ について再帰的に解きます。

再帰的に解くことが終わったら、$$[L, R)$$ を完全に覆っていた辺区間の情報を UnionFind から削除します。こうすることで Rollback の機能を実現できます。ここで、UnionFind から辺区間の情報を削除するときにはどうすればよいのでしょうか？これは、UnionFind における有名な計算量改善テクのひとつである、「小さい連結成分を大きい連結成分にマージ」のみをやることで実現できます (経路圧縮をやると壊れることに注意します)。実は、UnionFind ではひとつ前の状態に戻ることは簡単にできるため、これを活用すると Rollback ありの UnionFind を実現できます。

マージテクのみを用いるとき、UnionFind の中の配列であって unite の前後で値が変化しうるのは、頂点 $$u, v$$ の代表元のみです。なので、unite の前における代表元に関する値を覚えておき、削除したいときにその覚えた値に戻すことで、削除操作が実現できます。

条件の一部を強制的に満たすテク

条件を満たすペアの個数を求める問題で、満たすべき条件がひとつではなく複数存在する場合があります。この場合、分割統治法で処理できる可能性があります。

問題例はいっぱいあるので以下を解いてください (雑)

• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp
• https://onlinejudge.u-aizu.ac.jp/services/room.html#PakenCamp19Day2/problems/H
• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2959

オンラインにおける分割統治

正直これは分割統治かどうか微妙なんですが・・・

区間全体に対しては簡単に解け、さらにそれぞれの要素が独立に処理できる (ある要素が他のある要素による影響を受けない) 状況で、区間の一部 $$[L, R)$$ に対して問題を解いてほしいというときに、区間をいくつかのより小さい区間に分割することで処理できる場合があります。これはオンラインでもできるため一応「オンラインにおける」分割統治と書いておきます。

以下の問題を解いてみましょう。なお、紹介している問題は Educational Codeforces Round #26 G: Functions On The Segments です。

場合分けありの一次関数 $$f_i(x)$$ が $$N$$ 個与えられ、それぞれの関数は $$1$$ から $$N$$ まで番号付けられています (詳しい一次関数の形は元の問題を読んでください)。$$l_i, r_i, x_i$$ が $$Q$$ 回与えられますので、それぞれについて $$\sum_{k=l}^{r} f_k(x)$$ の値をオンラインで求めてください。

クエリにおいて区間の範囲の制約がなく、全部に対して $$f_k(x)$$ の値を足し合わせる場合、$$x_1$$ 以下であるもの、$$x_2$$ を超えるものを求めて適当に計算すれば良いです。これと同じ発想で、与えられた区間を $$O(\log N)$$ 個の区間に分割し (そのうちのひとつを $$[L, R)$$ とします)、番号インデックスの区間 $$[L, R)$$ について、その区間に含まれる関数のみを考慮して計算する、ということをやって値を合計すれば良いです (Segment Tree と同じような発想で区間を区切ってやります)。

備忘録なので説明が雑ですみません。もし質問があれば聞いてください。