G - Snake Escaping 2 Editorial
by 
maspy
私が使った盤面です．周期 (6,3) があります．
RGBRGBRGBRGBRGBRGBRGBRGBRGBRGB
RBGRBGRBGRBGRBGRBGRBGRBGRBGRBG
BRGBRGBRGBRGBRGBRGBRGBRGBRGBRG
BGRBGRBGRBGRBGRBGRBGRBGRBGRBGR
GBRGBRGBRGBRGBRGBRGBRGBRGBRGBR
GRBGRBGRBGRBGRBGRBGRBGRBGRBGRB
RGBRGBRGBRGBRGBRGBRGBRGBRGBRGB
RBGRBGRBGRBGRBGRBGRBGRBGRBGRBG
BRGBRGBRGBRGBRGBRGBRGBRGBRGBRG
BGRBGRBGRBGRBGRBGRBGRBGRBGRBGR
GBRGBRGBRGBRGBRGBRGBRGBRGBRGBR
GRBGRBGRBGRBGRBGRBGRBGRBGRBGRB
RGBRGBRGBRGBRGBRGBRGBRGBRGBRGB
RBGRBGRBGRBGRBGRBGRBGRBGRBGRBG
BRGBRGBRGBRGBRGBRGBRGBRGBRGBRG
BGRBGRBGRBGRBGRBGRBGRBGRBGRBGR
GBRGBRGBRGBRGBRGBRGBRGBRGBRGBR
GRBGRBGRBGRBGRBGRBGRBGRBGRBGRB
RGBRGBRGBRGBRGBRGBRGBRGBRGBRGB
RBGRBGRBGRBGRBGRBGRBGRBGRBGRBG
BRGBRGBRGBRGBRGBRGBRGBRGBRGBRG
BGRBGRBGRBGRBGRBGRBGRBGRBGRBGR
GBRGBRGBRGBRGBRGBRGBRGBRGBRGBR
GRBGRBGRBGRBGRBGRBGRBGRBGRBGRB
RGBRGBRGBRGBRGBRGBRGBRGBRGBRGB
RBGRBGRBGRBGRBGRBGRBGRBGRBGRBG
BRGBRGBRGBRGBRGBRGBRGBRGBRGBRG
BGRBGRBGRBGRBGRBGRBGRBGRBGRBGR
GBRGBRGBRGBRGBRGBRGBRGBRGBRGBR
GRBGRBGRBGRBGRBGRBGRBGRBGRBGRB
dp で経路復元します．dp は bitset を使えば時間・空間が十分少なくてよいです．
- 実験すると1000回ランダム生成して1000回上手くいきました．実験以上の確率的な考察はしていません．
- (24,24) にすると 1000回中990回上手くいきました．
- が，ジャッジに使われているデータでは (29,29) でも 1WA でした．ひとつ苦手パターンがあったようです．
- 平行移動とかを試すともっと強いかもしれません．
posted:
last update: