情報処理学会 第87回全国大会

5K-08
2色一次元ボタン&シザーズの線形時間アルゴリズム
○隼田 駿,伊藤大雄(電通大)
ボタン&シザーズとは,KyWorks Softwareによる一人用パズルである.一次元に制限されたボタン&シザーズでは,与えられた盤面が解を持つか否かを多項式時間で判定可能であることが知られている.本研究では,一次元かつ現れるボタンの色を2色に制限すると,与えられた盤面が解を持つか否かを線形時間で判定可能であることを証明する.