1/26 PKU

3537 Crosses and Crosses

1*Nのマス目があって、先手と後手が交互に×を書いていく。×が3つ並んだら並べた人の勝ち。どっちが必勝か求めよ。

×が3つ並んだら勝ちとは、すなわち×が置かれたらその１つか２つ隣に×を置くと負けるということになる。これを考えてGrundy's Numberを用いる。

3541 Given a string…

ビット列T,Sが与えられる。Sをi回転させてできるビット列と、j回転させてできるビット列でXORをとったとき、Tに一致するようなi,jは存在するか判定せよ。

i=0と固定し、できた文字列を回転させてTと一致するか判定する。これはKMPを使えばできる。O(N^2)で微妙だけど通る。

1947 Rebuilding Roads

いくつかの畜舎が道で結ばれて、木構造をなしている。道が地震で壊れ、ちょうどP個の畜舎が他の畜舎から切り離される（他の畜舎への道がない）とき、最低何本の道が壊れたか。

根付き木にしてDP。