まぁアレですよ、面倒くさくなって現実逃避するために
論文誌なんてダラダラ読んでいたら、面白そうなものが。
「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」
俺好みの話題だ。うほっ
なんでも、あのゲームのぷよぷよのルールを定式化して
入力初期盤面とピース列からｋ連鎖可能とか判定する感じ。
この問題、3-partitionからの帰着とかやることで
ＮＰ完全問題であることを証明しちゃってる。すげー
参考文献とか見ていても面白い。
二色のぷよのみを用いた全消し判定を線形時間で計算とか、
テトリスについて消去する行数の最大化もＮＰ完全だとか、
こーゆージャンルを研究している人が数多いのを知った。
金にもならないかもしれないけど、みんなの謎を解き明かす、
これが基礎研究なんだなと感心。こんな余力が世界を変える。
暇なら電子情報通信学会論文誌3月号和文Ｄとか見てみそ。
ここまで来たらやることは一つ。桃鉄でも挑戦せな。
