KMCv2 SRM 16

成績

1. A……AC 187.64/250.00
2. B……AC 458.99/500.00
3. C……Opened

3/6位

A

一番右端にドミノを置くとき、その置き方は「縦縦」か「縦横横」か「横横縦」か「横縦横」か「横横横横」だけ。

4xW にぴったりドミノを置くときの置き方を f(W) と書く。するとまずW列目に「縦縦」で置くときの置き方は f(W-1) 通りで、「横横横横」で置いた時は f(W-2) 通り。

次に4xWのうち右下の二つだけが空いている状態の置き方を f₁(W) と書くと、W列目に「縦横横」と置いたときの置き方が f₁(W-1) 通りになる。また4xWのうち右上の二つだけが空いている状態の置き方も f₁(W) と等しくなるので、W列目に「横横縦」と置いたときの置き方も f₁(W-1) 通りになる。

さらに4xWのうち右上一個と右下一個だけが空いている状態の置き方を f₂(W) と書けば、W列目に「横縦横」で置いた時は f₂(W-1) 通り。

したがって f(W) = f(W-1) + f(W-2) + 2f₁(W-1) + f₂(W-1)

次に f₁についても漸化式を立てる。

W列目の残り(赤いドミノ)がどう置かれているかで2通りに場合分けできる。case2では緑の部分に注目する。

最後に f₂についても漸化式を立てる。

これもW列目の残り(赤いドミノ)の置き方で場合分け。case2では赤の置き方から青の置き方が定まるので、残った緑の部分に注目する。

これで

f(W) = f(W-1) + f(W-2) + 2f₁(W-1) + f₂(W-1)
f₁(W) = f(W-1) + f₁(W-1)
f₂(W) = f(W-1) + f₂(W-2)

と式が立ったのであとはDPする。

B

ブレートシュナイダーの公式を見ると、四辺の長さが分かっていれば対角の和を180°にすればよいことが分かる。対角の和が180°ならブラーマグプタの公式になる。

ある四角形の四辺の長さを変えずに対角の和を180°にするように変形することができるかどうか考えたらなんかできそうだったのでブラーマグプタするだけのコードを書いたら通った。

C

よんでない