読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Week of Code 24

Apple and Orange

Happy Ladybugs

空きスペースがある場合は自在に動かせるので、同じ色のものを固めてしまうのが良い。もともと 1 つしかないのであれば NO である。

空きスペースがない場合は一切動かせないので、そのまま判定を行う。

Simplified Chess Engine

このチェスの特徴としてかなり高確率でチェックできる。チェックされているときは逃げるしかないので分岐数が減る。チェックしているのに見逃すのも無駄。このことを考慮すればm=6手くらいなら余裕で読める。

Xor Matrix

二進数にして桁ごとに計算する。

数列の長さが有限だと端の扱いが面倒なので、無限と考えてみよう。このときある要素の影響はパスカルの三角形のフラクタルと同じ形になる。

パスカルの三角形のフラクタルは以下の操作で作ることができる。初期状態では x[s]=1 としておく。

if (m >> 0 & 1) x ^= x >> 1
if (m >> 1 & 1) x ^= x >> 2
if (m >> 2 & 1) x ^= x >> 4
if (m >> 3 & 1) x ^= x >> 8
...

2k+1段目が端だけ 1 であることと、操作を 2 冪にばらすと各操作は干渉しないことを考えればこの操作が正しいことが分かる。実際には数列は有限なので、シフトは回転シフトに変わる。

複数箇所にセットすれば重ね合わせの理でまとめて処理できるので O(30*60*n/64)。

Shashank and the Palindromic

より単純な問題として、文字列に含まれる回文の個数を数える問題を考える。これは区間 DP で O(n2) でできる。

dp[l][r]:=S[l..r] に含まれる回分の個数 とすると、まず s[l], s[r] を使わないという遷移がある。

$$ dp[l][r] \gets dp[l+1][r]+dp[l][r-1]-dp[l+1][r-1] $$

dp[l+1][r-1] を引いているのはダブルカウントしている分を打ち消すため。また s[l]==s[r] が成り立っている場合は、s[l]とs[r]をペアにするという遷移がある。

$$ dp[l][r] \gets 1+dp[l+1][r-1] $$

1 を足しているのは、そのペアで構築を終了することを意味している。

これを少し変えれば今回の問題でも O(n2) でできる。部分列が空になってしまうような遷移をしないようにすれば良くて、これは 2 bit の情報を付加することで実現できる。

Academy Surveillance

簡単のためにまず 3×w の問題を考えてみよう。最初の 3×3 をまず決めてしまう。これは 9C2=36 通りある。次に abc を決定することを考える。

036a
147b
258c

abc の選択可能範囲は 012 にのみ依存する。そのため dp[ width ][ 012 ]:=num という DP により解くことができる。遷移は 3 つ飛ばしに行えば良い。

一般的に H×W の問題を解くことを考えよう。H×W の場合もやはり依存関係は 3 つ飛ばしで現れる。つまり wwwwwww の選択は xxxxxxx の選択にのみ依存している。

xxxxxxx
yyyyyyy
zzzzzzz
wwwwwww

では xxx と www はどのような関係なのだろうか。簡単にわかることとしてXXXとWWWの1の個数は等しい。

XXX....
.......
.......
WWW....

また WWW の部分が決まれば、残りの wwww の部分も自動的に定まる。つまり wwwwwww として取りうるパターンはたかだか 3 通りである。

今度は次の大文字部分に着目してみよう。

X..X..X
.......
.......
W..W..W

もし 0..11..0 という部分があったら X=W で確定する。一方 0..01..1 しか現れない場合は X=W であっても X=!W であっても良い。よって 0..11..0があるかどうかという情報があれば、xxxxxxxx を決めたとき wwwwwww が何通りあるかを知ることができる。

ところで、AAAAAAA を確定させたとき BBBBBBB として取りうるパターン数が 3 通りだったとする。すると CCCCCCC として取りうるパターン数も 3 通りになる。これは0..11..0 があるという状態が遺伝するためである。つまり AAAAAAA を確定させたとき BBBBBBB として取りうるパターン数さえ分かれば累乗の計算をするだけで求めることができる。

AAAAAAA
.......
.......
BBBBBBB
.......
.......
CCCCCCC

以上のことを踏まえれば解くことができる。