Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

2017-01-13SRM 705 - 1000

問題

02:49

(制限時間 4s.)

m <= 50 個のランプと、n <= 50 個のボタンがある。ボタン i は、いくつかのランプ S_i のオンオフを切り替える。ボタンの 2^n の押し方の組合せの中で、最大でいくつのランプを点灯させることができ、その方法は何通りあるか。

解答

02:49

(まだ確かめてない)

まず S を掃き出す。掃き出したあとの行列は、左に単位行列があって、右に何かよくわからないものがあることになる。

ランクを r とする。自由度は、2^(n - r) あることになる。

r <= 27 と場合は、基底の組合せをすべて試せば良い。

r > 27 の場合は、右側のよくわからないのの幅は、22 以下になっている。この部分をキーとするDPを走らせれば良い。

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;
    }
}

2014-06-07

TCO 2013 2A 500

21:27

editorial : http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A

Problem

A magic matrix is a square matrix filled with digits (0-9) such that its row sums and column sums

all have the same last digit.

John has n by n matrix. some of them are filled and the others are empty.

Find the number of ways to get a magic matrix assigning values to the empty cells.

制約
  • すでに埋まっているセルは10個以下
  • n <= 1000

解法

n > 10 だと空の列,行があるので,簡単.

n <= 10 の場合は,連立方程式 (Ax = b) の解の個数になる.

modulo が素数ならば,体なので,自由に割り当てられる変数の個数は,変数の数 - (行列 A のランク) になる.

modulo が素数でないので Chinese remainder theorem を使う.

ただ単に,mod 2 での解の個数と,mod 5 での解の個数を掛けあわせれば良い.

何故なら,Ax = b (mod 2), Ay = b (mod 5) を満たす x, y のペアと, Az = b (mod 10) を満たす z の間には一対一の対応があるから.

SRM 614 Hard (TorusSailing)

23:42

editorial: http://apps.topcoder.com/wiki/display/tc/SRM+614

参考: http://nkl.cc.u-tokyo.ac.jp/08s/CS01/GaussSeidel.pdf

http://petr-mitrichev.blogspot.jp/2014/03/this-week-in-competitive-programming_30.html

問題

N * M のトーラス上で,右か上に 1/2 の確率でランダムウォークする.(X,Y) にたどりつくまでの歩数の期待値を求めよ.

制約
  • N, M <= 100

解法

まともな解法は,editorial を参照.アイデア: https://twitter.com/ogiekako/status/449972273940660225

ここでは,反復法で解くやりかたを書く.あまり詳しくないので,補足など下さると嬉しいです.

結局,Ax = b という形の線形連立方程式の解を求めれば良い.ただし,方程式と,変数の数が最大 10000 個になるので,Gaussian elimination では解けない.そこで反復法を使う.

まず x0 =0 として初期化する.

Jacobi 法では,ベクトル x_i から x_{i+1} を計算する.これだと収束が遅くてダメ.

Gauss-Seidel 法では,x_{i,j} を計算したらすぐに,x_{i,j+1} の計算でその値を使う.

これによって,収束が速くなって(Petrブログによると50-100倍),7000回まわせば正しい解がでるようになる.

どういう行列だと収束が速いんだろうか?

TCO 2014 R2A 500 NarrowPassage

00:40

Problem

There is a narrow passage of length L.

For each valid i, wolf i wants to move from a[i] to b[i].

The passage is so narrow that no two wolves cannot pass by each other.

Luckily, there is a lot of empty space on each end of the passage. If some wolves reach the same end of the passage, they can change their order arbitrarily before reentering the passage.

Return the minimum total distance the wolves have to travel.

Constraints
  • L <= 1e6.
  • a.length <= 50

解法

(1) 外に出ない狼がいる場合と,(2) そうでない場合に分けて考える.

(1) の場合は,左に行く人数と,右に行く人数を固定すると,可能かどうかがわかり,可能な場合は,最小距離も自明.

(2) の場合は,一旦全員が外に出た後,左側に居る狼が右側に移動する場合がある.(これに気付かなかった.)

初期状態 S から左側に行く人数と,終状態 T に左側から戻ってくる人数を固定する.

S から左側に行く狼の集合を L1 , 右側に行く狼の集合を R1 とする.

T に関しても同様に L2, R2 を定める.

L1 にいて R2 にいる狼の数と,R1 にいて L2 にいる狼の数の和が,右端から左端,または左端から右端に移動しなければならない狼の数となる.

2013-07-19

SRM585 500 - LISNumber

04:06

ちょっと変なやり方で解いた気がするのでメモ(そうでもないかも).

O(n^4).

ソースコード

