[yukicoder] No. 1242 高橋君とすごろく

問題

方針

後ろから考える

マス \( x \) にいるとき、ゲームオーバーマスのマスペアが \(( x + 1, x + 6) \) または \( (x + 2, x + 5) \) または \( ( x + 3, x + 4) \) に存在するとき、ゲームオーバーになるので、マス \( x \) もまたゲームオーバーマスとなります。

マス \( x + 1, x + 6 \) にゲームオーバーマスがあるとき

このとき、マス \(x + 6, x + 1, x \) とゲームオーバーマスがあることになるので、

\[ x + 6, x + 1, x, x – 3, x – 5, x – 6, x – 8, x -9, x-10, x – 11, x – 12, \cdots \]

とゲームオーバーマスが存在することになります。

マス \( x + 2, x + 5 \) にゲームオーバーマスがあるとき

このとき、マス \(x + 5, x + 2, x \) とゲームオーバーマスがあることになるので、

\[ x + 5, x + 2, x, x – 1, x – 3, x – 4, x – 6, x -7, x-8, x – 9, x – 10, x – 11, x – 12\cdots \]

と地雷が存在することになります。

マス \( x + 3, x + 4 \) にゲームオーバーマスがあるとき

このとき、マス \(x + 4, x + 3, x \) とゲームオーバーマスがあることになるので、

\[ x + 4, x + 3, x, x – 2, x – 3, x – 5, x – 6, x -7, x-8, x – 9, x – 10, x – 11, x -12, \cdots \]

と地雷が存在することになります。

マス \( x \) にゲームオーバーマスがあるとき

このとき、マス \( x + 1, x + 3, x + 5 \) のいずれかにゲームオーバーマスがある場合、\( x – 9 \) 以降のマスが全てゲームオーバーマスとなります。したがって、\( A_i \geq 10 \) を満たす \( A_i \) に対して、

\[ A_i + 1 = A_j \vee A_i + 3 = A_j \vee  A_i + 5 = A_j\]

を満たす \( A_j \) が存在するとき、ゲームオーバーとなります。

また、マス \( 9 \) 以下のマスについてはゲームオーバーマスがマス \( 1 \) に出現するかをシミュレーションします。

コード

参考