Official

C - Piles of Pebbles Editorial by yutaka1999


\(A_i\)\(X+Y\) で割ったあまりを \(B_i\) とおきます.以下,高橋君,青木君のことをそれぞれ先手,後手と呼ぶことにします.

まず \(B_i\) がすべて \(X\) より小さい場合,後手の勝ちです.というのも,先手が選んだ山について,操作後の \(B_i\) の値は \(Y\) 以上となるので,後手は同じ山を選ぶことで\(B_i\) の値を元の値に戻すことができるからです.

次に \(X \leq Y\) として,ある \(B_i\)\(X\) 以上の場合を考えると,先手の勝ちとなります.というのも,\(B_i\)\(X\) 以上の山を選んで操作することで,\(B_i\) がすべて \(Y\) より小さい状態にすることができるからです.

最後に \(X>Y\) の場合を考えます.このとき,\(B_i\)\(X\) より小さい山を選ぶことはできず,逆に \(X\) 以上の山は必ず選ばなければいけません.よって,選ぶべき山の集合が一意に決まり,先程の場合から勝敗を決定することができます.

posted:
last update: