hogecoder

tsutaj 競技プログラミングの記録

第三回アルゴリズム実技検定 O 問題: 輪投げ

PAST AtCoder グラフ

問題概要

原文はこちら

atcoder.jp

棒が N 本ある。これらのうち異なる M 本に輪を投げ入れることを 3 回行う。投げ入れ方によって以下のように得点が定められる。

  • i 回目に j 番目の棒に輪を投げ入れたとき、 A_{j} \left( B_j \right)^{i} \bmod R_{i} 点を得る。これらの合計を X とする。
  • j 番目の棒について、全 3 回のうち i 回その棒に輪を投げ入れたとき、 A_{j} \left( B_j \right)^{i} 点を失う。これらの合計を Y とする。
  • 総得点は X - Y 点である。

得られる得点を最大化せよ。最大化した得点が負になることもある。

制約

  • 1 \leq M \leq N \leq 500
  • 2 \leq A_{i}, B_{i} \leq 1000
  • 2 \leq R_{i} \leq 10^{5}

解説

おそらくどう考えても動的計画法のアプローチでは無理だと思います。他のアプローチを考えましょう。満たすべき制約がそれなりに多いので、フローを考えてみることにします。必要そうな頂点や辺を順に考えていきます。

  1. それぞれの回において、ある M 本を選んでそこに投げなければならないので、流量 M だけ通過できるような頂点が 3 つ欲しい
  2. ある棒に関しては一度に複数回投げられないので、1. で用意した各頂点から流量 1 ずつ、棒を表す全頂点に張りたい
  3. 失点を表現できるように頂点を作りたい (後述)

符号を反転させて最小化問題として捉え、最小費用流で考えてみると、途中までは以下のようにグラフを作ると良くなります。辺に書いてある (a, b) とは、流量が a でコストが b であることを表します。

※図における A_i はすべて A_j に置き換えて読んでください

f:id:tsutaj:20200606180236j:plain

さて、実際には失点を表現できるようにグラフを作らなければならないですが、後半のグラフはどう作ればよいでしょうか？ここで超重要なのが、 B_{i} \geq 2 であるので 失点は指数的に増える ということです。より具体的に言うと、 x \lt y ならば \left( B^{x} - B^{x-1} \right) \lt \left( B^{y} - B^{y-1} \right) であることが重要です。

B の差分がどんどん広がっていくわけですので、以下のように辺を張ると、上の頂点から貪欲にいくつか使用したもののみが最小費用流の解となりえることがわかるので、このように張ると良いです。

f:id:tsutaj:20200606180249j:plain

ソースコード

// フロー 略

int main() {
    int N, M; cin >> N >> M;
    vector<ll> A(N), B(N);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++) cin >> B[i];
    vector<ll> R(3);
    for(int i=0; i<3; i++) cin >> R[i];

    Flow<ll, ll> fl(2 + 3 + N + 3*N, LONGINF, LONGINF, LONGINF);
    int source = 3 + N + 3*N, sink = source + 1;
    for(int i=0; i<3; i++) {
        fl.add_edge(source, i, M, 0);
    }
    for(int r=0; r<3; r++) {
        for(int i=0; i<N; i++) {
            ll val = A[i];
            for(int j=0; j<=r; j++) (val *= B[i]) %= R[r];
            fl.add_edge(r, 3+i, 1, -val);
        }
    }
    for(int i=0; i<N; i++) {
        ll acc = 0;
        for(int r=0; r<3; r++) {
            ll val = A[i];
            for(int j=0; j<=r; j++) (val *= B[i]);
            fl.add_edge(3+i, 3+N+(3*i+r), 1, val - acc);
            acc += val - acc;
        }
    }
    for(int i=0; i<N; i++) {
        for(int r=0; r<3; r++) {
            fl.add_edge(3+N+(3*i+r), sink, 1, 0);
        }
    }

    ll ans = fl.mincost_flow(source, sink, 3*M);
    assert(ans != LONGINF);
    printf("%lld\n", -ans);
    return 0;
}

検定の問題としては要求知識がコアだな・・・と少し思いましたが、過去問の傾向見るとこんなもんかなという気もしますね。

第三回アルゴリズム実技検定 N 問題: 入れ替えと並び替え

PAST AtCoder

問題概要

原文はこちら

atcoder.jp

長さ N の数列 A = \left( a_{i} \right) があり、 A ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計 Q 回行った後、最終的にできた数列を出力せよ。

  • 整数 1 \leq x \lt N が与えられるので、 a_{x} と a_{x+1} を交換する。
  • 整数 1 \leq l \leq r \leq N が与えられるので、 a_{l}, a_{l+1}, \ldots, a_{r} を昇順にソートする。

制約

  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq Q \leq 2 \times 10^{5}

解説

愚直にやると間に合いそうにないので、何か発想の転換が必要です。まずはどうやったら時間内に処理できそうかを考えてみましょう。

1 番目のクエリは隣り合っている要素を swap するだけなので簡単に O(1) で実現可能です。以降、2 番目のクエリをどうするかを考えます。まず、準備のため 転倒数 という概念を次のように定めます。

  • 数列 A = \left( a_i \right) のうち、 1 \leq l \lt r \leq N かつ a_{l} \gt a_{r} を満たす相異なるインデックス (l, r) の総数を 転倒数 とよぶ。

