Google Code Jam 2010 Round 3

A

線形合同法で生成した乱数列が部分的に与えられるので、次に出てくる数を答えよ、という問題。乱数は法Pで生成され、Pの桁数Dが与えられる。

決めないといけない変数が二つあるので、要素数が3つないと決定できないことがある。3つの乱数X->Y->Zという列があれば、AX+B=YかつAY+B=Z(=は法Pで等しいの意味)が成り立つので、(X-Y)A=Y-Zになる。これは法Pでの話なので、X-Yで除算できるので、Aが求まる。後はAを代入すればBが決定できる。これにより次の要素を生成できる。4つ以上与えられている場合には検証を続け、目的のものを探す。これをすべての可能なPについて行った結果、出てきた数字がユニークに定まればそれを答える。

また、要素数が2個の場合にも、同じ数字が連続している場合には副作用がない乱数生成なので決定可能になる点に注意する。