Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

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 にいる狼の数の和が,右端から左端,または左端から右端に移動しなければならない狼の数となる.

 |