例えば A = \left[ 3, 4, 1, 5, 2 \right] という数列に関して転倒数を考えると、インデックスのペア (1, 3), (1, 5), (2, 3), (2, 5), (4, 5) について上記の条件を満たすので、転倒数は 5 となります。

さて、はじめに与えられる A は昇順にソートされていることから、転倒数は 0 であることがわかります。また、 1 番目のクエリにおいて、swap される前の要素に関して a_{x} \lt a_{x+1} ならば転倒数は 1 増え、 a_{x} \gt a_{x+1} ならば転倒数は 1 減ることがわかります。これらのことから、次のようなことが言えます。

  • ある 2 番目のクエリについて、それ以前に発生した 1 番目のクエリの回数を q とするとき、2 番目のクエリの対象となる数列の転倒数は 高々 q である。

つまり転倒数が O(Q) であることが言えるというわけです。ある範囲をソートするという操作は、言い換えるとその範囲内の転倒数が 0 となるようにすることですので、転倒数 q に対して O(f(q)) (ここで f(q) は計算量に関する関数) で対処できるようなソートアルゴリズムがあるならば、慣らし計算量 O(f(Q)) で元の問題を解くことができます。

さて、ここで問題となるのはどのようなソートアルゴリズムを持ってくるかですが、自分は本番で f(q) = q \log q のアルゴリズムを作って解きました。次でその概要を簡単に説明します。

ソートアルゴリズム

a_{k} \gt a_{k+1} を満たす k の集合を管理することを考えます。初期状態ではこのような要素は存在しないため空集合です。

1 番目のクエリで a_{x}, a_{x+1} について swap の操作が行われるとき、 (a_{x-1}, a_{x}), (a_{x}, a_{x+1}), (a_{x+1}, a_{x+2}) の高々 3 つのペアについて大小関係が入れ替わる可能性があります。これらを更新することで、次の状態に対応する集合が得られます。この操作は、例えば C++ の場合ですと std::set で O(\log q) で実現できます。

2 番目のクエリでは l \leq x \lt r を満たす全ての x について (これは swap をした結果新たに生まれる x も含む) swap をすればソートができますが、先程の議論からこのような要素の数は高々 q なので、集合を更新しながら転倒数を減らすのは全体で O(q \log q) で処理できます。

ソースコード

上の解説とちょっと違います ( a_{k} \gt a_{k+1} を満たす k+1 の集合を管理してます)

int main() {
    int N, Q; cin >> N >> Q;
    set<int> ind;    
    vector<int> A(N);
    iota(A.begin(), A.end(), 1);
    while(Q--) {
        int t, x, y; cin >> t >> x >> y;
        if(t == 1) {
            x--;            
            for(int k=-1; k<=1; k++) {
                // x+k と x+k+1 との比較 -> x+k+1 のほうを削除
                if(x+k < 0 or x+k+1 >= N) continue;
                if(A[x+k] > A[x+k+1]) ind.erase(x+k+1);
            }
            swap(A[x], A[x+1]);
            for(int k=-1; k<=1; k++) {
                if(x+k < 0 or x+k+1 >= N) continue;
                if(A[x+k] > A[x+k+1]) ind.emplace(x+k+1);
            }
        }
        if(t == 2) {
            x--;            
            while(true) {
                auto ptr = ind.upper_bound(x);
                if(ptr == ind.end() or *ptr >= y) break;

                int u = *ptr - 1;
                for(int k=-1; k<=1; k++) {
                    // u+k と u+k+1 との比較 -> u+k+1 のほうを削除
                    if(u+k < 0 or u+k+1 >= N) continue;
                    if(A[u+k] > A[u+k+1]) ind.erase(u+k+1);
                }

                swap(A[u], A[u+1]);

                for(int k=-1; k<=1; k++) {
                    if(u+k < 0 or u+k+1 >= N) continue;
                    if(A[u+k] > A[u+k+1]) ind.emplace(u+k+1);
                }
            }
        }
    }
    for(int i=0; i<N; i++) printf("%d%c", A[i], " \n"[i + 1 == N]);
    return 0;
}

結構面白い問題だなと思いました。慣らし計算量に関する良い題材ですね。

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

AtCoder グラフ

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

問題概要

原文 → D - 大爆発

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

解説

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

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

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

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

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

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

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

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

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

f:id:tsutaj:20200602012552j:plain

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

f:id:tsutaj:20200602012557j:plain

ただし一点だけ注意しなければならないケースがあります。それは、「決め打ちした行」かつ「選ぶべき列」であるマスに空きマスが 1 つも存在しない場合です。この場合は選択できるマス (= 二部グラフにおける頂点) が存在しないため、そのままでは対応できません。いま、空きマスが全体で少なくとも 1 つ以上存在する場合のみを考えているので、どこかに空きマスがある (= 爆弾をおける) としてよく、そのようなマスに爆弾を置くと元々置きたかった行または列にも置けるようになります。しかし、最初に設置した爆弾は「元々置きたかった行」かつ「元々置きたかった列」に置いているわけではないため、置くべき爆弾の数は合計で \text{ (決め打ちした行数) } + \text{ (選ぶべき列数) } + 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 さんのコードをかなり参考にしました (ありがとうございます)