何回で満点とれる？【ちょまど問題に挑む人々】
-
- いいね！36
あっきー＠魔導師Lv.21
@akkyhowa
ちょまど問題で過去何回かの自分の回答とその点数が与えられたときに，それに矛盾しないような解答が存在するかの判定はNP完全(2008年Michael T. Goodrich)． #ちょまど問題
2014-06-20 17:46:44
あっきー＠魔導師Lv.21
@akkyhowa
ちょまど問題で過去何回かの自分の回答とその点数が与えられたときに，矛盾しないような解答がいくつ存在するか数えるのは#P完全(2012年Giovanni Viglietta)． #ちょまど問題
2014-06-20 17:46:48
あっきー＠魔導師Lv.21
@akkyhowa
@colun @chokudai @kusano_k 皆さん今日は楽しいディスカッションをありがとうございました．心強い言葉もありがとうございます．それではまたあまりしゃべらない人に戻りますねﾉｼ
2014-06-20 17:48:31
kusanoさん@がんばらない
@kusano_k
@colun @akkyhowa @chokudai 私だけ何もしてないw 次の機会には貢献できるようがんばります。
2014-06-20 22:08:55
おめ
@omeometo
4手全探索はどうかなとか言ってる人もいますけど3手時点で20000通り強（値忘れた）まで減らせるので4手終了時で11^4的なラインは確実に切ると思われるのであんまり意味ないだろうというのが私見ですよ
2014-06-20 17:44:25
コルン
@colun
あれあれ、chokudaiさんが言ってる全探索が、貪欲の子候補が全部、、、ってだけってことに今頃気付いた。頭悪い僕。（計算量の式を読んだ時点で気付かなきゃいけないのに。。。なぜだ。頭回ってないぞ。
2014-06-20 18:07:33
chokudai(高橋 直大)@AtCoder社長
@chokudai
（例の論文、The computation of all presented values needed a few hours on a Core 2 Duo 2.13 GHz or a Core i5 2.4 GHz processor. とか書いてあるような・・・）
2014-06-20 18:14:59
chokudai(高橋 直大)@AtCoder社長
@chokudai
一応読んでる論文はこれ snovit.math.umu.se/Personal/jaege…
2014-06-20 18:23:45
chokudai(高橋 直大)@AtCoder社長
@chokudai
「実はN択M問の時、答えはM以上になるんじゃね？」と思って、2択10問回してみたら、7と言われてしまい、ですよねー、ってなっている。
2014-06-20 18:40:43