Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2015-08-22TCO15 R2D 500 BallsInBoxes

TCO 2015 2D 500 BallsInBoxes

19:30

問題

N 個の箱があって、そのうち連続する K 個の箱にボールが入っている。できるだけ少ない個数の箱を開けてすべてのボールの位置を特定したい。最適な戦略をとった場合にあける必要のある箱の個数を答えよ。戦略は固定ではなくボールの有無によって次に開ける箱を変えて良い。

制約
  • K <= N <= 10^18

解法

はじめに以下のように問題の言い換えをする。

集合 S = {1, 2, ..., N - K + 1} がある。S の大きさが 1 になれば Alice の勝ちである。各ターンで、Aliceクエリ L = {max(1, x-K+1), ..., x-1, x} (1 <= x <= N) を発行し、Bob は S ∩ L、S \ L の好きな方で S を置き換える。Alice が自分が勝つまでのターン数を最小化、Bob が Alice が勝つまでのターン数を最大化するようにふるまったときの、Alice が勝つまでのターン数を求めよ。

|L| <= K であることより、Bob は、S \ L を返すことで、S の要素数を K 個しか減らさないことが可能である。また、S ∩ L、S \ L のうちの要素数の多い方を返すことで、S の要素数を floor(|S|/2) 個しか減らさないことも可能である。まとめると、Bob は S の要素数を min(K, floor(|S|/2)) 個しか減らさないことが可能である。逆に、Alice は常に S の要素数を min(K, floor(|S|/2)) 個減らすようにクエリを発行することができる。具体的には、|S| > 2 * K の時は L = {1, ..., K} とし、|S| <= 2 * K の時には L = {1, ..., |S| / 2} とすればよい。(インデックスは適宜平行移動して付け替える。S ∩ L も S \ L も連続になることに注意。)

以上より、Alice と Bob がこの戦略をとった時のターン数を答えれば良く、これは容易である。

ソースコード

import java.util.Arrays;

public class BallsInBoxes {
    public long maxTurns(long N, long K) {
        N -= K - 1;
        long res = 0;
        if (N > 2 * K) {
            long t = (N - 2 * K + K - 1) / K;
            res += t;
            N -= K * t;
        }
        while (N > 1) {
            res++;
            N -= N / 2;
        }
        return res;
    }
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/ogiekako/20150822
 |