2005-02-01から1日間の記事一覧

ぷよぷよと計算の複雑さ

第2回ぷよマスターズで準優勝した松金氏の発表。 どちらかというと「なぞぷよ」のネタ。盤面は可能な限り広くとった上での四色+おじゃまぷよ連鎖数判定問題がNP完全という話。3-PARTITIONでYESなら連鎖数判定問題でk連鎖可能なインスタンスが作れて、逆に連…