10/1 PKU

1659 Frogs' Neighborhood

蛙が何匹かいる。何組かの蛙はお互いに隣人であるらしい。各蛙の隣人の数が与えられるので、条件を満たす関係を1つ出力せよ、という問題。

2 < N < 10は大嘘らしい。配列の添字を9から20に変えるだけで通った。全探査やるだけ

2311 Cutting Game

長方形を切っていくゲーム。１回に１枚を、X軸かY軸に平行に切ることができる。1*1のかけらを作ったら勝ち。W*Hの長方形について、どっちが必勝？

Grundy数使ってDP。

2461 Magic Bitstrings

素数pがあって、長さp-1のビット列を考える。そのビット列の最後に、仮想的な「非ビット」xを付け加えて、さらにこれを循環文字列とみないして、次の規則でp-1個のビット列を生成する。
「1個目のビット列は元のビット列から1番目,2番目,…と1個ごとに選ぶ。2個目のビット列は2番目,4番目,…と2個ごと。3個目以降も同様。」
そうしてできたp-1個のビット列は、どれも最初のビット列に等しいか、その反転になっているという。そのような最初のビット列のうち、辞書順最小のものを出力せよ。もちろん、0か1をp-1個出力したりしてはいけない。

まずp=2のときはImpossibleを出力して終了。
それ以外のときは、まずpの原始根aを求める。そして、str[a^0]=0, str[a^1]=1, str[a^2]=0, …と0と1を交互にstrに埋めていく。

これでstrが、条件を満たしている理由は、(p-1)*(p-1)の表を作って、マス(i,j)にはa^k==ij (mod p)なるk(aは原始根より、そのようなkが存在)を入れてやると明らか。
そしてそれを見ていると、strの取り方として、「str[a^x]==str[a^y]⇒str[a^(x+i)]==str[a^(y+i)]」が成立する必要があることがわかり、str[a^x]==str[a^(x+1)]が成り立つと0か1をp-1個出力する羽目になるので、先程の求め方で求まるstrと、その反転しか答えが存在しないことがわかる。