public class LISNumber {
    int MOD = (int) (1e9 + 7);
    public int count(int[] cardsnum, int K) {
        long[] A = new long[K + 1];
        long[][] C = generateCombinationMod(1500, 1500, MOD);
        int all = 0;
        for (int num : cardsnum) all += num;
        if (all < K) return 0;        // !!!!!

        for (int i = 1; i <= K; i++) {// 1
            A[i] = 1;
            for (int num : cardsnum) {
                A[i] = (A[i] * C[i][num]) % MOD;
            }
        }
        for (int i = 1; i <= K; i++) {// 2
            for (int j = 1; j < i; j++) {
                A[i] -= A[j] * C[i][j];
                A[i] %= MOD;
            }
            if (A[i] < 0) A[i] += MOD;
        }
        for (int i = 1; i <= K; i++) {// 3
            for (int j = 1; j < i; j++) {
                A[i] -= A[j] * C[all - j][i - j];
                A[i] %= MOD;
            }
            if (A[i] < 0) A[i] += MOD;
        }
        return (int) A[K];
    }

    public static long[][] generateCombinationMod(int h, int w, int MOD) {
        long[][] C = new long[h][w];
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w && j <= i; j++) {
                long value = j == 0 ? 1 : C[i - 1][j - 1] + C[i - 1][j];
                if (value >= MOD) value -= MOD;
                C[i][j] = value;
            }
        return C;
    }
}

説明

1番目のループでは,A[i] = i個の箱に,(空かもしれない)単調増加列を入れる方法の数となる.

123|∅|2|3 みたいなのも入ってしまっている.

2番目のループでは,ここから∅を含むようなものを除いている.まだ,

12|3|2|3 みたいな(前の箱の最大値 < 次の箱の最小値となっている)ものも含まれてしまっている.

3番めのループでは,こういうものを除いている.

(最初書いた時,!!!!!の部分がなくて,負の添字で落ちてたorz.寝坊してよかった.)

2013-02-07

SRM569 Hard - MegaFactorial

03:23

問題

n!0 = n
0!k = 1
n!k = n!k-1 * n-1!k ... (1)
とする. n!k をB進数表記した時の末尾の0の個数をmod 1e9+9 で求めよ.
n<=1e9, k<=16, 2<=B<=10.

解法

立式

n!k に,1<=m<=n の寄与がいくつあるかを考える.

n方向,k方向の二次元の格子を考えると,

(m,1) から,(n,k) に(最短距離で)到達する方法の数の分だけ寄与することが,(1)よりわかる.

すなわち,{n-m+k-1 \choose k-1} の寄与がある.

よって,

n!k = \prod_{1\leq m\leq n}m^{n-m+k-1\choose k-1}.

B<=10のおかげで,ある素数pに対して上式が何回pで割れるかをmod M (M = 1e9+9 or 2 or 3)で計算出来れば解が求まる(詳細は略). その値は

 \sum_j\sum_{1\leq ap^j\leq n}{n-ap^j+k-1\choose k-1}.

P = p^j はすべて回すことにして,m = floor(n/P) と置くと,

 \sum_{1\leq aP\leq n}{n-aP+k-1\choose k-1} = \sum_{0\leq a\lt m}{n-mP+aP+k-1\choose k-1}

を求めれば良い.

f(N,P,m,K) = \sum_{0\leq a\lt m}{N+aP\choose K}

なる関数を高速に計算出来れば良いことになる.

Kが小さい時の組合せ

まず,単に {N\choose K} を求める方法を復習しておく.

 \begin{array}{C} {n\choose0}\\ {n\choose 1}\\ \vdots \\ {n\choose k} \end{array} = \left(\begin{array}{CCCCC}1&&&& \\ 1&1&&& \\ &&\ddots&& \\ &&&1& \\&&&1&1 \end{array} \right)^n \begin{array}{C}{0\choose 0}\\ {0\choose 1} \\ \vdots \\ {0\choose k} \end{array}

が成り立つ.これは組合せの漸化式からすぐ出てくる.中央の k+1 * k+1 行列をAとおき,右辺のベクトル(先頭要素のみが1)をxとおくと,

 {N\choose K} = \left(A^Nx\right) \[K\].

fを求める

 f = \sum_{0\leq a\lt m}{N+aP\choose K} = \sum_{0\leq a\lt m}{A^{N+aP}x\[K\]} = (A^N(\sum_{0\leq a\lt m}(A^P)^a)x)\[K\].

よって,B=A^Pとしたとき,

 \sum_{0\leq a\lt m}B^a を高速に計算出来れば良いことになる.

これは可能で,

 B' = \left(\begin{array}{CC}B&I \\ 0&I \end{array}\right) とおくと, B'^m の右上にそれが現れる.

あるいは,

 \sum_{0\leq a\lt m}B^ax を直接計算することもでき,

 B' = \left(\begin{array}{CC}B&x \\ 0&1 \end{array}\right) とおくと, B'^m の右上にそれが現れる.こちらのほうが8倍くらい高速.

計算量は,O(\log^2nK^3)くらい.

おわり

ところで,しばらくmodの値を1e9+7と間違えてハマっていたorz