読者です 読者をやめる 読者になる 読者になる

研究や趣味やらあれこれ

日々のあれこれをあれ

yukicoder No.2 素因数ゲーム

yukicoderシリーズ2回目

 

この調子で続けたい…が早速WAで進めなくなった

 

ある数Nを2人で交互に素因数で割っていく。同じ数なら何度割っても良い。1を渡されたほうが負け。どちらが勝つか出力せよ、という問題

 

至極単純…が法則がつかめなかった…

 

github.com

 

 

少し紙に書いてみて、素因数の種類の数が奇数のとき先手必勝。偶数のときは素因数分解したときの素因数の総数が偶数なら後攻必勝かな?と思って書いたのが↑

 

見事にWA。でもACのケースが多かったので惜しいのかなとか思ってしまい見事にどん詰まり

 

sugarknri.hatenablog.com

 

testestest様の解説をちら見

 

このような山崩しケームは勝敗に法則があるらしい…

 

「全山の石の個数の排他的論理和が0なら後攻必勝」

 

…?わからん。ちら見じゃ無理だ、ガン見

 

どうやらこの手のゲームはNim問題と呼ばれるもので、この排他的論理和のことを

Nim和と言うみたいで、常にNim和が0で相手に手番を渡すことができれば勝つ事ができるようだ

 

ということで書き直し

 

github.com

 

ACでした

 

世の中知らないことだらけ〜